下载文档原格式
05-⽆约束优化算法05-⽆约束优化算法⽬录⼀、⽆约束最⼩化问题[⽆约束最⼩化问题] 使 f(x) 最⼩化， f:R n→R 是凸的，且⼆次可微（意味着 domf 是开集)。
假设这个问题是可解的，也就是存在最优点 x∗ ，最优值 inf x f(x)=f(x∗) ，记为 p∗ .[最优充要条件] 因为 f 是可微且凸的，点 x∗ 是最优点的充要条件是∇f(x∗)=0 .注：其实可以从⼆维的图像去理解因此解决⽆约束最⼩化问题等同于寻找上式的解，是含有n个未知数的n个⽅程的集⽅程组。
有时我们是⽤递归算法来解决这个问题，也就是依次计算x(0),x(1),...∈domf , 有f(x(k))→p∗,k→∞ 。
这样的序列叫做问题的最⼩化序列 (minimizing sequence)。
算法的停⽌条件：f(x(k))−p∗≤ϵ，ϵ≥0 是可容许的误差值。
[初始点，下⽔平集] 初始点 x(0) 必须在 domf 中，并且下⽔平集S={x∈domf|f(x)≤f(x(0))} 必须是闭的。
注：下⽔平集是闭的，其实就是对函数做了⽔平切割，然后⽔平切割下的图像是封闭的如果函数 f 是闭的（也就是它的所有下⽔平集都是闭的）那么以上条件都能满⾜。
定义在domf=R n上的连续函数是闭的，所以如果domf=R n，那么初始下⽔平集条件对于任何x(0)都满⾜。
另⼀种闭函数：定义域是开集，当x趋近于bd domf时，f(x) 趋近于⽆限。
[强凸] ⼀个函数在 S 上是强凸的，如果存在 m>0 ，使得对于所有的 x∈S ，有∇2f(x)⪰mI.注：强凸的性质，其实就是保证函数的 ∇2f(x)>0 ，也就是确保只有⼀个最优解，⽽弱凸是最优解有多个，如下图所⽰。
对于x,y∈S我们有f(y)=f(x)+∇f(x)T(y−x)+12(y−x)T∇2f(z)(y−x) , for some z∈[x,y] 。
根据强凸的假设，最后⼀项⼤于等于 (m/2)‖y−x‖22,∀x,y∈S ，也就是：f(y)≥f(x)+∇f(x)T(y−x)+(m/2)‖y−x‖22 .当m=0 时，我们得到了描述凸性的基本不等式。
无约束最优化直接方法和间接方法的异同一、什么是无约束最优化最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。
其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。
实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。
最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。
无约束最优化问题实际上是一个多元函数无条件极值问题。
虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。
或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。
所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。
无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。
这里我们比较这两类方法的异同。
二、无约束最优化方法1. 使用导数的间接方法1.1 最速下降法函数的负梯度方向是函数值在该点下降最快的方向。
将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。
无约束优化问题的数学模型可以表示为：()n R f ∈x x xmin ，我们假设函数()x f 具有一阶连续偏导数。
⽆约束最优化的常⽤⽅法11/22/2017 12:40:56 PM优化问题在很多领域有着重要的应⽤。
为了⽇后查阅⽅便，本⽂列举常见的⽆约束优化⽅法的计算公式。
需要说明的是，本⽂的⼤部分内容选⾃图书《算法笔记》。
⼀、梯度下降法梯度下降法（Gradient Descent Method）也叫做最速下降法（Steepest Descent Method），因为负梯度是函数局部下降最快的⽅向。
梯度下降梯度下降法的迭代格式为x k+1=x k−αk∇f(x k)梯度下降法⾮常简单，只需要知道如何计算⽬标函数的梯度就可以写出迭代格式。
因此，尽管在不少情况下梯度下降法的收敛速度都很慢，也依然不影响它在⼯业界的⼴泛应⽤。
梯度下降法应⽤到⼀些具体模型上有时也会被视作⼀类特定的算法，例如神经⽹络中的后向传导算法（Back Propagation Algorithm）。
随机梯度下降在机器学习中经常有f(x)=∑m i=1ℓi(x)，其中ℓi(x)是第i个训练样本的损失函数。
这时我们可以使⽤随机梯度下降法（Stochastic Gradient Descent Method）。
其迭代格式为x k+1=x k−αk∇ℓr(x k)其中r∈1,2,⋯,m为随机数。
这种做法可以理解为随机选择⼀个训练样本，进⾏⼀次梯度下降的训练。
在机器学习的问题中，我们通常不需要真的求得最优值，这样不精确的迭代，使得算法不容易过拟合。
由于随机梯度下降法的普及，与此相对的梯度下降法有时被称为批量梯度下降法（Batch Gradient Descent Method），因为它同时考虑所有训练样本。
介于批量梯度下降法和随机梯度下降法之间，还有⼩批量梯度下降法（Min-Batch Gradient Descent Method），也就是每次迭代选择若⼲个训练样本。
步长αk的选取梯度下降法可采⽤BB步长（Barzilai Borwein）。
BB步长有两个计算公式，选择其⼀即可。
无约束最优化直接方法和间接方法的异同一、什么是无约束最优化最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。
其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。
实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。
最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。
无约束最优化问题实际上是一个多元函数无条件极值问题。
虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。
或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。
所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。
无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。
这里我们比较这两类方法的异同。
二、无约束最优化方法1. 使用导数的间接方法1.1 最速下降法函数的负梯度方向是函数值在该点下降最快的方向。
将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。
无约束优化问题的数学模型可以表示为：()n R f ∈x x xmin ，我们假设函数()x f 具有一阶连续偏导数。
无约束优化算法无约束优化算法问题，是指优化问题的可行集为，无约束的标准形式为：∙最优性条件∙极小值点的一阶必要条件设为连续可微函数，如果为局部极小值点，则为驻点，即梯度。
∙极小值的二阶必要条件设为二阶连续可微函数，如果为局部极小值点，则为驻点，即梯度，二阶半正定。
∙极小值点的二阶充分条件设为二阶连续可微函数，如果梯度，二阶正定，则为的局部极小值点，。
以上三个定理为搜索最优点以及判断一个点是否为最优点的基本依据。
经典的优化算法的停止条件为，例如在程序中，即在导数范数小于某特定误差限时停止。
误差限较大，则算法迭代次数减少，计算时间缩短，但解得质量降低；误差限较小，则算法迭代次数增加，计算时间增加，但解的质量提高；误差限一般为，可以根据实际情况设定合适的误差限。
当然，还有极小值点的二阶必要条件与极小值点的二阶充分条件，对的判断，由于目标函数比较复杂，二阶导数矩阵的计算量极大，所以一般算法都在迭代过程中对进行修正，得到，在修正的过程中始终保持的正定性，以此方法解决极小值点的二阶条件问题。
一、最速下降法(1) 算法原理最速下降法是早期的优化算法，其理论根据函数的一阶泰勒展开：由得到根据下降要求故实际中要求根据上式选取合适的，得。
最速下降法取。
由于近似的有：取，则由知：最速下降法有全局收敛性，并且是线性收敛的，算法比较简单。
一般来说，在实际计算中，最速下降法在开始迭代时效果较好，有时能很快地找到最优解得附近，但是当局继续迭代时，常常发生扭摆现象，以致不能达到最优解。
(2) 算法步骤给定控制误差。
步骤1：取初始点，令步骤2：计算。
步骤3：若，则，停止计算；否则，令，由一维搜索步长，使得步骤4：令，，转步骤2。
二、黄金分割法(1) 算法思想通过不断缩小区间的长度来搜索目标函数的极小值点,且是按照可行域全长的0.618(及0.382)选取新点,而不断更新区间进行的.(2) 算法流程步骤ε>.设函数发f(x),初始区间为[a,b],0步骤1：取两点x1,x2(x1<x2),x2=a+0.618(b-a),x1=a+b-x2或x1=a+0.382(b-a),x2=a+b-x1 计算f(x1),f(x2);步骤2: 若f(x1)<f(x2);则去掉[x2,b],则a=a,b=x2,x2=x1,x1=a+b-x2,步骤3: 若f(x1)>f(x2);则去掉[a,x1],则a=x1,b=b,x1=x2,x2=a+b-x1,步骤4: 若f(x1)=f(x2);则去掉[a,x1]和[x2,b],则a=x1,b=x2,重复步骤1.步骤5: 在每一次缩小区间时,判断|b-a|≤ε是否成立,若成立则结束.三、共轭梯度法(1) 算法思想共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。
