最优化方法 第三章(乘子法)

乘子法Rockafellar法Powell法一二Hestenes法三一、Hestenes法..0,1,,.minnRifsthiElxxx考虑等式约束问题Hestenes乘子法22111(,)()()()(,)()22llljjjjjjjccxvfxvhxhxLxvhx𝐿(𝑥,𝑣)=𝑓(𝑥)+𝑣𝑗𝑕𝑗(𝑥𝑙𝑗=1其中为等式约束问题对应的拉格朗日函数。Hestenes乘子法相当于对拉格朗日函数进行外点惩罚。22111(,)()()()(,)()22llljjjjjjjccxvfxvhxhxLxvhx上式称为增广拉格朗日函数。增广拉格朗日函数可以有两种机制逼近极小值点令𝑣逼近极小值点对应的拉格朗日乘子，即𝑣→𝑣∗。原因：存在阈值𝑐1>0,当𝑐>𝑐1时，𝜑(𝑥,𝑣∗)的极小值点即为等式约束优化问题的极小值点。结论：将等式约束优化问题转化为增广拉格朗日函数求解问题(无约束优化问题)。给定一个足够大的𝑐，用迭代方法调整𝑣𝑘→𝑣∗。令𝑐取值很大。类似于外点罚函数法，对不可行解以很大惩罚，在迭代的过程中，迭代点逐步向可行域逼近，此时，𝑕𝑗(𝑥→022111(,)()()()(,)()22(,)()(,)llljjjjjjjccxvfxvhxhxLxvhxxvfxLxv明显地，无约束优化问题的极小值点可以逼近等式约束优化的极小值点。第二种策略逼近效果偏差，其原因在于此时𝒄必须趋近于无穷大。21min(,)()()lkkjjFxMfxMhx外点罚函数法找不到一个有限的，使得kM(,)xkFxM若是等式约束优化问题的局部最优解，则*x*()0,1,..,hxjl****1(,)()2()()lxkkjjjFxMfxMhxhx*()fx因此，要求，但通常情况下*()0fx*()0fx*()0fxHestenes乘子法22111(,)()()()(,)()22llljjjjjjjccxvfxvhxhxLxvhx存在，使得*,1,..,jvjl*****1(,)()()0lxjjjLxvfxvhxK-T条件**1()()0ljjjchxhx而附加项在处的梯度*x增广拉格朗日函数的梯度**(,)0xxv是的稳定点。*x*(,)xv*?,1,..,jvjl拉格朗日乘子调整策略*?,1,..,jvjl首先给定一个足够大的数c，然后通过迭代方法逐步调整min(,)kxv假设已得到，求解无约束优化问题得到解kxkv0(,)kkxxv11()()()()llkkkkkjjjjjjfxvhxchxhx1()()()lkkkkjjjjfxvchxhx1(),1,...,kkkjjjvvchxjl而*****1(,)()()0lxjjjxvfxvhx若是的最优解，则是等式约束问题最优解，kx211()()()2llkkkkjjjjjcfxvhxhx()0,1,...,kjhxjlmin(,)kxv()kfx211()()()2llkjjjjjcfxvhxhx(,)kkxv()fx(,)kxv则是等式约束优化的最优解。kx终止条件：1/221()lkjjhx()khxHestenes乘子法终止条件kxkv为其相应的拉格朗日乘子的充要条件是可行解充分性最优解若是约束优化问题的K-T点，是相应的乘子向量，即*x则存在，使得罚因子c的调整策略*v*x是增广Lagrange函数的极小点。1c1cc当时，**1()()0lkjjjfxvhx*(,)xv若收敛太慢或者不收敛，c选的太小，这时增大c即可。kv(1)cc判断1()/()kkhxhxr1.给定初始点，初始乘子，精度0x1v0,0,01,cr2.以初始点，求解无约束优化问题,1kx211min(,)()()()2llkkjjjjjcxvfxvhxhx得到极小点。kx3.若，则停止计算，得到近似极小点kx1,:1.k否则，若，转步骤4；否则，令()khx1()/()kkhxhxr，置k:=k+1，转步骤2。cc转步骤4。4.令1(),1,...,kkkjjjvvchxjlHestenes乘子法迭代步骤例：用乘子法求解：解：问题的增广Lagrange函数为：下面用解析法求无约束优化的驻点，令：得：221212min.20fxxxstxx222121212,222kkcxvxxvxxxx1121220kxvcxxx2122220kxvcxxx122,22kcvxxc22,2222Tkkkcvcvxcc乘子迭代公式为：取所以设对上式取极限有：得:1(),1,...,,kkkjjjvvchxjl1l1122kkkkvvcxx222222kkkcvcxcvc1211kcvcc10,c11201111kkvv*,kvv*2v*1,1Tx**1201111vv所以22,2222Tkkkcvcvxcc由解：(外点法)对于惩罚函数分别用外点法和乘子法求等式约束问题可求得最优解为：1s.t.6121min212221xxxx222121211(,)(1)26kkFxMxxMxx26,1818TkkkkkMMxMM例：kM令*(0.25,0.75)Tx得（乘子法）对于增广Lagrange函数可求得最优解为：3(),1414Tkkkkkkkcvcvxcc00.0252,0,1,kkcvk取得下22212121211(,)(1)(1)262kkkcxvxxvxxxx1121(1)=1414kkkkkkkkkcvvcxxvcc乘子迭代公式为*0.25v上式中令k趋于无穷，得到得到约束问题的最优解*(0.25,0.75).Tx从表中可见，用乘子法迭代6次就达到外点法迭代15次的效果．罚因子在外点法中要增大到M15＝3276.8，而在乘子法中只要增大到c6=6.4．相比之下，乘子法不需过分地增大惩罚因子，确实比外点法有效很多.Powell乘子法Powell在1969年，与Hestenes几乎同时提出一种乘子法。211(,,)()(())2ljjjjMxfxhx松弛21221221111(,,)()(())21()(()2())211()()()22ljjjjljjjjjjllljjjjjjjjjjMxfxhxfxhxhxfxhxhx211(,)()()()2lljjjjjcxvfxvhxhx/jjjcvc211(,,)(,)2ljjMxxvvc两种乘子方法仅差一个常数项，Powell法是一种比Hestenes法更广泛的乘子方法。但两者的构造思想不同。定理：设对某参数𝜎和𝛼，𝑥∗(𝜎,𝛼)是𝑀(𝑥,𝜎,𝛼)的无约束极小点，则𝑥∗(𝜎,𝛼)也是问题*min()..()((,)),1,2,...,jjfxsthxhxjl的极小值点。若能找到参数𝜎和𝛼，使得*()((,))0,1,2,...,jjhxhxjl则𝑥∗(𝜎,𝛼)是等式约束问题的最优解。*lim((,))0,1,2,...,(,)(,)kkjkkkhxjlxx迭代1(,,)()(())()ljjjjjMxfxhxhx*****1(,)()()0lxjjjLxvfxvhx/jjjcvc1((,)),1,...,kkkjjjhxjl存在充分大的𝜎𝑗，若收敛太慢或者不收敛，说明选的太小，这时增大c即可。kjj终止条件：((,))kkhxPowell乘子法的计算步骤与Hestenes乘子方法类似。Rockafellar乘子法Rockafellar在1973年将乘子法推广到不等式约束优化问题，其思想是引入松弛变量，将不等式约束转化为等式约束。..0,1,,.minnRifstgiIlxxx20,1,,.iigziIlx则增广拉格朗日函数为22211(,,)()[()][()]2lljjjjjjjcxzvfxvgxzgxz将𝜑(𝑥,𝑧,𝑣)关于z求极小，令𝛻𝑧𝜑(𝑥,𝑧,𝑣)=0解析解2[(())]0,1,2,...,jjjjzczvcgxjl若，则𝑣𝑗+𝑐𝑔𝑗(𝑥)≤0𝑧𝑗2=0。若，则𝑣𝑗+𝑐𝑔𝑗𝑥>021(())jjjzvcgxc2(),()0()/,()0jjjjjjjjgxvcgxgxzvcvcgx当，有𝑣𝑗+𝑐𝑔𝑗(𝑥)≤0222222[()][()]()(())221[(())]2jjjjjjjjjjjccvgxzgxzvgxgxvcgxvc当，有𝑣𝑗+𝑐𝑔𝑗𝑥>0222222[()][()]2()22jjjjjjjjcvgxzgxzvvvcccc221(,)(,,)1()[min(0,())]2minzljjjjxvxzvfxvcgxvc由Hestenes乘子法乘子迭代1(),1,...,,kkkjjjvvchxjl2(),()0()()/,()0jjjjjjjjjgxvcgxhxgxzvcvcgx而1min0,()kkkjjjvvcgx结束准则221[min(),/]lkkjjjgxvc..0,1,,g()0,1,,.minnRijfsthiljmxxxx对一般的非线性最优化问题可取211221(,,)()()(())21[min(0,())]2lliiiiimjjjjcxvfxhxhxvcgxvc结束准则22211(())[min(),/]llkkkijjjjhxgxvc