上一章传送门：

本章将讨论无约束静态最优问题

(3.1) 

以及导出必要的足够的最优条件。之后会介绍一些知名的数值优化方法，使读者对数值优化产生基本印象。

3.1 必要最优条件

对无约束问题的最优条件，一方面要找到(局部的)极值  也要对其检验，保证极值为足够小的领域里的(定义2.1)最小值(Minimum)

(3.2) 

基于  至少二次连续可微，可进行泰勒展开

(3.3) 

若  取到局部最小，那么  对所有足够小的  都可满足(3.2)条件。代入(3.4) 

对于足够小  的来说，一阶项主导，也决定了不等式左边的符号，这要求 。而  取到局部最小，则不等式对所有足够小邻域内  成立

(3.5) 

条件(3.5)也对最大值(Maximum)或者鞍点(Sattelpunkt)满足，如下图所示。不过一般语境下的最优化指的是稳定点。

对局部最小的更严格的二阶条件则进一步确保(3.3)的成立，即

(3.6) 

其对足够小的  覆盖的邻域成立，则必须保证Hesse矩阵至少半正定。

定理3.1 必要最优条件：若  是二次连续可微且  取到  局部最小，则有必要的一二阶最优条件
(3.7)  
(3.8) 

不过该定理也不是足够最优条件，也不可逆。有反例如，  易知它满足条件，却在  处只能取到鞍点，而非最小值。

3.2 足够的最优条件

为了确保局部最小的存在，当一阶项已经为0后，使二阶项严格为正方能保证符号。

定理3.2 足够的最优条件：若  是二次连续可微且  取到  局部最小，则有必要的一二阶最优条件
(3.9)  
(3.10) 

从中可以看出，严格最小的  不会自动导出  的正定性。例如，  ，易知它在  处取到最小值，但其二阶导数在此为零，非正定。

一阶最优条件  ，用于求可解的n阶方程的非线性系统的稳定点  。再利用二阶最优条件检验  以确保严格最小。

例3.1 对于最优问题

(3.11) 

所以参数  会影响函数稳定点，其梯度向量和Hesse矩阵为

(3.12) 

由一阶条件得到稳定点  ，其作为  时唯一的稳定点。用顺序主子式判断正定性有  。所以若  有严格最小；反之，  时，  矩阵定性不确定；  则为鞍点，其函数形状如上图3.1右图所示。

如果代价函数  (严格)凸，那么最优断言更强力。

定理3.3 凸函数足够的最优条件：若  是二次连续可微且(严格)凸，若，那么  取到  (唯一)全局最小。

3.3 用线搜索的数值解

因为稳定条件只有很少的情况可以解析表达，大部分情况下都是数值方法来找到稳定点  。其中最有名的就是线搜索(Liniensuchverfahren)。从次优的起始解  出发，不断迭代逼近最小值，例如会经历  次迭代，都有出现

(3.13) 

那么当  ，迭代值会收敛于最小值  。线搜索的策略就是确定一个搜索方向(梯度下降方向)  ，沿着这个搜索方向向量都有不等式条件保证。用泰勒展开分析

(3.14) 

对于足够小的搜索方向  可以忽略剩下的高阶项，不过应该满足

(3.15) 

这样可以保证  。有很多方法可以确定搜索方向，之后会一一介绍。此外必须确定合适的步长  以此确定下一步位置有多远

(3.16) 

最优的步长也就是从属的最优问题的解

(3.17) 

也对应最大可能下降的搜索方向  。不过总的来说(3.1)不能精确解出，只能借助合适方法近似，下图展示了对一个非凸代价函数在  上给定搜索方向  的线搜索的原理。基本的算法以伪代码形式给出。

3.3.1 确定步长

一个适合的步长涉及计算时长和精度的妥协。它的最优解在于标量最优问题精确或者至少足够精确解出，在实际中依然还有很多对代价函数的估计，有些甚至需要梯度。常见的数值方法使用次优线搜索来确定步长  ，这样可以相适应地减少下一步的代价函数  用的状态  。一些基本的方法为：

• 曲率下降条件
• Back Tracing法
• 区间套法

曲率下降条件(Wolfe条件)

偶尔下降条件(Abstiegsbedingung)也被称为Armijio条件。而一个足够快下降的判别标准取决于不等式

(3.18) 

这个新的以  为自变量的函数表示就取决于新的参数  。形象地说，不等式左侧是原本的函数值，而右侧等价于和左侧共起点，  的下降速度与步长成比例，并且应该恰为方向导数  的一条直线。

不等式右侧表示一个负斜率的直线下降  ，而由于  ，只有对足够小的 会使直线高过函数值  。有了下降条件会要求，仅当函数值  在这条直线之下，才有许用的  。实操时常选很小的参数比如  。这样下降条件不会太严格。

为保证值得一提的  下降量，单独只有下降条件往往还不够，因为足够小步长  一直满足这个条件。太小的步长也可以通过第二条判据再加约束。

(3.19) 

也就是曲率条件(Krümmungsbedingung)。而参数 与 相关。因为曲率条件左侧为梯度  ，这表示从  出发的梯度下降量应当小于等于  倍的从起始点出发的梯度下降  。两个不等于约束即能确定合适的步长范围。

总的来说，曲率判别法还是有意义的，在很快速的下降  的假设下，  依然能减少，只要沿着  轴前行。另一方面，也通过约束条件避免  太大以至于偏离  的最小值太远。

曲率条件和下降条件合并统称为Wolfe条件，可以广泛应用。常见选择是  ，若采用了Newton法或者Quasi-Newton法来确定的搜索向量  ；或  ，若采用共轭梯度法。需要指出的是，一个连续可微且从下约束的函数总是存在满足Wolfe条件区间。

Back Tracing法

就如已经提到的，为保证代价函数足够快下降，单独的下降条件是不够的。若有候选步长  ，那么也可以不用曲率条件，直接只使用下降条件。Back Tracing法即可选出合适候选步长。而它的过程也可以用图3.3来解释。

若初始值  落在很远的右侧，那么  通过因数  来缩减，直到满足 位于直线之下(通常  取到0.1或者0.25)。因数  持续的减少  确保最终输出的步长  足够小。而这样也能确保迭代之后的  不会太小，最终会下降到一个平台阶段。

Back Tracing法往往结合Newton法并且令初始步长  ，而对于Quasi-Newton法或共轭梯度法而言，则稍逊风骚。

区间套法

另一个备选方法是区间套法，通过区间套的不断的收敛序列来夹逼最小值  。

首先需要先确定一个区间  ，该区间包含最小值，如图3.5。若从一个极小的  开始，并让  持续变大，直到函数值  开始增大。

之后选取估计值  通过线性关系

(3.20) 

参数一般选在  。算出函数值  ，若  ，那么显然最小值处于  ，点  可以舍去；反之，若  ，则获得区间 舍去  。下一步迭代就在这个新的缩短的区间  (  )内进行。

参数  选成黄金比，可以确保区间宽度在每次迭代中以相同的恒定比例缩小，因此也叫黄金比例搜索。每次迭代可以减小大约38%的区间宽度。最终输出步长为  或者用三四个最小的函数值对应的  平方插值获得。区间套法十分简单鲁棒，但是相对来说，计算步数明显多于其他方法。

参考文献：

Numerische Optimierung und modellprädiktive Regelung (WS 2019/2020), A. Völz, K. Graichen, Lehrstuhl für Regelungstechnik, Friedrich-Alexander-Universität Erlangen-Nürnberg