数据科学优化方法 课件 第2章 无约束最优化方法基础

数据科学优化方法Optimization

Method

in

Data

Science数据科学与大数据技术第2章

无约束最优化方法基础2.1最优性条件2.2方法框架2.3收敛准则最优性条件2.1.1全局最优解与局部最优解2.1.2最优性条件最优性条件2.1.1全局最优解与局部最优解2.1.2最优性条件若对任意，有

，则称

为问题(1.1)的全局最优解.定义2.1全局最优解全局最优解与局部最优解若存在的一个邻域，使得对任意，有，则称

为问题(1.1)的局部最优解（也称为弱局部最优解）.其中，是一个小的正数；范数可以是任意向量范数，如无特别说明，一般指2范数定义2.2局部最优解全局最优解与局部最优解全局最优解与局部最优解若存在的一个邻域,在该邻域内有且仅有

这一个局部最优解，则称

为问题(1.1)的孤立局部最优解.定义2.4孤立局部最优解若存在的一个邻域,使得对任意有，则称

为问题(1.1)的严格局部最优解（也称为强局部最优解）.定义2.3严格局部最优解注：孤立局部最优解一定是严格局部最优解，而严格局部最优解未必是孤立局部最优解.注：相较于弱局部最优解，严格局部最优解能在其领域内达到绝对最优.全局最优解与局部最优解例:

如图2.1，目标函数，问题(1.1)有严格局部最优解，但它附近还有无穷个不同的局部最优解，且，所以并不是孤立局部最优解.图2.1

其中

是严格局部最优解同时也是孤立局部最优解，而

是非严格局部最优解.全局最优解与局部最优解图2.2局部最优解：全局最优解：例:

考虑图2.2所示的目标函数全局最优解与局部最优解许多优化问题有多个局部最优解，而优化方法在迭代过程中常常会陷入局部最优解，因此求全局最优解通常是一个极为困难的问题。本课程介绍的方法一般只能用于确定最优化问题的局部最优解，有关确定全局最优解的优化方法属于最优化研究的另一个重要领域——全局最优化。若最优化问题（1.1）的目标函数是凸函数，则问题的每个局部最优解都是全局最优解。2.1最优性条件2.1.1全局最优解与局部最优解2.1.2最优性条件最优性条件根据局部最优解的定义，可以通过计算目标函数在领域内所有点上的取值情况，判断是否为局部最优解当函数二阶连续可微时，可以借助目标函数在处的梯度以及Hesse矩阵判断是否为局部最优解本节给出判断局部最优解的必要条件和充分条件最优性条件若为问题(1.1)的局部最优解，且目标函数在一个开邻域内连续可微，则定理2.1一阶必要条件满足的点称为稳定点.问题(1.1)的任何一个局部最优解一定是目标函数

的稳定点，但反之不一定成立.（即不是局部最优解的充分条件）例：考虑问题是稳定点，但不是该问题的局部最优解.注：最优性条件证明：用反证法.假设定义向量于是由于在

的一个开邻域内连续，故存在常数，使得由中值定理知，对任意存在

使得因此

这与局部最优解的定义矛盾，于是假设错误，由此推出最优性条件若为问题(1.1)的局部最优解，在

的一个开邻域内存在且连续，则且半正定.定理2.2二阶必要条件注：二阶必要条件并不充分，即一个点

满足二阶必要条件，但它可能不是问题(1.1)的最优解。例：考虑问题在处有

，满足二阶必要条件，但不是该问题的局部最优解.最优性条件证明：由定理2.1知接下来用反证法证明半正定.假设不是半正定，于是可以找到一个向量

，使得

因为在

的一个开邻域内连续，故存在常数，对任意

都有

由在

处的泰勒展式及定理2.1知，对任意存在

使得这与是

的局部最优解矛盾，所以假设不成立，由此推出半正定.最优性条件设

在

的一个开邻域内连续，若

正定，则

为问题(1.1)的严格局部最优解.

定理2.3二阶充分条件注：二阶充分条件不是必要条件，即一个严格局部最优解

可能并不满足二阶充分条件.例：考虑问题

是该问题的严格局部最优解，但，故不满足二阶充分条件.最优性条件证明：由于在点

处连续且正定，故可选择

，使得对于任意均有是正定的.对于任意满足

的非零向量,显然有由泰勒展式及有其中因为故

因此即

是

的严格局部最优解.最优性条件设

是凸函数，则问题(1.1)的局部最优解

也是全局最优解；若

还是可微函数，则任何稳定点

都是问题(1.1)的全局最优解.

定理2.4最优性条件证明：先用反证法证明第一部分.假设

是问题(1.1)的局部最优解，但非全局最优解.于是，我们可以找到一个点满足令

为

与

的线性组合，即由函数

的凸性，有因为的任一邻域

都包含线段(2.1)的一部分，故总存在点

使得这与

为局部最优解相矛盾，所以假设不成立，故

是问题(1.1)的全局最优解.(2.1)最优性条件接下来证明第二部分.再次使用反证法，假设

不是全局最优解，类似于前面过程，我们可以找到满足由函数

的凸性，有可知这与

为稳定点相矛盾，所以假设不成立，故

是问题(1.1)的全局最优解.最优性条件本课程关注的目标函数大多为光滑函数，对于非光滑甚至非连续的目标函数，一般情况下很难找到它的最优解.若目标函数是由几段光滑的曲线连接而成，不同曲线之间并不连续，则可以通过最优化目标函数在各光滑曲线上的取值，获得最优解.若目标函数处处连续，仅在个别点不可微，则在这些不可微点，可以根据次梯度判定其是否为最优解.最优性条件例2.1考虑问题证明为该问题的全局最优解.最优性条件在处，正定，因此

是问题的局部最优解.因为函数

是凸函数，故

是该问题的全局最优解.解：第2章

无约束最优化方法基础2.1最优性条件2.2方法框架2.3收敛准则方法框架求解最优化问题一般不太可能给出问题的最优解的解析表达式一般采用迭代方法求解给定最优解的一个初始估计方法产生一个逐步改善的估计序列直到满足收敛准则迭代方法基本思想方法框架在后面章节中，将介绍无约束最优化问题的一些具体求解方法.所有这些方法均需要使用者提供初始点

，以便进行迭代.随着迭代的进行，可以得到一个有限或无限的迭代序列

当满足给定的某个终止准则时，或者表明以满足要求的最优求解近似精度，或者表明方法已无法进一步改善迭代点时，迭代结束.方法框架算法2.1:无约束最优化方法的基本结构1给定初始点

，k:=0；2若在点

处满足终止准则，则停止迭代，输出有关信息；3确定一个改善

的修正量

；4得到最优解的一个新估计

k:=k+1，转至步骤2.涉及问题：迭代终止准则的确定修正量

的确定：线搜索方法和信赖域方法初始点的选取：依赖于方法的收敛性方法框架迭代终止准则(2.2)不同优化方法迭代终止准则不同.根据最优性的一阶必要条件,可用其中，是给定的精度要求.局限性依赖于目标函数在最优解邻域内的性质.方法框架例：如图2.3，目标函数为，点和点是问题的两个局部最优解，点和点分别在和的领域内.图2.3虽然点离还有一段距离，但由于目标函数在这个领域内较为平坦，在点处的梯度（即导数）值已经很小，故迭代容易停止.对于点，虽然它已相当接近最优解，但由于目标函数在这个领域内比较陡峭，在点处的梯度值依然较大，从而迭代难以停止.方法框架迭代终止准则理想的终止准则：由于

未知，这样的准则并不具有任何实用价值.实际应用中常用的终止准则(2.3)(2.4)注：准则(2.3)或(2.4)满足只能说明算法目前的迭代过程对迭代点或迭代点处目标函数值的改善已经很小，并不能保证

或亦足够小.当和，采用方法框架迭代终止准则同时采用终止准则(2.3),(2.4)：否则采用：方法框架确定修正量在完成第k步迭代后，优化方法需要根据目标函数在当前迭代点处的取值，甚至包括前面所有迭代点

处的信息来计算修正量，进而确定下一步的迭代点.修正量的确定是优化方法中最关键和最主要的工作，主要有两种策略：线搜索方法和信赖域方法.方法框架2.2.1线搜索方法2.2.2信赖域方法其中，是搜索方向，是沿的步长.线搜索方法修正量：线搜索方法：先确定搜索方向，再确定步长，使得目标函数值达到最小，即通过求解一维优化问题：可以得到精确步长.注：精确步长的计算需要很大的计算量，可以采用简单高效的方法求出一个非精确步长（第3章讨论）.线搜索方法搜索方向的重要准则：该方向能够使目标函数值下降.设是经k步迭代后得到的迭代点，是搜索方向，是步长，第k+1个迭代点为

满足当与的夹角大于，有线搜索方法根据泰勒定理，有由此，对于充分小的步长，有称满足(2.5)的搜索方向

为

在

点的下降方向.常用下降方向：负梯度方向、牛顿方向、拟牛顿方向、共轭梯度方向等.(2.5)满足什么条件的搜索方向是在点

处使下降的方向呢？线搜索方法算法2.2:

线搜索方法的基本结构1给定初始点

2若在点

处终止准则满足，则停止迭代，输出有关信息；3确定

在

点处的下降方向

；4确定步长

，使

较之

有一定下降；5转至步骤2.线搜索方法例：图2.4是线搜索方法的迭代过程.目标函数：最优解：最优值：0初始点：图2.4

线搜索过程方法框架2.2.1线搜索方法2.2.2信赖域方法信赖域方法线搜索方法：先在点处求得下降方向

，再沿

确定步长.信赖域方法：先限定步长的范围，再同时确定下降方向

和步长.确定修正量的两种策略定义一个包含

的邻域，假设在这个邻域内，模型

是

的一个合适的近似，称该邻域

为信赖域，

为信赖域半径.信赖域方法：在当前迭代点，信赖域方法构造目标函数的一个近似模型

，该模型在点

附近的取值与目标函数

相近。信赖域方法信赖域方法通常将近似模型

设为二次函数形式其中，矩阵

是一个对称矩阵，它是Hesse矩阵

或其近似矩阵.(2.7)信赖域方法通过在信赖域内求解子问题得到近似极小点，并取，其中(2.6)信赖域方法每一步迭代时，需提前设置信赖域的大小（即），然后在该信赖域内求解.太小，则导致步长过短，从而影响算法的收敛速度.过大，则无法保证是的好的近似函数，直接求解子问题（2.6），可能会出现的极小点与目标函数的极小点相距甚远的情况.因此，需要每步迭代时都在点处选择一个合适的信赖域方法选择合适的：根据模型函数对目标函数的近似程度来调整信赖域半径假设在点

处，在半径

的信赖域内最小化子问题(2.6)得到实际下降量：预测下降量：，注意定义比值：

的大小反映了近似的程度当

接近于1，表明近似的程度好，下一步迭代可适当增大

如果但不接近于1，则保持

不变如果

为接近于零的正数，表明近似的程度不好，下一步迭代应减小

当，因为

是子问题(2.6)的解，故当，表明，即目标函数值出现了上升，故不应被接受为下一步迭代点，这时只得减小信赖域半径

，重新求解子问题(2.6)信赖域方法信赖域方法算法2.3:信赖域方法的基本结构1给定初始点

，初始信赖域半径

，

;2若满足终止准则，则停止迭代，输出有关信息;3（近似）求解子问题(2.6)得到

；4计算.

若

，则

；否则

;5修正信赖域半径:若

，则缩小信赖域半径

若

且

，则适当增大信赖域半径，

否则

;6更新近似模型，

，转至步骤2.注：该方法对其中的1/4，3/4

等常数不敏感，

可取为1或信赖域方法线搜索方法：先在点处求得下降方向

，再沿

确定步长.信赖域方法：首先在当前迭代点

处定义一个邻域，在该邻域内通过最小化目标函数的一个近似模型获得搜索方向和步长，搜索方向和步长同时被确定.如果信赖域过大，则缩小信赖域，搜索方向和步长会同时改变.总结：信赖域方法图2.5

线搜索方法和信赖域方法的搜索过程例：如图2.5，在同一个迭代点处，两种方法产生出不同搜索方向，其中信赖域方法产生的搜索方向使目标函数值出现更大下降.第2章

无约束最优化方法基础2.1最优性条件2.2方法框架2.3收敛准则收敛准则2.3.1收敛性2.3.2收敛速度收敛性如果方法产生的迭代序列

在某种范数意义下满足则称这个算法是收敛的.全局收敛：对于任意给定的初始点，方法都能够收敛.局部收敛：只有当初始点充分接近最优解时才能够收敛.注：对于全局收敛方法，初始点的选择可以没有任何限制；而对于局部收敛方法，则需要在最优解附近选取初始点，才能保证方法收敛.2.3收敛准则2.3.1收敛性2.3.2收敛速度若存在常数使得对于所有足够大的k，有则称该方法是Q-线性收敛的.收敛速度定义2.5Q-线性收敛收敛速度的快慢是评价方法优劣的一个重要标准.设方法产生的迭代序列

收敛到.注：Q是英文单词quotient(商)的首字母Q-线性收敛说明当迭代充分多步后，每迭代一步，迭代点

与

的距离会缩减至少一个常数倍例：序列