2、最优化理论的简介

1、最优化模型及其分类

最优化的数学模型一般表示为
$\begin{cases} \underset{x\in\mathbb{R}^n}\min&{f(x)},\\ \rm{s.t} ~~~~ &c_i(x)=0,~~i=1,2,\dots,m_e,\\ &c_i(x)\ge 0,~~i=m_e+1,\dots,m, \end{cases}$
其中 $~f(x)~$ 及 $~c_i(x)~(i=1,2,\dots,m)$ 都是定义在 $~\mathbb{R}^n~$ 上的实值连续函数，且至少有一个是非线性的。如果 $~m=0~$ ，则问题被称为无约束优化问题。如果 $~m~$ 是正整数，则问题被称为约束优化问题。其中， $~f(x)~$ 称为目标函数， $~c_i(x)~$ 称为约束函数。如果 $~f(x),c_i(x)~$ 都是线性函数，则问题就是线性规划。如果 $~f(x)~$ 和 $~c_i(x)~$ 存在一个非线性函数，则问题就是非线性规划。特别地，若 $~f(x)~$ 为二次函数， $~c_i(x)~$ 为线性函数，则问题是二次规划问题。
$\color{red}{不过我们主要研究的是无约束非线性规划问题}$

2、求解无约束优化问题的方法

无约束优化问题，即
$\min_{x\in\mathbb{R}^n}~f(x)\tag{1}$
求解无约束优化问题 (1) 的算法有线搜索算法和信赖域法等
(1)、线搜索
线搜索的基本迭代格式为
$x_{k+1}=x_k+\alpha_k d_k\tag{2}$
其中 $~d_k~$ 是搜索方向， $~\alpha_k>0~$ 是搜索步长为线搜索确定。线搜索分为精确线搜索和非精确线搜索

i、精确线搜索
$\alpha_k=\arg\underset{\alpha>0}\min~f(x_k+\alpha d_k)$
精确线搜索的代价较高，实际计算中很难实现和锯齿现象。所以在实际中我们会常常选择非精确线搜索，不要求函数 $~f(x)~$ 沿着方向 $~d_k~$ 下降到最小，只需满足一定的下降条件即可。以下列举几种常见的非精确线搜索

ii、Armijo-Goldstein 准则
这一准则是 Armijo 和 Goldstein 在 20 世纪 60 年代提出的，它要求步长 $~\alpha_k~$ 满足下列条件
$\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\alpha_k\rho g_k^Td_k\\ f(x_k+\alpha_k d_k)\ge f(x_k)+\alpha_k(1-\rho) g_k^T d_k\tag{3} \end{cases}$
其中 $~0<\rho<\sigma<1~$ ，(3) 式中的第一个不等式是保证目标函数有足够的下降，第二个不等式则防止 $~\alpha_k~$ 过小

iii、Wolfe--Powell 准则
由于 $~\rm{Armijo-Goldstein}~$ 准则有可能把步长的极小值排除在接受区间外，为此 Wolfe 和 Powell 提出了如下准则
$\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k\\ g(x_k+\alpha_k)^T d_k\ge\sigma g_k^Td_k\tag{4} \end{cases}$
其中 $~0<\rho<\sigma<1~$ ，(4) 式中第一个不等式是关于函数信息，第二个不等式是曲率信息。Wolfe-Powell 准则也被称为标准 Wolfe 准则。

iV、强 Wolfe 准则
(4) 中的不足之处在于，当 $~\sigma\rightarrow 0~$ 时也不能得到精确线搜索。为此有
$\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k\\ \vert g(x_k+\alpha_k)^T d_k\vert\le-\sigma g_k^Td_k\tag{5} \end{cases}$

以上只是几种常见的线搜索，线搜索的种类有很多，以后会详细谈到。要使得上述线搜索中的 $~\alpha_k~$ 存在，则 $~d_k~$ 应是下降方向，即
$g_k^T d_k< 0,~~~\forall~~k\ge 1\tag{6}$
关于 $~\alpha_k~$ 的存在性，我们都未给出证明，可以参考一些书籍，或者一些知网上面的文章吧，过程并不复杂。

(2)、线搜索算法
下面介绍几种常见的线搜索算法：最速下降法，牛顿法，阻尼牛顿法、共轭梯度法和拟牛顿法。

i、最速下降法
1847 年，法国数学家 Cauchy 在研究函数沿什么方向下降最快的问题，提出了最速下降法。其基本迭代格式
$x_{k+1}=x_k-\alpha_k^c g_k\tag{7}$
其中 Cauchy 步长 $~\alpha_k^c~$ 由精确线搜索所确定，虽然理论是 $~-g_k~$ 是函数 $~f(x)~$ 在 $~x_k~$ 下降最快的方向且 Cauchy 步长让函数在搜索方向最小，但这只是反映了函数的局部性质。从整体上看，最速下降法效率却很低，因为相邻的两次搜索方向是正交。当趋于极小值时，锯齿现象会更严重。

ii、牛顿法
若 $~f(x)~$ 二阶连续可微，由 Taylor 公式， $~f(x)~$ 在 $~x_k~$ 处的二阶近似为
$f(x)\approx f(x_k)+g_k(x-x_k)+\frac{1}{2}(x-x_k)^TG_k(x-x_k)=m_k(x)$
假设 Hesse 矩阵 $~G_k~$ 是正定的，牛顿法将 $~m_k(x)~$ 的极小值作为下一个迭代点。即
$x_{k+1}=x_k-G_k^{-1}g_k$
当初始点接近极小值点时，牛顿法是二阶收敛的。值得注意的是，当初始点远离极小值点时，牛顿法可能不收敛，为此提出了阻尼牛顿法。

iii、阻尼牛顿法
牛顿法面临的主要困难是 $~G_k~$ 不正定，在这种情况下，下降方向很难获得，为此有阻尼牛顿法。阻尼牛顿法的种类有很多，主要介绍两种，分别是 Goldstein--Price 修正和 Goldfeld 修正。他们思想都很简单，Goldstein--Price 修正就是如果 $~G_k~$ 不正定，我们选择负梯度方向作为搜索方向。Goldfeld 修正就是若 $~G_k~$ 不正定，令 $~d_k=-B_k^{-1}g_k~$ ，其中 $~B_k=G_k+ E_k~$ ，其中 $~E_k~$ 是修正矩阵。

iv、共轭梯度法
$\color{red}{共轭梯度法是我目前研究的方向，此处只是简单提一下，后面会有更加详细的介绍。}$
1952 年，Hestense 和 Stiefel 在求解线性方程组 AX=b 时提出了共轭梯度法，我们称为线性共轭梯度法。1964 年，Fletcher 和 Reeves 将共轭梯度法应用到求解二次函数的局部极小点问题中，这通常被认为是求解无约束优化问题的非线性共轭梯度法的开端。共轭梯度法由于只是需要一阶导数信息，所以具有存贮量小的特点，适合求解大型无约束无约束优化问题。共轭梯度法有很多细分方向，比如混合共轭梯度法，三项共轭梯度法，修正共轭梯度法，三项共轭梯度法等。

V、拟牛顿法
拟牛顿法就是用拟牛顿矩阵 $~B_k~$ 近似 $~\rm{Hesse}~$ 矩阵 $~G_k~$ ，从而避免直接计算 $~G_k~$ ，矩阵 $~B_k~$ 满足拟牛顿方程
$B_ks_k=y_k$
其中 $~s_k=x_{k+1}-x_k,y_k=g_{k+1}-g_k~$ ，不同的拟牛顿矩阵对应不同的算法，主要有 DFP 算法和 BFGS 算法。此处省略。

(3)、信赖域法
根据前面的分析，我们知道线搜索是先确定搜索方向，再由线搜索条件确定步长因子，从而确定位移。但是信赖域法则不然，是在算法中直接求出每次迭代步的位移。
信赖域法首先给出一个位移长度上界（信赖域半径），以当前点为中心，以此上界为半径确立一个领域。然后通过求这个领域内的二次近似目标函数的最优点来确定候选位移。这个区域内的近似函数往往是可信赖的而称为信赖域。若新的位移能够使目标函数值充分下降，则接受候选位移，并保持或扩大信赖域范围，然后继续新的迭代。若新的位移不能使目标函数值充分下降，这说明二次模型与目标函数的近似程度不够好，因此需要缩小信赖域范围，然后通过新的信赖域内二次模型，求新的候选位移。
其基本数学模型为
最优化的数学模型一般表示为
$\begin{cases} &\min~~~~&m_k(s)=f_k+g_k^Ts+\frac{1}{2}s^T B_ks\\ &\rm{s.t}&\Vert s\Vert\le\triangle_k\tag{8} \end{cases}$
其中 $~\triangle_k~$ 是信赖域半径， $~B_k~$ 为 $~G_k~$ 的近似，我们定义实际下降量（ $Ared_k$ ）和实际下降量（ $Pred_k$ ）
$Ared_k=f_k-f(x_k+s_k)$
$Pred_k=m_k(0)-m_k(s_k)$
定义比值为
$\rho_k=\frac{Ared_k}{Pred_k}$
若 $~\rho_k~$ 趋于1，则二次模型与目标函数在信赖域范围内有很好的近似，则可令 $~x_{k+1}=x_k+s_k~$ ，下一次迭代可以适当扩大信赖域半径。否则，我们就需要缩小信赖域半径。

$\color{red}{以上内容也只是根据我个人所理解书写出来，可能有不当之处。我目前主要研究的是共轭梯度法，所以后面会详细介绍共轭梯度法。}$

最后编辑于：2022.08.10 19:51:01

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,793评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,567评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,342评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,825评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,814评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,680评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,033评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,687评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,175评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,668评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,775评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,419评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,020评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,206评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,092评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,510评论 2赞 343

2、最优化理论的简介

1、最优化模型及其分类

2、求解无约束优化问题的方法

推荐阅读更多精彩内容