最优化：下降算法与线性搜索

最优化主讲：刘陶文课件制作：刘陶文唯楚有材於斯为盛学好最优化，走遍天下都不怕第二章无约束问题的下降算法与线性搜索第一节无约束问题的最优性条件第二节下降算法的一般步骤第三节线性搜索第一节无约束问题的最优性条件束问题最优解的条件本节，我们来介绍无约是连续可微的这里函数考察无约束问题RRfRxxfnn:(2.1)),(min向的概念首先，我们介绍下降方上升则称是下降处的一个下降方向；若在是函数则称使得若存在数设定义ddxfdxfdxfRdxn,),(),()(,,,1.1.2单调递减在原点处于一元函数处的一个下降方向等价在则函数若令)()()(xfdxf定理下面简单的判别和构造关于下降方向，我们有.)(,.)(,n)(,)()(,)(1.1.2T处的一个下降方向在是特别个下降方向一处的在是则向量对称正定阶矩阵若处的一个下降方向在是则满足若向量则连续可微且设函数定理xfxfdxfxfHdHxfddxfdxff处的一个下降方向在是函数即使得从而存在一个且充分小时则当由于我们有由泰勒展开证明：xfdxfdxfodxfdxfodxfxfdxfTTT)(0,),()(,0)()(,,)()()()()(,)(处的一个下降方向在是函数知所以由的正定性知由时当xfxfHdxfHxfdxfHxfHd)(-,(1)0)()(-)(,)(-)(TT约束问题最优解的条件推广而得到判别多维无条件进行容易将一元函数的极值利用下降方向，我们很关于极小值点）函数的极值条件我们先来回忆一下一元(Rx)1(nRxn0)(*'xf一阶必要条件：0)(0)('*'*xfxf＇二阶必要条件：0)(*xf半正定)(0)(*2*xfx0)(0)('*'*xfxf＇二阶充分条件：正定)(0)(*2*xfx注意这个条件不是充分的。而是双曲抛物面的鞍点不是极小点但显然处在的图形是一双曲抛物面例如：函数,0)0,0(,)0,0(,**21xfxxxfT(2.2)0)(,)1.2(,:)(2.1.2**xfxRRfn则有部最优解的一个局是无约束问题若连续可微设函数条件无约束问题的一阶必要定理1x2xf)0,0(●)(0)(,)1.2(,:)(3.1.2*2**半正定且则有一个局部最优解的是无约束问题若二次连续可微设函数条件无约束问题的二阶必要定理xfxfxRRfn.)1.2(,)(,0)(,:)(4.1.2**2*的一个严格局部最优解是无约束问题则正定且若二次连续可微设函数条件无约束问题的二阶充分定理xxfxfRRfn不正定但最小点是严格局部极小点显然如函数的条件不是必要的定理注意)(),()0,0()(.4.1.2:*2*4241xfxxxxfT2213231--3131)(min1.1.2xxxxxf的问题利用极值条件求解下面例212221212002-2)(,1-2-)(xxxfxxxxf解：1-2,12,1-0,10,0)()4()3()2()1(xxxxxf得稳定点：由一阶必要条件,2-002)(,2002)(,2-002-)(,2002-)(Hessian)4(2(3)2(2)2)1(2xfxfxfxf矩阵为：相应的.,,)3(其它三点不是极值点严格局部最优由二阶条件知x不定负定正定不定条件一阶必要条件也是充分是凸函数时当,f.0)()1.2(,4.1.2***xfxxf满足的最优解的充要条件是是问题则是连续可微的凸函数若函数定理)()(0)-()()(-)(,,0)(**T****xfxfxxxfxfxfRxxfxn即，有对任意的判别定理则由凸函数的满足若证明：只需证充分性：第二节下降算法的一般步骤。无约束问题的下降算法可构造求解的方式，在此基础上，并给出了确定下降方向条件，处的下降方向所满足的在点在前面我们给出了函数xf问题的解或稳定点。是原中某个点或某个极限点算法的目标是使得点列满足条件的原则构造点列出发，按照函数值下降从某个初始点下降算法的基本思想：}{,2,1,0),()(}{10kkkkxkxfxfxx其一般步骤为：的算法优化问题的一类最基本下降算法是求解无约束kkkkkkkkkkTkkkdxxxfdxfdxfdx1:.3)()(:0.20)(:,.1,计算新的近似最优解满足然后计算步长满足计算下降方向首先已知近似最优解.2,1:,4)()(:0330,)(.,||)(||2;0.0,1)(1.3k1kkT0转步令步满足计算步长步；然后转步满足：计算下降方向否则算法终止，则得解若步令精度给定初始点步下降算法结构算法kkdxxxfdxfdxfdxxfkRxkkkkkkkkkkkn总结如下：各章介绍具体将在以后同的最优化算法的不同构造方式对应不的线性组合和，即是某一对称正定矩阵其中：基本的构造方法有两个满足计算下降方向已知近似最优解,)(-)(-)(),(-)()(:.,,-,-kkkkkkkkkkkkkTkkkddxfdbxfadHxfHddxfdx作主要有两部分：我们的工算法为构造一个使用的下降由下降算法的结构知,,具体在下一节介绍求极值一元函数—索来完成这一步主要通过线性搜满足计算步长,)()()()(:.kkkkkkkkdxfxfdxf第三节线性搜索搜索和非精确搜索：的两种线性搜索：精确计算步长k0)()(minT0kkkkkkkkddxfdxf满足即是一维优化问题的解精确搜索：.)()(降即函数值有一定程度下满足按照某种规则计算使之非精确搜索：kkkkkxfdxf一、精确线性搜索(100)0)(.0)()()(),()()(minT'T'0kkkkkkkkkkkkkddxfddxfdxfdxf等价于解方程所以计算得解由则令是一维优化问题的解精确搜索：方法求近似解否则需用数值直接解方程求得简单如果方程;,)100(k有理插值法抛物线法切线法曲线拟合法：分数法黄金分割法二分法试探法：数值方法：的例子：直接解方程计算步长kkTkkTkkkTkkTkkkTkkTkkkQdddxfdxfQddxfdxfQdddxf)(0,)()()()()()()(''得解令则由于对称且正定其中矩阵如二次函数,21)(QRxcxqQxxxfnTT1.单峰函数一、精确线性搜索——黄金分割法(0.618法)定义：设)(xf是区间],[ba上的一元函数，x是)(xf在],[ba上的极小点，且对任意的,,],[,2121xxbaxx有（a）当xx2时，;)()(21xfxf（b）当时，xx1.)()(21xfxf则称是单峰函数。)(xfa..b.x..1x2x..性质：通过计算区间],[ba内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理设是区间],[ba上的单峰函数，x是)(xf在],[ba上的极小点。任取点)(xf,],[badc则有（1）如果)()(dfcf，则;],[bcx（2）如果,)()(dfcf则。],[daxa..b.x..cd2.黄金分割法思想：通过选取试探点使包含极小点的区间按相同比例不断缩短，直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。下面推导黄金分割法的计算公式上单峰，在设],[)(11baxf].,[11bax极小点次迭代前第k],,[kkbax],,[,kkkkba取规定.kk,)()(kkff和计算分两种情况：,)()(.1kkff若,1kka则令;1kkbb,)()(.2kkff若,1kkaa则令.1kkb？与如何确定kkkakbkkukkkkab.1比率相同，即每次迭代区间长度缩短.2)0()(11为某一缩小比例kkkkabab)1()2(）可得：）与（由式（21)())(1(kkkkkkkkabaaba)3()4(件：要求其满足以下两个条kakbkku？取值的确定通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。,)()()1(kkuffk次迭代时有设在第则有。],[],[11kkkkuaba,,111kkuk次迭代时选取在第）有则由（4)(1111kkkkabau)(2kkkaba。不必重新计算因此则，如果令112,1kkkuu618.021512。次迭代时有若在第)()()2(kkuffk同理可得算法步骤：0.],,[.111精度要求给定初始区间ba.1:k令),(382.01111aba令),(618.01111aba).()(11ff与并计算,.2kkab若停止，.2kkabx且否则，；时，转当3)()(kkff.4)()(时，转当kkff,.31kka令,1kkbb,1kk),(618.01111kkkkaba),(1kf计算。转2,.41kkaa令,1kkb,1kk),(382.01111kkkkaba),(1kf计算,1:kk令。转2,1:kk令黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的。倍k)215(其它的试探点算法：Fibonacci算法(分数法)。,2,1,,1Fibonacci1-121kFFFFFkkk数列：Fibonacci算法计算试探点的公式为：-,,,),-(-,,,),-(-----nkabFFankabFFakkknknkkkkknknkk1--knknkFF缩小比例：)(1--11kkknknkkabFFabnnabn-,给定计算次数的计算：关于nnFabFabFFabFFabFFFFFFabFFabnnnnnnnnnn而后得到由此计算出从而故有由递推关系可得11111111111-32211-1-21-)-()-()-()-(-Fibonacci法为一维极小化最优策略，而黄金分割法为近似最优,但后者简单，因而较常用Fibonacci法是黄金分割法的推广，黄金分割法是Fibonacci法的极限25125101Fibonacci212，两个特征根为程为数列递推关系的特征方ccFFccFkkk,Fibonacci代入后得由初始条件数列递推关系的的解是.lim-nnnkkkFFF于是所以)(618.071-三位有效数字时，当nnFFn二、非精确线性搜索—Armijo型线性搜索和Wolfe-Powell型线性搜索.)()(有一定下降量较使得其计算步长易于实现，非精确搜索计算量小，精确搜索计算量较大，kkkkkxfdxf搜索是非精确搜索中最简单的Armijo)6.2()()()(),1,0(Arm