数据科学优化方法 课件全套 孙怡帆 第1-12章 导论、无约束最优化方法基础-交替方向乘子方法+附录A 数学基础

数据科学优化方法Optimization

Method

in

Data

Science数据科学与大数据技术第1章导论1.1最优化问题简介1.2本课程考虑的最优化问题

1.3优化方法的特点和要求1.4本课程的主要内容第1章导论1.1最优化问题简介1.2本课程考虑的最优化问题

1.3优化方法的特点和要求1.4本课程的主要内容最优化问题简介最优化问题：在限制条件下最大或最小化一个函数的问题.最优化问题简介优化方法：寻求某些变量（因素）的值，使得目标函数达到最优.在某些情况下，变量的取值可能受到限制或约束.最优化问题简介日常工作项目投资最优化问题简介统计和机器学习最优化最优化问题简介机器学习=表示+优化+评估—AAAI会士、华盛顿大学Domingos教授最优化问题简介统计和机器学习最优化第1章导论1.1最优化问题简介1.2本课程考虑的最优化问题

1.3优化方法的特点和要求1.4本课程的主要内容本课程考虑的最优化问题2112无约束最优化问题约束最优化问题3复合最优化问题求极小：无约束最优化问题无约束最优化问题：求一个函数的极值（极小或极大）问题为变量或参数，为目标函数求极大：求极小：等价（1.1）求解：找到一个解，使目标函数

达到极小.

称为最优解，

称为最优值.例1.1（线性回归）给定m个样本，其中

表示第i个样本的特征，表达为一个列向量，表示第i个样本的预测值。我们希望从训练数据中学习一组参数x，使得尽可能拟合训练数据.假设采用平方经验损失函数，用什么优化模型来学习参数x

？无约束最优化问题无约束最优化问题优化模型（1.2）解：损失函数越小，模型对训练数据的拟合效果越好.因此，给定一个线性回归模型，我们可以通过“优化”找到一组好的参数x

.约束最优化问题约束最优化问题：变量受到某些条件限制时，求函数极值问题(1.3)最优化问题的一般形式：为约束函数.为等式约束；为不等式约束.（注：可转换为）均为光滑函数，和

分别是等式约束和不等式约束的指标集.s.t.是subjectto的缩写，意为“满足”“受约束”.约束最优化问题例1.2将下列约束最优化问题转化为(1.3)的最优化问题的一般形式(1.4)约束最优化问题解：令则问题(1.4)可转化为问题(1.3)的形式.约束最优化问题例1.3（矩阵填充）矩阵填充问题在机器学习和信号处理领域中有广泛应用，该问题可以写成约束最优化问题形式：其中表示矩阵的核范数，即矩阵特征值的和，表示矩阵所有被观测到的元素的位置的集合.由此，可通过求解(1.5)找到一个满足观测约束且低秩的矩阵.(1.5)复合最优化问题复合最优化问题形式：(1.6)其中，

是一个光滑函数，是正则项，通常为一个非光滑函数，是正则化参数.在监督学习中，通常对应于一个经验损失函数，如：平方损失函数，逻辑斯蒂（Logistic）损失函数，交叉熵损失函数.正则项

的常见例子包括

正则项和

正则项复合最优化问题例1.4(Lasso)正则化线性回归（亦称为Lasso回归）是机器学习领域涉及的最简单且常用的复合最优化问题.该正则最优化问题在无约束最优化问题(1.2)的基础上增加了一个

正则项：由于可以将参数

的部分分量“压缩”到0，即稀疏化，因此，可以通过求解复合最优化问题(1.7)找到一个既能较好拟合数据且相对稀疏的参数.(1.7)第1章导论1.1最优化问题简介1.2本课程考虑的最优化问题

1.3优化方法的特点和要求1.4本课程的主要内容优化方法的特点和要求一般不太可能给出问题的最优解的解析表达式一般采用迭代方法求解优化方法的特点和要求给定最优解的一个初始估计优化方法产生一个逐步改善的估计序列直到满足收敛准则迭代方法基本思想优化方法的特点和要求不同的优化方法采用不同的迭代策略.绝大多数迭代策略会用到目标函数值、约束条件以及目标函数的一阶导数甚至二阶导数的信息.一些优化方法只需要当前迭代点的局部信息，而另一些优化方法则需要积累已有的迭代信息.优化方法的特点和要求优化方法的性质稳健性：在任意一个合理初始值条件下，都应该能在一大类问题而非个别问题中表现良好.有效性：要使用尽量少的计算时间和计算空间.精确性：应该是数值稳定的，即求出的解不会对数据误差或计算过程中的舍入误差高度敏感.注：上述三个性质可能是相互矛盾的数值最优化的核心问题：收敛速度与计算空间、收敛速度与稳健性之间的平衡.第1章导论1.1最优化问题简介1.2本课程考虑的最优化问题

1.3优化方法的特点和要求1.4本课程的主要内容本课程的主要内容非线性最优化问题及方法第一部分（2-7章）讨论无约束最优化问题的基本理论与基本方法

2-3章讨论无约束最优化方法的基本概念及基本结构

4-7章讨论无约束最优化问题的四类求解方法第二部分（8-9章）讨论约束最优化问题的最优性条件及求解方法第三部分（10-12章）讨论复合最优化问题及其三类求解方法数据科学优化方法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-线性收敛说明当迭代充分多步后，每迭代一步，迭代点

与

的距离会缩减至少一个常数倍例：序列Q-线性收敛到0。收敛速度若

则称该方法是Q-次线性收敛的.定义2.6Q-次线性收敛例：序列Q-次线性收敛到0.注：Q-线性收敛快于Q-次线性收敛的.收敛速度若

则称该方法是Q-超线性收敛的.定义2.7Q-超线性收敛例：序列Q-超线性收敛到2.注：任何一个Q-超线性收敛序列也是Q-线性收敛的.收敛速度若存在正数M，对于足够大的k，有则称该方法是Q-平方收敛（也称为Q-二阶收敛）的.定义2.8Q-平方收敛例：序列Q-平方收敛到1.注：任何一个Q-平方收敛序列也是Q-超线性收敛的.一般来说，具有Q超线性收敛速度和Q-平方收敛速度的方法收敛速度是较快的.为了简便，提到收敛速度时常略去Q，直接称收敛速度为线性、次线性、超线性、二阶等.收敛速度例2.2假设有两个具有不同收敛速度的方法.当迭代次数k充分大时，方法一产生的迭代序列

具有线性收敛速度，满足算法二产生的迭代序列

具有平方收敛速度，满足假设在当前迭代点

处，两个方法均满足请问：若要达到

的精度，方法一和方法二各需进行多少次迭代？收敛速度解：根据线性收敛定义,由

得到，故方法一需要再进行13次迭代.类似地，由平方收敛的定义，有可知方法二只需再进行2次迭代即可达到要求的精度.收敛速度注：收敛性和收敛速度均是理论结果，一种方法有好的理论收敛性和收敛速度，并不能保证有好的实际运算结果.考虑到舍入误差会对计算过程产生影响，应该在理论分析的基础上，对方法进行数值实验.数据科学优化方法Optimization

Method

in

Data

Science数据科学与大数据技术第3章线搜索方法3.1精确线搜索方法3.2精确线搜索方法的收敛性3.3非精确线搜索方法3.4非精确线搜索方法的收敛性引入基本思想：在每次迭代时，先依据当前信息求得迭代方向，然后沿确定步长.线搜索方法的优劣与搜索方向和步长的选取密切相关.212迭代方向：一般是下降方向，即目标函数值沿着方向有所下降（）步长：精确线搜索和非精确线搜索引入？如何基于当前迭代点和下降方向确定步长？步长需满足的一些基本准则？第3章线搜索方法3.1精确线搜索方法3.2精确线搜索方法的收敛性3.3非精确线搜索方法3.4非精确线搜索方法的收敛性迭代点

，当迭代方向

已知时，使目标函数

沿方向达到极小，即这样的线搜索方法称为精确线搜索，所得到的

称为精确步长因子.精确线搜索方法（3.1）满足注：很多情况下，问题(3.1)没有解析解，需要通过迭代方法求数值解.精确线搜索方法的两个阶段1.第一阶段确定包含精确步长的初始搜索区间2.第二阶段采用某种分割或插值技术缩小这个区间，直到区间长度达到给定精度精确线搜索方法3.1.1确定初始搜索区间3.1.2分割方法3.1.3插值方法基本思想：从一个点出发，按一定步长，试图确定出目标函数呈现“高—低—高”的形状.确定初始搜索区间进退法确定初始搜索区间分析：给定初始点初始步长若则下一步从出发，加大步长，继续向前搜索，直到目标函数上升为止.若则下一步仍以

为出发点，沿反方向搜索，直到目标函数上升为止.无论是向前搜索还是向后搜索，最后可得使得确定初始搜索区间算法3.1:进退法求初始搜索区间1给定初始点

初始步长

加倍系数2比较目标函数值.

令

若

则转至步骤3，否则转至步骤4.3加大搜索步长.

令

转至步骤2.4反向搜索.

若

则转换搜索方向，令

转至步骤2；否则停止迭代，令

输出利用的导数确定初始搜索区间:包含真实极小点的区间端点处，给定步长取初始点若则取若则取其余过程与前述方法类似.确定初始搜索区间分割方法二分法黄金分割法Fibonacci法插值方法一点二次插值法两点二次插值法三点二次插值法三次插值法常用的精确线搜索方法3.1精确线搜索方法3.1.1确定初始搜索区间3.1.2分割方法3.1.3插值方法设函数若存在使

在上单调下降，在上单调上升，则称

是区间上的单峰函数，称为的单峰区间.分割方法定义3.1单峰函数二分法、黄金分割法、Fibonacci法都是分割方法，不同之处在于区间的分割方式.这些方法均要求目标函数是单峰函数.注：单峰函数具有“高—低—高”形状，存在唯一的局部极小点.分割方法图3.1为一个单峰函数的图象目标函数不是单峰函数时，把所考虑的区间划分为若干小区间，在每个小区间上函数是单峰的.在每个小区间上求极小点，选取其中的最小点，得到最终步长.图3.1单峰函数分割方法3.1.2.1二分法3.1.2.2黄金分割法3.1.2.3

Fibonacci法二分法基本思想：二分法通过计算目标函数在区间端点的导数值来不断将区间一分为二，直至区间长度足够小，区间中的点均接近极小点为止.二分法算法3.2:二分法的计算步骤1.给定初始区间2.计算3.若

是最优解，停止迭代;若

则

转至步骤4;若

则

转至步骤4.4.如果

则停止迭代，输出

；否则

转至步骤2.二分法算法3.2:二分法的计算步骤1.给定初始区间2.计算3.若

是最优解，停止迭代;若

则

转至步骤4;若

则

转至步骤4.4.如果

则停止迭代，输出

；否则

转至步骤2.二分法算法3.2:二分法的计算步骤1.给定初始区间2.计算3.若

是最优解，停止迭代;若

则

转至步骤4;若

则

转至步骤4.4.如果

则停止迭代，输出

；否则

转至步骤2.二分法收敛速度：二分法每次搜索时将搜索区间长度缩短一半，收敛速度是线性的，收敛比为1/2.

若要求最后的区间长度不超过，则迭代次数n需满足二分法用到了的一阶导数值，后面介绍的黄金分割法和Fibonacci法没有用到任何导数信息，只根据的大小对区间进行压缩.分割方法3.1.2.1二分法3.1.2.2黄金分割法3.1.2.3

Fibonacci法黄金分割法基本思想在初始区间

上选取两个对称点

和，通过比较

和

的大小决定要删除的区间：若，则删除右半区间，否则，删除左半区间.剩余区间作为下一步迭代的新区间，新区间的长度为原区间长度的0.618倍.新区间包含原区间中两个对称点中的一点，只需再选一个对称点，比较这两个新对称点处的目标函数值.重复这个过程，最后确定出极小点.黄金分割法分析：设是区间

上的单峰函数，令设区间经i

次缩短后变为.在中选两个对称点和，满足:第一个等号表明和为区间上的两个对称点，第二个等号表明新区间为原区间长度的倍。由此可得：（3.2）（3.3）（3.4）黄金分割法计算在两个对称点的值：若，则取新区间若，则取新区间记下步迭代时选取的两个新对称点为和对比上一步的表达式(3.3)：若令则：故只需计算一个试探点：黄金分割法情形1：假设所选区间为如图3.2，由(3.4),有：图3.2黄金分割法一步迭代

若令则：故只需计算一个试探点：黄金分割法情形2：假设所选区间为由(3.3),有：再比较和，重复上述过程，直到小于给定精度.黄金分割法解方程

可确定区间缩短率.由于

可得：新区间的长度为原区间长度的0.618倍.若要求最后的区间长度不超过

，即由于可知迭代次数n满足：（3.5）黄金分割法算法3.3:黄金分割法1给定初始区间2计算两个试探点计算

若

则转至步骤3，否则转至步骤4.3若

则停止迭代，输出

否则计算

，转至步骤5.4若

则停止迭代，输出

否则计算

，转至步骤5.5转至步骤2.黄金分割法例3.1用黄金分割法求函数

在

上的极小点，最后的区间长度.黄金分割法已知，由(3.5)可以解得即进行4次迭代后，区间长度就不超过.具体迭代过程如下：第一次迭代：计算：因为令更新区间为解：黄金分割法第二次迭代：计算：因为令更新区间为第三次迭代：计算：因为令更新区间为黄金分割法第四次迭代：计算：因为停止迭代。最终区间为[0.7639,0.9098]，将作为函数在[0,1]上极小点的近似估计.3.1.2分割方法3.1.2.1二分法3.1.2.2黄金分割法3.1.2.3

Fibonacci法Fibonacci法基本思想Fibonacci法与黄金分割法类似，主要区别在于搜索区间的缩短率不再采用黄金分割数，而是Fibonacci数列.

对于给定的最后区间长度，Fibonacci法需预先确定迭代次数.注：Fibonacci数列满足：Fibonacci法搜索区间的缩短率Fibonacci法的新搜索区间与原搜索区间的长度具有以下关系：其中n是迭代次数.（3.6）迭代次数n的确定要求经过n次迭代后，最后的区间长度不超过，即从而：对于最后的区间长度

，由(3.7)预先计算出，再根据确定出迭代次数n.（3.7）Fibonacci法按照Fibonacci数列进行区间压缩的问题当进行第n步迭代时，由(3.6)可知，第n步的区间缩短率为：表明在第n步选取的两个试探点恰好在区间中点重合，无法对区间进行下一步压缩.解决方案：给原压缩率

增加一个较小的正数，使得到的新试探点略微向区间中点的左侧或右侧偏移，而上一步选择的试探点则位置保持不变.然后通过比较和的大小进行区间压缩.此时新区间长度可能是上一步区间长度的1/2，也可能是倍.Fibonacci法计算第n步得到的区间长度为上一步区间长度的

倍时所需要的最大迭代次数当进行第n步迭代时，由(3.6)可知，第n步的区间缩短率为则有（3.8）Fibonacci法Fibonacci法与黄金分割法的关系对于给定的以及最后的区间长度，可由(3.8)提前确定最大迭代次数.然后按照黄金分割法不断选取试探点，压缩区间，直至达到最大迭代次数，此时区间长度不超过.可证明：即当时，Fibonacci法与黄金分割法的区间缩短率相同

Fibonacci法是求解一维极小化问题的最优分割方法；黄金分割法是近似最优.Fibonacci法更加高效；黄金分割法的区间缩短率固定，计算简单，应用更加广泛.Fibonacci法Fibonacci法计算步骤1.根据和确定最大迭代次数2.确定搜索区间的缩短率,按照黄金分割法方式不断选取试探点，压缩区间，直到达到最大迭代次数，此时区间长度不超过.Fibonacci法例3.2用Fibonacci法求函数

在

上的极小点，最后的区间长度.已知，由(3.8)可知方法所需的最大迭代次数n满足:当时，进行次迭代后，区间长度就缩小到.具体迭代过程见后.Fibonacci法解：Fibonacci法第一次迭代：计算：因为令更新区间为Fibonacci法第二次迭代：计算：因为令更新区间为Fibonacci法第三次迭代：计算：因为令更新区间为Fibonacci法第四次迭代：令计算：因为故停止迭代.最后区间为[0.75,0.8875]，将作为函数在[0,1]上极小点的近似估计.3.1精确线搜索方法3.1.1确定初始搜索区间3.1.2分割方法3.1.3插值方法插值方法基本思想利用函数在区间内某些点的已知信息，不断地构造低次（通常不超过三次）插值多项式来近似目标函数，并逐步用插值多项式的极小点来逼近的极小点.由于插值多项式的极小点容易求得，从而可用其逼近的极小点.插值方法设函数

在区间上有定义，已知

在m+1个不同点

处函数值分别为

若存在一个次数为m的多项式，满足则称

为

的m次插值多项式，

称为被插函数，(3.9)称为插值条件，称为插值点.定义3.2m次插值多项式（3.9）插值方法插值方法的几何意义满足条件式(3.9)，即找一条通过平面上m+1个点的曲线.当m+1个插值点互不相同时，满足条件(3.9)的次数不超过m的多项式存在且唯一.插值条件式(3.9)利用的是插值点的函数值；利用插值点的导数值也可建立插值条件.不同的插值条件可以得到不同的插值多项式.插值方法3.1.3.1一点二次插值法3.1.3.2两点二次插值法3.1.3.3三点二次插值法3.1.3.4三次插值法一点二次插值法设在一个插值点已知函数值、一阶导数值和二阶导数值.利用、和构造二次插值多项式：并要求满足插值条件：解上述方程组得：则二次多项式

的极小点为：基本思路一点二次插值法一点二次插值法的迭代公式（3.10）按(3.10)不断迭代，当满足终止准则时，就可得到目标函数极小点的近似估计.注：若对区间内任意，有，则一点二次插值法会收敛到极小点；反之，该方法可能会失效.一点二次插值法例3.3用一点二次插值法求函数的近似极小点.取插值点当

时停止迭代，其中解：已知初始点计算函数

的一阶和二阶导数：第一次迭代：第二次迭代：一点二次插值法第三次迭代：由于

，故停止迭代.此时，因此为函数

的一个近似极小点.一点二次插值法一点二次插值法收敛性和收敛速度设是二阶连续可微函数，

满足

，则当初始点

充分接近

时，一点二次插值公式(3.10)产生的序列收敛到，其收敛速度为二阶.定理3.1注：定理表明，一点二次插值法具有局部二阶收敛速度.插值方法3.1.3.1一点二次插值法3.1.3.2两点二次插值法3.1.3.3三点二次插值法3.1.3.4三次插值法两点二次插值法设已知两个插值点处的函数值以及其中一个插值点的一阶导数值或，由此构造二次插值多项式：并要求满足插值条件：方法1两点二次插值法解方程组得：则二次多项式

的极小点为：迭代公式为：（3.11）两点二次插值法设已知两个插值点处的一阶导函数值，以及其中一个插值点的函数值或，由此构造二次插值多项式：并要求满足插值条件：方法2两点二次插值法解方程组得：则二次多项式

的极小点为：迭代公式为：(3.13)又称为割线公式，故该方法又被称为割线法.（3.13）（3.12）两点二次插值法收敛性和收敛速度设是三阶连续可微函数，

满足

则由式(3.13)迭代产生的序列收敛到，其收敛速度为类似地，由式(3.11)迭代产生的收敛速度也约为1.618.定理3.2注：定理表明，两点二次插值法具有超线性收敛速度.插值方法3.1.3.1一点二次插值法3.1.3.2两点二次插值法3.1.3.3三点二次插值法3.1.3.4三次插值法三点二次插值法设已知两个插值点满足

利用三点处的函数值构造二次插值多项式并要求满足插值条件基本思路三点二次插值法解方程组得：则多项式

的极小点为：（3.14）三点二次插值法求得和后，满足终止准则须符合下面任一条件：当时，当时，其中，通常取此时，如果则极小点估计为，否则为若终止准则不满足，则需要利用

提供的信息，从和中选出三个相邻的点，将原来的搜索区间缩小，然后重复上述过程，直到终止准则满足.

三点二次插值法算法3.4:三点二次插值法的计算步骤1给定插值点

及函数值2由式(3.14)计算

;3比较

和的大小.若

，则转至步骤4；否则转至步骤5;4若

则

转至步骤6；否则

转至步骤6；5若

则

转至步骤6；否则

转至步骤6;6若满足终止准则，则停止迭代；否则转至步骤2，在新的搜索区间上按公式(3.14)计算二次插值多项式的极小点

.三点二次插值法收敛性和收敛速度设是四阶连续可微函数，

满足

则由三点二次插值法式(3.14)迭代产生的序列

收敛到，其收敛速度的阶约为1.32.定理3.3注：定理表明，三点二次插值法具有超线性收敛速度.3.1.3插值方法3.1.3.1一点二次插值法3.1.3.2两点二次插值法3.1.3.3三点二次插值法3.1.3.4三次插值法三次插值法利用及构造三次多项式，求该三次多项式的极小点可得迭代公式：其中：可以证明，在一定条件下两点三次插值法具有二阶收敛速度.基本思路一些情况下，二次多项式无法很好地近似，此时应采用三次插值法.第3章线搜索方法3.1精确线搜索方法3.2精确线搜索方法的收敛性3.3非精确线搜索方法3.4非精确线搜索方法的收敛性精确线搜索方法的收敛性负梯度方向和迭代方向的夹角记为，即设是下降方向，

是精确线搜索的步长因子，若存在常数

对所有都有

则定理3.4精确线搜索方法的收敛性证明：由泰勒定理和假设可知对于任意

存在使得令可以得到：精确线搜索方法的收敛性由于是精确线搜索步长，故有：精确线搜索方法的收敛性设在水平集上，有下界，

存在且一致连续.若迭代方向

与

之间的夹角

一致有界，即存在使得则对某个有限k有或者定理3.5精确线搜索方法的收敛性精确线搜索方法的收敛性证明：假设对所有的k，下面用反证法证明假设则存在和一个子序列使得从而(3.15)由中值定理和柯西-施瓦茨(Cauchy-Schwarz)不等式，可得其中在和之间.因为在水平集L上一致连续，故存在

，使得当

时，有精确线搜索方法的收敛性(3.16)令由式（3.16）可得其中，第二个不等式是由式(3.15)得到的.由于

为精确线搜索步长，故有因此精确线搜索方法的收敛性(3.17)由假设知有下界，又因为单调下降，故有：这与式(3.17)矛盾，从而有定理得证.精确线搜索方法的收敛性(3.18)第3章线搜索方法3.1精确线搜索方法3.2精确线搜索方法的收敛性3.3非精确线搜索方法3.4非精确线搜索方法的收敛性非精确线搜索方法精确线搜索方法：当迭代方向已知时，通过求解得到步长.通常选取使得局限性：精确线搜索方法要求精确或几乎精确的步长因子，问题规模大或目标函数复杂时，计算量很大为提高方法效率，引入非精确线搜索非精确线搜索方法3.3.1

Armijo准则3.3.2

Wolfe准则3.3.3

Goldstein准则3.3.4后退法Armijo准则充分下降条件目标函数在迭代后充分下降，即满足其中一般地，可取为或更小的值.(3.19)例：令Armijo准则如图3.3所示，不等式(3.19)右边为

的线性函数(用虚线表示).图3.3中，满足Armijo准则的步长区间为和.（此时位于虚线下方）

图3.3满足Armijo准则的区间算法3.5:Armijo非精确线搜索方法的计算步骤1给定初始搜索区间

取2计算3计算

若

则停止迭代,输出步长

否则由二次插值公式(3.12)求近似极小点

4转至步骤2.Armijo准则在实际应用中，一般利用插值方法求近似满足Armijo准则的步长.非精确线搜索方法3.3.1

Armijo准则3.3.2

Wolfe准则3.3.3

Goldstein准则3.3.4后退法Wolfe准则曲率条件由图3.3可知，

非常小时，Armijo准则一定成立.为避免步长

取得过小，降低方法效率，引入曲率条件即(3.20)图3.4曲率条件1.曲率条件要求不小于的倍若远小于0，表明沿着当前迭代方向目标函数可以继续下降若

略小于0或大于0，表明沿该当前迭代方向目标函数不会再继续下降，故停止向前搜索Wolfe准则2.对于牛顿方法和拟牛顿方法，

通常取为0.9，对于非线性共轭梯度方法，

通常取为0.1.注：Wolfe准则Wolfe准则Wolfe准则由充分下降条件和曲率条件构成：其中(3.21)Wolfe准则例：在图3.5中，满足Wolfe准则的

的区间为和图3.5满足Wolfe准则的区间

Wolfe准则Wolfe准则的局限性曲率条件(3.20)的不足之处在于，即使，也无法保证满足准则的点接近精确线搜索的结果.图3.5满足Wolfe准则的区间

例：在图3.5中，区间

内的点均满足Wolfe准则，但该区间与真实极小点，即精确线搜索结果，相距甚远.为使步长在局部极小点的领域内，提出了强Wolfe准则.Wolfe准则强Wolfe准则强Wolfe准则由下列充分下降条件和曲率条件构成：其中(3.22)(3.23)注：强Wolfe准则不允许远大于0，排除了一些远离局部极小点的步长.当时，(3.23)的极限就是精确线搜索条件.一般地，

取得越小，满足强Wolfe准则的

越接近精确线搜索结果，但工作量也越大.通常取Wolfe准则算法3.6:Wolfe非精确线搜索方法的计算步骤1给定初始搜索区间

取2计算3计算

若

转至步骤4；否则由二次插值公式(3.11)计算近似极小点

令

转至步骤3;4计算

若则停止迭代，输出步长否则用二次插值公式(3.13)计算近似极小点

令

转至步骤3.Wolfe准则设是连续可微函数，

是

在

处的一个下降方向，且在

时有下界.若

满足

，则

一定存在一个区间，该区间内所有步长均满足Wolfe准则和强Wolfe准则.定理3.6注：定理表明，对于任意一个光滑且有下界的函数

，一定存在步长满足Wolfe准则和强Wolfe准则.证明：由假设可知对所有有下界.因为故线性函数关于

无下界，因此，

与至少存在一个交点.令

表示交点对应的最小步长，于是显然，所有

均满足充分下降条件由中值定理知存在满足Wolfe准则(3.24)(3.25)Wolfe准则结合(3.24)、(3.25)以及可得因此，步长

满足Wolfe准则，且(3.20)中不等号严格成立.于是，由

的光滑性假设，一定存在

的某个邻域，该邻域内所有步长均满足Wolfe准则.因为(3.26)不等号左端项是负的，故在该领域内，强Wolfe准则也成立.(3.26)非精确线搜索方法3.3.1

Armijo准则3.3.2

Wolfe准则3.3.3

Goldstein准则3.3.4后退法Goldstein准则Goldstein准则为:其中(3.27)(3.28)注：Goldstein准则中(3.27)为充分下降条件，保证步长

可以实现目标函数充分下降，同时(3.28)保证步长又不会取得过小.Goldstein准则例：如图3.6所示，满足Goldstein准则的步长区间为图3.6满足Goldstein准则的区间Goldstein准则算法3.7:Goldstein非精确线搜索方法的计算步骤1给定初始搜索区间

取2计算3计算

若

则转至步骤4；否则

转至步骤3;4若则停止迭代，输出步长否则

,转至步骤3.Goldstein准则Goldstein准则vs

Wolfe准则相较于Wolfe准则，Goldstein准则一个缺点是式(3.28)可能把

的极小点排除在可接受区间之外Goldstein准则和Wolfe准则有许多共同之处，且两个准则的收敛性质非常相似Goldstein准则常用于牛顿方法，但不适用于拟牛顿方法，而Wolfe准则在拟牛顿方法中起重要作用非精确线搜索方法3.3.1

Armijo准则3.3.2

Wolfe准则3.3.3

Goldstein准则3.3.4后退法后退法方法对比Armijo准则：仅使用充分下降条件，可能会出现很小的步长，从而增加计算量.Wolfe准则和Goldstein准则：添加额外条件以避免步长取得过小.后退法（回溯直线搜索法）：合适地选取候选步长，只用充分下降条件.后退法算法3.8:后退法的计算步骤1取2计算3计算

若

则停止迭代，输出步长否则转至步骤4;4令其中转至步骤3.注：在牛顿方法和拟牛顿方法中，初始步长通常取为1，在其他方法（例如共轭梯度方法）中，可能取不同的值.随着步长不断缩小，最终会得到满足充分下降条件的步长.参数

可以在每步迭代时取不同值，只要保证在每步迭代中,

均属于预设的区间后退法非常适合牛顿方法，但不太适合拟牛顿方法和共轭梯度方法.第3章线搜索方法3.1精确线搜索方法3.2精确线搜索方法的收敛性3.3非精确线搜索方法3.4非精确线搜索方法的收敛性非精确线搜索方法的收敛性Wolfe准则Wolfe准则由充分下降条件和曲率条件构成：其中(3.21)非精确线搜索方法的收敛性负梯度方向和迭代方向的夹角记为设

是连续可微函数，梯度

满足Lipschitz

连续条件，即存在常数

使得为

在

处的一个下降方向，若在时有下界，则对满足Wolfe准则的任何都有引理3.1(3.29)(3.30)注：引理给出了采用Wolfe准则的非精确线搜索方法在单步迭代中目标函数减少量的下界.非精确线搜索方法的收敛性证明：由Lipschitz连续条件得结合Wolfe准则的曲率条件，可得即利用Wolfe准则的充分下降条件和式(3.31)，有(3.31)非精确线搜索方法的收敛性设连续可微，有下界，满足Lipschitz

连续条件，即存在常数

使得设非精确线搜索方法采用Wolfe准则，则若迭代方向

与之间的夹角

一致有界，即存在

使得

则定理3.7注：1.定理表明，只要迭代方向没有太接近梯度的正交方向，就可以保证采用Wolfe准则的非精确线搜索方法的全局收敛性.2.对于强Wolfe准则和Goldstein准则，可以得到类似结论.(3.32)非精确线搜索方法的收敛性证明：由引理3.1，有对上式从进行累加求和，可得由于

有下界，因此可知对任意均小于某个正常数.于是，对(3.33)关于

取极限，得到因此(3.33)(3.34)非精确线搜索方法的收敛性若夹角一致有界，则存在一个正数

使得结合(3.34)，可得数据科学优化方法Optimization

Method

in

Data

Science引入从本章开始，我们将讨论求解无约束最优化问题的基本最优化方法，内容包括方法的思想、计算步骤、性质、数值表现等.主要内容12本章介绍最基本的一类最优化方法——负梯度方法，包括梯度下降方法、最速下降方法以及各种变体和改进.这一类方法仅需利用目标函数的一阶导数信息，是目前深度学习领域最常用的一类优化方法.第4章负梯度方法4.1梯度下降方法4.2最速下降方法4.3梯度下降方法的变体4.4梯度下降方法的改进4.5数值实验第4章负梯度方法4.1梯度下降方法4.2最速下降方法4.3梯度下降方法的变体4.4梯度下降方法的改进4.5数值实验梯度下降方法？梯度下降(GradientDescent,GD)方法以目标函数在当前迭代点处的负梯度为迭代方向，即令，其原因在于在所有迭代方向中，负梯度方向是使目标函数下降最快的方向.梯度下降方法

由泰勒定理可知，对任意迭代方向和步长均有显然，若满足，则，故是下降方向.给定步长后，

的值越小，在处的下降量越大.由Cauchy-Schwartz不等式可知，当且仅当时，

最小，等于.由此可见，负梯度方向就是目标函数在处下降最快的方向.梯度下降方法算法4.1：梯度下降方法的计算步骤1给定初始点

；2若满足终止准则，则停止