最优化方法第二章_线搜索算法_最速下降法

1. 算法原理最速下降法的搜索法向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。

已知目标函数在()k X 点的梯度为：()()()()()()()()12...Tk k k k nf X f X f X f X x x x ⎡⎤∂∂∂⎢⎥∇=∂∂∂⎢⎥⎣⎦当求目标函数的最小点时，由于函数沿负梯度方向下降最快，故在()k X 点的探索方向应取该点的负梯度方向，即()()()()()k k k f X S f X∇=-∇显然，()k S 为单位向量。

这样第1k +次迭代计算所得的新点为()()()()(1)()()()()()k k k k k k k k f X X X S X f Xαα+∇=+=-∇负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最速下降的过程，它们依赖于()()()k k f Xα∇的大小。

步长()k α有两种取法：一种方法是任意给定一个初始步长，使满足条件：()()()()()()k k k k f X S f X α+<另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步长α，即对目标函数极小，以得到最优步长：()()()()()0min ()()k k k k k f X S f X S ααα>+=+以此最优步长作为由()k X点出发沿该点的负梯度方向探索的步长()k α。

这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来进行判断：()()()()()1()(1)2()()(1)3k k k k k k f X f X f X f X X Xεεε--⎧∇≤⎪⎪-⎪≤⎨⎪⎪-≤⎪⎩2. 算法步骤用最速下降法求无约束多维极值问题min (),nf x x R ∈的算法步骤如下：（1） 取初始点(0)x ，精度0ε>，令0k = （2） 计算搜索方向()()()k k vf x =-∇，其中()()k f x ∇表示函数()f x 在点()k x 处的梯度；（3） 若()k v ε≤，则停止计算；否则，从()k x 出发，沿()k v 进行一维搜索，即求k λ，使得()()()()0()min ()k k k k k f xv f x v λλλ≥+=+。

《最优化方法》课程教学大纲一、课程基本信息课程代码：102193课程名称：最优化方法英文名称：Optimization Methods课程类别：专业选修课学时：48学分：3适用对象:大三学生考核方式：考试先修课程：高等代数，数学分析二、课程简介本课程介绍线性规划，非线性规划的优化算法，主要包括：单纯形法，最速下降法，牛顿法，共轭梯度法，拟牛顿法等。

This course will introduce optimization methods in linear programming, and nonlinear programming, including: simplex method, steepest descent method, Newton's method, Conjugate gradient method and quasi Newton method et al.三、课程性质与教学目的本课程是面向大三数学与应用数学，信息与计算科学专业学生开设的专业选修课。

课程目的是介绍最优化的一些方法，作为人工智能的重要辅助课程，培养和增强学生解决实际数据分析问题中优化算法设计的能力。

四、教学内容及要求第一章最优化简介（一）目的与要求介绍最优化的研究内容和框架（二）教学内容最优化的研究范畴1．主要内容最优化方法的发展历程，分类2．基本概念和知识点最优化方法方法的简史.3．问题与应用（能力要求）了解最优化方法的发展历程.（三）思考与实践思考最优化方法所涉及的基础预备知识。

（四）教学方法与手段课堂讲授第二章凸优化（一）目的与要求介绍凸优化的基本概念和研究内容（二）教学内容1.主要内容凸集，凸包，凸函数，方向导数，上图2.基本概念和知识点凸集，凸函数3.问题与应用（能力要求）凸函数的判别（三）思考与实践上图的应用（四）教学方法与手段课堂讲授第三章一维优化（一）目的与要求掌握一维优化问题的可微性，凸性判别条件。

最优化Armijo算法确定步长的最速下降法资料最速下降法是最优化算法中最简单、最基础的一种方法，但其收敛速度较慢且容易陷入局部最优解。

因此，在最速下降法的基础上，可以通过引入步长的方法来提高算法的收敛速度。

而Armijo算法就是一种常见的用于确定步长的方法。

最速下降法基础假设我们要最小化目标函数f(x)，那么最速下降法的思路就是从一个初始点x0开始，不断朝着负梯度方向进行迭代，直到找到最优解x∗，即：$x_{k+1} = x_k - \\alpha_k \ abla f(x_k)$其中，ablaf(x k)是f(x)在x k处的梯度，$\\alpha_k$ 是步长（也称为学习率），表示每次迭代的步长大小。

但这里还有一个问题：如何确定每次迭代的步长呢？Armijo算法Armijo算法是一种基于梯度下降法的步长确定方法。

它的思路是，每次迭代的步长不应该过大，否则容易导致超出收敛区域。

同时，步长也不应该过小，否则收敛速度会变得非常缓慢。

因此，步长的大小应该恰到好处，即在一定范围内找到一个最优的步长大小。

具体地，Armijo算法通过二分搜索的方法，在可行步长范围内找到一个最优的步长 $\\alpha_k$。

具体过程如下：1.首先初始化 $\\alpha_0$，并设定一些参数，如尝试步长大小t、可行步长下界 $\\tau$ 和函数下降的最小比例 $\\gamma$。

2.计算目标函数f(x k−t ablaf(x k))，以及根据一定准则确定下一个$\\alpha$。

3.如果 $f(x_k - \\alpha_k\ abla f(x_k))$ 函数值比f(x k)减小了一些比例$\\gamma$，则认为当前 $\\alpha_k$ 是可行的步长。

4.如果当前 $\\alpha_k$ 不是可行的步长，则将其折半，即 $\\alpha_k\\leftarrow \\alpha_k/2$，直到找到一个可行的步长为止。

最优化方法-习题解答张彦斌计算机学院2014年10月20日Contents1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、412第二章线搜索算法-P27习题2、4、643第三章最速下降法和牛顿法P41习题1，2，374第四章共轭梯度法P51习题1，3，6(1)105第五章拟牛顿法P73-2126第六章信赖域方法P86-8147第七章非线性最小二乘问题P98-1，2，6188第八章最优性条件P112-1，2,5,6239第九章罚函数法P132，1-(1)、2-(1)、3-(3),62610第十一章二次规划习题11P178-1（1），5291第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、4 1.验证下列各集合是凸集:(1)S={(x1,x2)|2x1+x2≥1,x1−2x2≥1};需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)∈S及任意的实数λ∈[0,1],都有λx+(1−λ)y∈S.即,(λx1+(1−λ)y1,λx2+(1−λ)y2)∈S证：由x(x1,x2),y(y1,y2)∈S得到，{2x1+x2≥1,x1−2x2≥12y1+y2≥1,y1−2y2≥1(1)1把(1)中的两个式子对应的左右两部分分别乘以λ和1−λ,然后再相加，即得λ(2x1+x2)+(1−λ)(2y1+y2)≥1,λ(x1−2x2)+(1−λ)(y1−2y2)≥1(2)合并同类项，2(λx1+(1−λ)y1)+(λx2+(1−λ)y2)≥1,(λx1+(1−λ)y1)−2(λx2+(1−λ)y2)≥1(3)证毕.2.判断下列函数为凸（凹）函数或严格凸（凹）函数：(3)f(x)=x21−2x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5，f在凸集上是（I）凸函数的充分必要条件是∇2f(x)对一切x为半正定；（II）严格凸函数的充分条件是∇2f(x)对一切x为正定。

最速下降法：算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点。

沿负梯度方向函数值下降很快的特点，容易使认为这一定是最理想的搜索方向，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢。

其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象。

从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.牛顿法：基本思想：利用目标函数的一个二次函数去近似一个目标函数，然后精确的求出这个二次函数的极小点，从而该极小点近似为原目标函数的一个局部极小点。

优点 1. 当目标函数是正定二次函数时，Newton 法具有二次终止性。

2. 当目标函数的梯度和Hesse 矩阵易求时，并且能对初始点给出较好估计时，建议使用牛顿法为宜。

缺点：1. Hesse 矩阵可能为奇异矩阵，处理办法有：改为梯度方向搜索。

共轭梯度法：优点：收敛速度优于最速下降法，存贮量小，计算简单.适合于优化变量数目较多的中等规模优化问题.缺点：变度量法：较好的收敛速度，不计算Hesse 矩阵1．对称秩1 修正公式的缺点（1）要求( ) ( ) ( ) ( ) ( ) 0 k k k T k y B s s − ≠0（2）不能保证B ( k ) 正定性的传递2．BFGS 算法与DFP 算法的对比对正定二次函数效果相同，对一般可微函数效果可能不同。

1） BFGS 算法的收敛性、数值计算效率优于DFP 算法；（2） BFGS 算法要解线性方程组，而DFP 算法不需要。

基本性质：有效集法：算法思想：依据凸二次规划问题的性质2，通过求解等式约束的凸二次规划问题，可能得到原凸二次规划问题的最优解。

有效集法就是通过求解一系列等式约束凸二次规划问题，获取一般凸二次规划问题解的方法。

数学与计算科学学院实验报告实验项目名称使用非精确线搜索Armijo算法确定步长的最速下降法所属课程名称最优化方法实验类型算法编程实验日期班级学号姓名成绩)](-)([11-)(-)( )2.3(||-||21)-()-(21)(-)( 0)( )(,*2*12**T *****x f x f x f x f x x x x Q x x x f x f q Qx x f x q Qx x f k k Q ⎪⎭⎫ ⎝⎛+≤===+=∇+=∇+κκ可以改写成所以则处且在由于对于二次函数.,( .,1 , ,1,,,)2.3(算法收敛很慢接近病态）较大时而当求出最优解算法只需一次迭代即可的所有特征值相等时即当特别最速下降收敛很快接近于当有关的条件数矩阵最速下降的收敛速度与看到由收敛速度估计式Q Q Q κκκκ=结论：最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步.【实验环境】Win 7； Matlab7.0二、实验内容： 【实验方案】1、求梯度；2、向梯度相反的方向移动x ，其中 为步长。

如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。

3、循环迭代步骤2，直到x 的值变化到使得在两次迭代之间的差值足够小，比如0.00000001，也就是说，直到两次迭代计算出来的基本没有变化，则说明此时已经达到局部最小值了。

4、此时，输出x ，这个x 就是使得函数最小时的x 的取值 。

【实验过程】梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。

其迭代公式为,其中代表梯度负方向，表示梯度方向上的搜索步长。

梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。

一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的 即可。