最优化理论

一维搜索:

1精确一维搜索

精确一维搜索可以分为三类：区间收缩法、函数逼近法（插值法）、

以及求根法。

区间收缩法：用某种分割技术缩小最优解所在的区间(称为搜索

区间)。包括：黄金分割法、成功失败法、斐波那契法、对分搜索法

以及三点等间隔搜索法等。

优化算法通常具有局部性质，通常的迭代需要在单峰区间进行操

作以保证算法收敛。确定初始区间的方法：进退法

①已知搜索起点和初始步长；②然后从起点开始以初始步长向前

试探，如果函数值变大，则改变步长方向；③如果函数值下降，则维

持原来的试探方向，并将步长加倍。

1.1黄金分割法：

黄金分割法是一种区间收缩方法(或分割方法)，其基本思想是通

过取试探点和进行函数值比较，使包含极小点的搜索区间不断缩短以

逼近极小值点。具有对称性以及保持缩减比原则。

优点：不要求函数可微，除过第一次外，每次迭代只需计算一个

函数值，计算量小，程序简单；

缺点：收敛速度慢；

函数逼近法（插值法）：用比较简单函数的极小值点近似代替原

函数的极小值点。从几何上看是用比较简单的曲线近似代替原的曲线，

用简单曲线的极小值点代替原曲线的极小点。

1.2牛顿法：

将目标函数二阶泰勒展开，略去高阶项后近似的替代目标函数，

然后用二次函数的极小点作为目标函数的近似极小点。

牛顿法的优点是收敛速度快，缺点是需要计算二阶导数，要求初

始点选的好，否则可能不收敛。

1.2抛物线法：

抛物线法的基本思想就是用二次函数抛物线来近似的代替目标

函数，并以它的极小点作为目标函数的近似极小点。在一定条件下，

1

抛物线法是超线性收敛的。

1.3三次插值法：

三次插值法是用两点处的函数值和导数值来构造差值多项式，以

该曲线的极小点来逼近目标函数的极小点。一般来说，三次插值法比

抛物线法的收敛速度要快。

精确一维搜索的方法选择：

1如目标函数能求二阶导数：用Newton法，收敛快。

2如目标函数能求一阶导数：

1如果导数容易求出，考虑用三次插值法，收敛较快；

2对分法、收敛速度慢，但可靠；

3只需计算函数值的方法：

1二次插值法, 收敛快，但对函数单峰依赖较强；

2黄金分割法收敛速度较慢，但实用性强，可靠；

4减少总体计算时间：非精确一维搜索方法更加有效。

2非精确一维搜索

精确搜索计算量较大，特别是当迭代点远离最优解时，效率很低；

而且，很多最优化方法的收敛速度并不依赖于精确一维搜索的过程。

非精确的一维搜索：通过计算少量的函数值，得到一个可接受步

长，使得后续迭代点使目标函数要“充分”下降,达到一个满意水平，

非精确一维搜索方法可大大节省计算量，且总体上有较快的收敛速度。

不用寻找单谷区间！

包括Armijo-Goldstein准则和Wolfe准则。Armijo-Goldstein 准则

可能将目标函数的极小点给排除在可接受区域外！！ Wolfe将准则更

新后可避免最优解被排除。

2

2无约束优化

2.1一维搜索

（精确一维搜索，非精确一维搜索）

2.2最速下降法

基本思想：以负梯度方向为下降方向，利用精确一维搜索得最佳

步长。

最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭

代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，这样

从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极

小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运

用中，在可行的计算时间内可能得不到需要的结果。

优缺点：

优点：1方法简单，每迭代一次的工作量和存贮量小；2从一个

不好的初始点出发，也能保证算法的收敛性。

缺点：1在极小值点附近收敛得很慢；2梯度法的收敛速度与变

量的尺度关系很大；3梯度法对小的扰动是不稳定的，这样就可能破

坏方法的收敛性。

2.3牛顿法

基本思想：将目标函数二阶泰勒展开，略去高阶项后近似的替代

目标函数，然后用二次函数的极小点作为目标函数的近似极小点。

优点：

1初始点离最优解很近时，算法收敛速度快；

2算法简单，不需要进行一维搜索(确定步长=1)；

3正定二次函数，迭代一次就可得到最优解。

缺点：

1对多数算法不具有全局收敛性，对初值依赖；

2每次迭代都要计算Hes矩阵的逆，计算量大；

3海塞矩阵的逆可能不存在或者对应方程组奇异(或病态);

4海塞矩阵可能非正定，d可能不是下降方向，算法也可能收敛

于最大值点或者鞍点。

3

2.4阻尼牛顿法：

基本思想：阻尼牛顿法中下降方向仍为牛顿方向，但最佳步长通

过精确一维搜索得到。

若f(x)存在二阶连续偏导数，函数的Hes矩阵正定，且水平集

有界，则阻尼Newton法或者在有限步迭代后终止，即具有二次终止

性。

2.5共轭梯度法

用迭代点处的负梯度向量为基础产生一组共轭方向的方法叫做

共轭梯度法。

最速下降法计算简单，但收敛速度慢，Newton法(阻尼)具有收敛

速度快的优点，但需要计算Hes矩阵的逆，计算量大。共轭梯度法

它比最速下降法的收敛速度要快得多，同时又避免了像牛顿法所要求

的海塞矩阵的计算，存贮和求逆。

共轭梯度法的特点：

1对凸函数全局收敛（下降算法）；

2计算简单，不用求Hes矩阵或者逆矩阵，计算量小，存储量

小，每步迭代只需存储若干向量，适用于大规模问题；

3具有二次收敛性；

4共轭梯度法的收敛速率不坏于最速下降法。如果初始方向不用

负梯度方向，则其收敛速率是线性收敛的；

2.6变尺度法（拟牛顿法）

最速下降法计算简单，但收敛速度慢，Newton法(阻尼)具有收敛

速度快的优点，但需要计算Hes矩阵的逆。上述两种方法可用一个

统一的模型描述，为减小计算量，用尺度矩阵近似代替海塞矩阵的逆，

由此产生搜索方向的方法称为变尺度法。

特点：

1若尺度矩阵正定，，则每一迭代步总使得函数值下降，即算法

是稳定的。

2易计算性，尺度矩阵在迭代中逐次生成，初始矩阵为任一正定

矩阵，修正矩阵选取的不同，对应着不同的变尺度法。包括对称秩1

4

校正公式、DFP算法、BFGS算法以及布洛伊登族尺度法。

对称秩1校正公式：

SR1校正公式的缺点是尺度矩阵的正定性不具有遗传性质，从能

可能导致算法终止，即算法不稳定。SR1的优点是其对海塞矩阵的逆

的近似比BFGS法还好；算法具有二次终止性。

DFP算法：

若目标函数是正定二次函数，则DFP算法经过有限步迭代必达

到极小点，既具有二次收敛性。若 f (x)是可微的严格凸函数，则DFP

算法全局收敛。实际运算中，由于舍入误差的存在可能影响算法的稳

定性，但BFGS算法受到的影响要小得多。

BFGS算法：

它比DFP的数值稳定性更好并且在一定条件下可以证明在

BFGS法中使用不精确一维搜索时有全局收敛性。

2.7直接搜索法

直接搜索法包括：模式搜索法、Powell法、和单纯形法。

1模式搜索法

Hooke & Jeeves方法：

逼近极小点,算法从初始基点开始,包括两种类型的移动，探测移

动和模式移动。

探测移动：依次沿n个坐标轴进行,用以确定新的基点和有利于函数

值下降的方向。

模式移动：沿相邻两个基点连线方向进行。

Ronbrock算法(转轴法)：

算法每次迭代包括探测阶段和构造搜索方向两部分。

探测阶段:从一点出发,依次沿n个单位正交方向进行探测移动,

一轮探测之后,再从第1个方向开始继续探测.经过若干轮探测移动,完

成一个探测阶段。

构造搜索方向：利用探测阶段得到的结果构造一组新的正交方向,

并将其单位化称之为转轴。下次探测方向按照最新生成的正交方向进

5

行探测。

2 Powell方法

基本思想：Powell方法主要由基本搜索、加速搜索和调整搜索方

向三个部分组成。基本搜索包括从基点出发沿着已知的n个搜索方向

进行一维搜索，确定一个新基点；加速搜索是沿着相邻的两个基点的

连线方向进行一维搜索，使函数下降更快；最后用基点连线方向代替

已知的n个搜索方向之一，构造新的搜索方向组并进行下一步迭代。

与模式搜索法的异同：

Powell方法用一维搜索取代模式搜索中的试探方式；

Powell方法的加速搜索采用的方式与模式搜索法类似，仅在步长

的取法上有一定差异，Powell方法仍然采用一维搜索方法；

Powell方法产生新的迭代方向，而模式搜索法迭代方向保持不变

或者产生正交迭代方向，与之相比，Powell方法所产生的迭代方向为

共轭方向，具有二次收敛性。

Powell法存在的问题：

在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭

方向。这时组不成n维空间，可能求不到极小点。

3单纯形法

基本思想：单纯形替换法不是利用搜索方向从一个点迭代到另一个更

优的点，而是从一个单纯形迭代到另一个更优的单纯形。在单纯形替

换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、

收缩和缩边这4个操作来实现。

2.8信赖域算法

信赖域方法是把最优化问题转化为一系列相对简单的局部寻优

问题。方法能够对局部的所有方向进行“搜索”，进而同时确定“局

部最好”的前进方向及长度。接着用某一评价函数来决定是否接受该

位移以及确定下一次迭代的信赖域。如果试探步较好，下一步信赖域

扩大或保持不变，否则减小信赖域。在迭代过程中不断利用二次函数

模型对目标函数进行逐步逼近。

6

信赖域算法特点：

1这种方法既具有牛顿法的快速局部收敛性，又具有理想的全局

收敛性;

2不要求目标函数的Hes阵是正定的;

3利用了二次模型来求修正步长，使得目标函数的下降比线性搜

索方法更有效。

1折线法：

折线法思想：用低维空间内满足一定要求的折线，代替最优曲线。

单折线法：

连接Cauchy点和牛顿点，其连线与信赖域的边界的交点即为子

模型的近似解。

双折线法：

原理：若信赖域迭代产生的点一开始就偏向牛顿方向，能够改善

算法性能。于是把Cauchy点和牛顿方向上的Nˆ点连接起来，这条连

线与信赖域边界的交点即为子模型的近似最优解。

2.9非线性最小二乘

非线性最小二乘法包括Gauss-Newton法Levenberg-Marquardt法。

Gauss-Newton法

基本思想：Gauss-Newton法也可以看成是对目标函数线性化得到的。

Gauss-Newton法的优缺点：

1对于不是很严重的大残量问题，有较慢的收敛速度。对于残量很大

的问题，算法不收敛。对于小残量问题，具有较快的局部收敛速度。

对于零残量问题，具有局部二阶收敛速度；

2如果雅克比矩阵不满秩，方法没有定义；算法不一定总体收敛。

3对于线性最小二乘问题，一步达到极小值点。

Levenberg-Marquardt法：

Gauss-Newton法在迭代过程中要求雅克比矩阵列满秩以保证搜

索方向为下降方向，限制了其应用。L-M法则通过优化模型来获取下

7

降方向。

3约束优化

3.1罚函数法

借助罚函数将约束非线性规划转化为一系列无约束问题，通过求

解无约束问题来求解约束非线性规划。

外点法：

对违反约束的点在目标函数中加入相应的惩罚，可行点不予惩罚，

这种方法的迭代点一般在可行域D的外部移动。

内点法：

对从内部企图穿越可行域D边界的点在目标函数中加入障碍，

距边界越近，障碍越大，在边界上给予无穷大的障碍，从而保证迭代

点一直在可行域内部移动。

1内点法要求迭代点在可行域内部移动，初始点必须是内点，可

行域的内部必须是非空的，内点法只能处理不等式约束。

2惩罚函数的有效区域是约束的可行域，目标函数在可行域内的

所有点都受到惩罚，越靠近边界惩罚越多。

3不同的惩罚因子对应不同的惩罚函数，惩罚因子越小，惩罚函

数的极小点越接近于边界处的最优点。

4当惩罚因子趋近与零时，惩罚函数的极小点就是原约束问题的

最优点。

混合法：

外点法适用于求解一般约束问题，且初始值任意选取但求解结果

常为不可行解，内点法适于解仅含不等式约束问题，并且每次迭代的

点都是可行点。但要求初始点为可行域的内点，需要浪费相当的工作

量，将外点法和内点法结合，两种惩罚函数联合使用。

外点罚函数的特点：

1初始点可以任选，对等式约束和不等式约束均可适用；

2初始罚因子要选择得当，否则会影响迭代计算的正常进行；

3每个近似解往往不是可行解，这是某些实际问题所无法接受的；

8

4外点法中要求罚因子趋于无穷大，而罚因子太大将造成增广目

标函数的Hes阵条件数越大，趋于病态，给无约束问题求解增加很

大困难，甚至无法求解。

5如果在可行域外目标函数f(x)的性质复杂或者没有定义时，外

点法不适用了。

内点罚函数法的几点说明：

1使用内点法时，初始点应选择一个离约束边界较远的可行点。

如果太靠近某一约束边界，求解无约束优化问题时可能会发生困难。

2惩罚因子的初值应适当，否则会影响迭代计算的正常进行。

3为求解约束优化问题，需要求解一系列的无约束优化问题，计

算量大，且罚因子的选取方法对收敛速度的影响比较大。并且罚因子

的增大（外点法）与缩小（内点法）使得问题的求解变得很困难。常

常会使增广目标函数趋于病态。

3.2乘子法

1 Hestenes法

Hestenes乘子法相当于对拉格朗日函数进行外点惩罚。结论：将

等式约束优化问题转化为增广拉格朗日函数求解问题（无约束优化问

题），乘子法不需过分地增大惩罚因子，确实比外点法有效很多。

2 Powell法

3 Rockafellar法

Rockafellar在1973年将乘子法推广到不等式约束优化问题，其

思想是引入松弛变量，将不等式约束转化为等式约束。此乘子法比外

点法收敛速度快很多。

3.3二次逼近法

对于较为复杂的非线性问题，一种很自然的想法：将问题的约束

和目标函数通过泰勒展式线性化(二次规划时，目标函数的拉格朗日

函数展开为二次逼近函数)。数值实验表明，二次逼近法具有很好的

计算效率。

9

有效集法：

等式约束下的二次规划问题有很多求解方法，如消去法、QR分

解法等。上述求解方程组对病态方程组求解会遇到一定困难。

有效集法：只要能够找到最优解对应的有效集，就可以通过求解

等式约束下的二次规划问题得到最优解。从二次规划问题的一个子问

题出发，求出对应的有效集，然后按照使目标函数减少的原则，对有

效集不断调整，直到迭代到最优解对应的有效集为止。

3.4可行方向法

基本思想：从可行点出发，沿着下降的可行方向进行搜索，求出

使目标函数值下降的新的可行点，直到满足终止条件，得到最优解

x*。

可行方向法的核心是选择可行下降搜索方向和确定搜索步长。搜

索方向的选择方式不同就形成不同的可行方向法。如Frank Wolfe方

法、梯度投影法、既约梯度法。

梯度投影法：

基本思想: 当迭代点在可行域内部时，取该点处的负梯度方向为

可行下降方向；当迭代点在可行域边界上时，取该点处负梯度方向在

可行域边界上的投影产生一个可行下降方向．

目标函数的最速下降方向是负梯度方向．但是，在有约束情况下，

沿最速下降方向移动可能导致非可行点．对负梯度进行投影，使得目

标函数值不仅改进，同时又保持迭代点的可行性．

既约梯度法:

基本思想：借鉴求解线性规划的单纯形算法，选择某些变量为基

变量，其它的作为非基变量，将基变量用非基变量表示，并从目标函

数中消去基变量，得到以非基变量为自变量的简化的目标函数，进而

利用此函数的负梯度构造下降可行方向。

Frank Wolfe方法:

算法思想：在每次迭代中,将目标函数线性化，通过求解线性规

划方法求得可行下降方向,并沿该方向在可行域内进行一维搜索。

10