乘子(罚函数)法

《乘子(罚函数)法》由会员分享，可在线阅读，更多相关《乘子(罚函数)法（40页珍藏版）》请在金锄头文库上搜索。

1、邵建峰 运筹与优化运筹与优化 邵建峰 第五章第五章 约束最优化方法约束最优化方法 信息与计算科学系信息与计算科学系 邵建峰邵建峰 本章内容：本章内容： 5.1 5.1 约束最优化问题的最优性条件约束最优化问题的最优性条件 5.2 5.2 罚函数法罚函数法 5.3 5.3 乘子乘子( (罚函数罚函数) )法法 5.4 5.4 投影梯度法投影梯度法 5.5 5.5 简约梯度法简约梯度法 5.6 5.6 约束变尺度法约束变尺度法 邵建峰 7.2 7.2 乘子乘子( (罚函数罚函数) )法法 信息与计算科学系信息与计算科学系 邵建峰邵建峰 本节内容：本节内容： 一一. . 等式约束问题等式约束问题 二

2、不等式约束问题二不等式约束问题 三三. . 约束优化问题的约束优化问题的Matlab求解求解 约束最优化问题的约束最优化问题的罚函数思想：罚函数思想： min( )f xmixgi, 2, 10)(ljxhj, 2, 10)(nTnRxxxx),(21s.t. 其可行（容许）解集其可行（容许）解集 |( )0,1,2,( )0,1,2, ,ijSxg ximh xjl nTnRxxxx),(21外外罚函数法：罚函数法： 可以构造可以构造增广目标函数增广目标函数 其中其中 求解原问题转化为求解一系列的求解原问题转化为求解一系列的无约束问题无约束问题 ( , )( )( )P xf xP x+11

3、( )|min(0,( )|( )|(1,1)mlij ijP xg xh x+ 0 称为称为罚因子罚因子. . 称为称为罚函数罚函数, , ( )P xmin P(x, k) ( k + ) 内外混合罚函数法：内外混合罚函数法： 可以构造可以构造增广目标函数增广目标函数 求解原问题转化为求解一系列的求解原问题转化为求解一系列的无约束问题无约束问题 min P(x, rk) (rk 0+) 10( ) 0,1,2,iIi g xim20( ) 0,1,2,iIi g xim30( ) 0,1,2,jIj h xjl1( , )( )ln( )i i IP x rf xrg x-23221|mi

4、n(0,( )|min(0,( )|ij i Ij Ig xh xr+211|( )|lj jh xr+内部惩罚函数内部惩罚函数 外部惩罚函数外部惩罚函数 由于增广目标函数的由于增广目标函数的 Hesse 阵阵 2P(x, ) 和和 2B(x, r) 的条件数随的条件数随 增大和增大和 r 的减小而变大，会造成求解系列的减小而变大，会造成求解系列 无约束优化问题的困难：无约束优化问题的困难： 为使无约束优化的解接近于原约束优化的解，选择的为使无约束优化的解接近于原约束优化的解，选择的 罚因子罚因子 和和 r 应该充分大或充分小，但是，这时对应的应该充分大或充分小，但是，这时对应的 无约束优化问

5、题的目标函数接近于“病态”无约束优化问题的目标函数接近于“病态”. 这是这是罚函数法固有的，本质性的弱点罚函数法固有的，本质性的弱点。因而提出下面。因而提出下面 的的乘子法（乘子罚函数法）乘子法（乘子罚函数法）. 一一等式约束问题的等式约束问题的乘子乘子 (罚函数罚函数) 法法 min( )f x( )0,1,2,jh xjls.t. 拉格朗日（拉格朗日（Lagrange）函数）函数 )()(),(xhxfxLT- -ljjjxhxf 1)()(其中其中 12( )( ),( ),( ) .T lh xh xh xh x( , )( )( ),T xL xf xh x-( , )( )L xh

6、 x而且而且 222( , )( )( )T xxxL xf xh x-定理定理1 1 (Lagrange) 回顾回顾 （1）*x是问题（）的局部最优点； （2）)(,),(),(),(21xhxhxhxfl：RRn 在*x附近 的某邻域内可微； （3）)(,),(),(21xhxhxhl线性无关。 则必存在实数* 2* 1,l，使得 0)()( 1*- ljjjxhxf即 *()(,)0()()T xf xhLxx- 其中T l),(* 2* 1*。 设设 定理定理2 2 (二阶充分二阶充分条件条件) 设在问题（）中 （1）)(,),(),(),(21xhxhxhxfl二阶 连续可微； （2

7、）存在nRx *，lR* 使得 Lagrange 函数的梯度为零，即 0)()()(),(*-xhxfxLT（3）对任意nRv，且使得0)(*xhvT的非零 向量v，总有 0),(*2vxLvxT那么，*x是问题（）的严格局部最优点。 回顾回顾 1 1、拉格朗日函数拉格朗日函数的极小点的极小点 *(,)0xL x*x是问题是问题的的局部最优点局部最优点 即若即若 拉格朗日（拉格朗日（Lagrange）函数）函数的极小点可能不存在的极小点可能不存在! 一个自然的问题是一个自然的问题是, 能否找到能否找到 *使得使得 (x*, *) 是是 Lagrange函数的极小点函数的极小点? 那样的话那样的

8、话, 约束问题就转化为无约束问题约束问题就转化为无约束问题. 例例1 1 约束优化问题约束优化问题 22 122min( )3f xxxx-解解 因为拉格朗日（因为拉格朗日（Lagrange）函数）函数 22 12223( , )L xxxxx-22 122(3)xxx-+-对于任何对于任何 , 拉格朗日拉格朗日L(x, )关于关于 x 的极小点不存在的极小点不存在. s.t. 20x 事实上，对于任何参数事实上，对于任何参数 , 对任何确定的对任何确定的 x1, 当当 x2 + 时，时， ( , ).L x - -2 2、外罚函数外罚函数参数参数 外罚函数法：外罚函数法： 构造构造增广目标函

9、数增广目标函数 其中其中 求解原问题转化为求解一系列的求解原问题转化为求解一系列的无约束问题无约束问题 ( , )( )( )P xf xP x+21( )|( )|lj jP xh x 0 称为称为罚因子罚因子. . 称为称为罚函数罚函数, , ( )P xmin P(x, k) ( k + ) 回顾回顾 关于关于罚函数罚函数参数参数 ： 另一个问题是另一个问题是, 能否找到能否找到 *, 使得使得 P(x, *) 的无约束的无约束 极小点极小点 x* 是是原原约束问题的极小点约束问题的极小点？ 21( , )( )( )lj jP xf xh x+如果如果 x* 是是 P(x, *)的极小

10、点的极小点, 则有则有 由于由于x*是可行点是可行点, hj(x*) = 0, 因此因此应该有应该有 这在一般情况下这在一般情况下是不成立的是不成立的. 0*(,)xP x 0*().f x1*()()()ljj jf xh xh x + + min P(x, k) ( k + ) 3 3、等式约束问题的乘子法、等式约束问题的乘子法 我们将上述两种思路结合起来：我们将上述两种思路结合起来： *, *, 使得使得 x* 是下面的是下面的增广增广Lagrange函数函数的极小点的极小点. ( , )L x min( ,) nlx R RL x 21min( , )( )( ) nljx RjP x

11、f xh x +即考虑能否找到即考虑能否找到 ( )P x + +例例1 1 约束优化问题约束优化问题 22 122min( )3f xxxx-解解 因为拉格朗日（因为拉格朗日（Lagrange）函数）函数 ( , )L x 22 122(3),xxx-+-增广增广Lagrange函数函数 s.t. 20x 取取 2 22( )/P xx 22 122232( , ,)()M xxxx - -+-+当当 *= -3, * = 2 时时, ,原问题最优解原问题最优解 (0,0)(0,0)T 是是 增广增广Lagrange函数的最优解函数的最优解. . 112( , ,)xMxx 2232( ,

12、,)()()xMxx -+- -+-求解求解无约束问题无约束问题 得得 令令 要求要求 x0 满足约束条件满足约束条件 x2 = 0, 必须取必须取 = -3, 从而从而 x0 = (0, 0)T = x*, 得到原约束问题的最优解得到原约束问题的最优解. 112( , ,)xMxx 2232( , ,)()()xMxx -+- -+-1 102,Mxx 2 2023()().Mxx -+-+ 0302( ,) .Tx + + - -22 122232( , ,)()M xxxx - -+-+4 4、乘子法的理论分析、乘子法的理论分析 min( )f x( )0,1,2,jh xjls.t.

13、其中其中h(x)=(h1(x), ,hl(x)T, 目标函数和约束函数目标函数和约束函数二次二次 连续可微连续可微. 设设 Rl 为乘子向量为乘子向量, 则上面问题的则上面问题的Lagrange 函数为函数为 ( , )( )( ),TL xf xh x-对任意的对任意的 x*D, 有有 *(,)()()()TL xf xh xf x-*( )( )( ,)Tf xh xL x-因此因此, 原约束问题原约束问题等价于等价于下面的约束问题下面的约束问题 min( , *)L x( )0,1,2,jh xjls.t. 构造构造增广增广Lagrange函数函数 2( , ,)( , )( )( )T

14、M xL xh xh x +min( )f x( )0,1,2,jh xjls.t. 并求解并求解 2min( , ,)( , )( )( )TM xL xh xh x +引理引理（收敛收敛相关相关性性质质） x*Rn和和 *Rn满足满足二阶充分条件二阶充分条件(定理定理2), 则存在则存在 一个数一个数 * 0, 对所有的对所有的 *, x*是增广目标函数是增广目标函数 的严格局部极小点的严格局部极小点; 反之反之, 若若h(x0)=0 ，且，且 x0对某个对某个 0是增广目标函数的是增广目标函数的 局部极小点局部极小点, 则则x0 是等式约束问题的局部极小点是等式约束问题的局部极小点. 设在上面等式约束问题中设在上面等式约束问题中, 2( , ,)( , )( )( )TM xL xh xh x