东北财经大学：《运筹学》课程教学资源（教案讲义）第三篇 非线性规划 第三章 等式约束的优化

第三章等式约束的优化 §1最优性条件 考虑具有等式约束的最优化问题: min f(x) sth,(x)=0j=1… 其中∫:R”→R,h:R”→R.这类问题的求解方法在数学分析中已解决,即 Lagrange乘数法 先作简要复述。 定理1(一阶必要条件)设∫、b,j=1…,在可行点x的某个邻域0(x,6)可微,向量组 Vh(x)j=1…,l线性无关,若x是(1)的局部最优解,则存在实数,j=1…,l使得 V(x)+∑Vh(x)=0 (2) 定义(n+l)元函数 L(r, d)=f(x)+/h(x) 称为 Lagrange函数,其中λ=(λ,…,1)称为 Lagrange乘子,h(x)=(h1(x)…,h(x)2。可以证 明(2)成立。这只需考虑函数L(x,A)在无约束条件下取极值的必要条件。 VL(x,1)=V(x)+∑Vh(x) V2L(x,A)=h(x)=(h1(x)…,h(x) 由VL(x',x)=0,立得(2)式且有 h,(x)=0,j=1,… 它表明x必须满足(1)之约束条件 联立(2)、(3)所得的解称为 Lagrange函数的稳定点。 定理2(二阶充分条件)设x是(1)的可行解,f、h,J=1…二次可微,若存在向量x∈R 使VL(x,)=0,且L(x,A)的Hese矩阵H(x,λ)正定,则x是(1)的严格局部最优解。 191

191 第三章 等式约束的优化 §1 最优性条件 考虑具有等式约束的最优化问题：    st h x = j = l f x j . . ( ) 0 1, , min ( )  （1） 其中 f R R : n → ，h R R n j : → .这类问题的求解方法在数学分析中已解决，即 Lagranger 乘数法， 先作简要复述。 定理 1（一阶必要条件） 设 f 、 h j l j , = 1,, 在可行点 x *的某个邻域 0( , ) * x  可微，向量组 h x j l j ( ), 1, ,  * =  线性无关，若 x *是（1）的局部最优解，则存在实数 j l j , 1, ,  * =  使得 =  +  = l j j j f x h x 1 * * * ( )  ( ) 0 （2） 定义（n+ l )元函数 L(x, ) f (x) h(x) T  = +  称为 Lagrange 函数，其中 T l ( , , )  = 1   称为 Lagrange 乘子， T l h(x) (h (x), ,h (x)) = 1  。可以证 明（2）成立。这只需考虑函数 L(x,) 在无约束条件下取极值的必要条件。 =  =  +  l j x j j L x f x h x 1 ( ,) ( )  ( ) T l L(x, ) h(x) (h (x), ,h (x))   = = 1  由 ( , 0 * * L x ）= ，立得（2）式且有 h x j l j ( ) = 0, = 1,, （3） 它表明 x *必须满足（1）之约束条件。 联立（2）、（3）所得的解称为 Lagrange 函数的稳定点。 定理 2（二阶充分条件） 设 x *是（1）的可行解， f 、h j l j , = 1,, 二次可微，若存在向量 l  R *  ， 使 ( , ) 0 * * L x  = ，且 L(x,) 的 Hesse 矩阵 H(x * , *） 正定，则 x *是（1）的严格局部最优解

定理的证明只要注意到对任意可行解x,有L(x,A)=f(x),故由上一章定理7 L(, 2)>L(x, 2)=f(x) 故当x为可行解时上式亦成立。 定理2中关于Hese矩阵H(x,)正定的要求太强,很难满足,其实只需要求H(x,)在集合 D={y|wh,(x')y=0,j=1…l} 上正定即可。即若对于y∈D,y≠0有yH(xx)y>0,则x是(1)的严格局部最优解(证 明略,可参见文献[34]) 例1研究问题minf=x1x2-x2xxx St.1+x2+X3= 容易求得稳定点为x’=(1,1,1),x=2。在这种情况下,L(x,x)的H(x,x)阵变为(视λ 为常数,只考虑对x的导数): H=-10 它既不是正定,也不是负定,但在子空间D={y|y+y2+y3=0}上,注意 yhy=-y(y2+y3)-y2(y1+y2)-y2(+y2)=y2+y2+y2>0 于是H在D上是正定的,所以ⅹ至少是问题的局部极小点 下面讨论把 Botsko一阶充分条件用于等式约束(1)的情形以下总假定f(x)及h(x)(k=1,2.1) 于点x的某邻域OXx,)内可微,且可从(1)的约束条件中解出(这只需满足隐函数存在定理的条 件) x=x(x1,…,xm)=x,(x,i=n-l+1…n (4) 这里x=(x1…,xn)2 将(4)代入目标函数f(x)中,可得 F(x)=f(x,…xn-1,xn+(x,…Xn-1)…Xn(x,…Xn-1)]=f(菜,x=+(x)…(x) 于是 Botsko一阶充分条件(上一章()式)变成 (x-x VF(x)>0 其中ⅴF(x)等于零或不存在,x=(x1,…x灬),x=(x1…x),∈O(x,δ) 这时,利用复合函数求导,则上一章(13)式变成

192 定理的证明只要注意到对任意可行解 x，有 L(x,) = f (x) ，故由上一章定理 7 ( , ) ( , ) ( ) * * * L x   L x  = f x 故当 x 为可行解时上式亦成立。 定理 2 中关于 Hesse 矩阵 H(x* , *  )正定的要求太强，很难满足，其实只需要求 H(x* , *  )在集合 D={y ︱ ( ) 0, 1, } * h x y j l T  j = =  上正定即可。即若对于 y  D, y  0 有 T y H(x* , *  ) y  0 ，则 * x 是（1）的严格局部最优解（证 明略，可参见文献[34]）。 例 1 研究问题 min f=-x1x2-x2x3-x1x3 s.t. x1+x2+x3=3 容易求得稳定点为 x *=（1，1，1）T， *  =2。在这种情况下， L(x,) 的 H(x* , *  )阵变为（视  为常数，只考虑对 x 的导数）： H=           − − − − − − 1 1 0 1 0 1 0 1 1 它既不是正定，也不是负定，但在子空间 D = {y ︱ 0} y1 + y2 + y3 = 上，注意 ( ) ( ) ( ) 0 2 3 2 2 2 y Hy = −y1 y2 + y3 − y2 y1 + y3 − y3 y1 + y2 = y1 + y + y  T 于是 H 在 D 上是正定的，所以 x *至少是问题的局部极小点。 下面讨论把 Botsko 一阶充分条件用于等式约束(1)的情形.以下总假定 f(x)及 hk(x)(k=1,2…l ) 于点 x *的某邻域 O(x* , ) 内可微，且可从（1）的约束条件中解出（这只需满足隐函数存在定理的条 件）： xi xi x  xn l xi (x),i n l 1, n ~ ( , , ) ~ = 1 − = = − + （4） 这里 x = （ T n l x , , x ) 1  − 。 将（4）代入目标函数 f(x)中，可得 F( x) = f [( x1,..x n − l , ( ~ n−l+1 x x1,..x n − l )… n x ~ ( x1,..x n − l )]= ( ), ( )) ~ ( , 1 f x x x x x n−l+  n 于是 Botsko 一阶充分条件(上一章(9)式)变成 ( ) ( ) 0 * x − x F x  T (5) 其中 F(x ) , x  * 等于零或不存在 =( T n l x , , x ) 1  − , x = x x − x  T n l ( , , ) , * * 1 *  O( * x , ) 。 这时，利用复合函数求导，则上一章（13）式变成

其中。(j=n-1+1,…,n)由方程组 k=1,…,l,i=1, ax. ax a 出(这要求其导数矩阵/ 非奇异)而解的矩阵形式为 Vx=-( h)v,h 其中x=( )的值 充分性的另一条件(上一章(14)式)变成 (x-xIVF(x)-VF( )I 其极限形式为 lim (x-x)VF(x)=>0 (-X)VF(o) 其中 VF(r)=OF(U)aF(x(2))aF(x (n) ax 与x仅第i个分量不同 例2 求f(x1,x2,x1)=x2+x2+x2在条件 +x2+x3-1=0 值 下的极 解用 Lagrange乘数法可求得问题的稳定点为 1+√3

193 i n l x x x f x f x x i j j n i j n l i i  = −             +   − = − + 0, 1, ~ ~ ( ) 1 * (6) 其中 ( 1, , ) ~ j n l n x x i j = − +    由方程组 k l i n l x h x x x h i k i j j k n j n l = = −   = −     = − + , 1, , , 1, , ~ ~ 1   (7) 给出(这要求其导数矩阵 l l j k x h            ~ 非奇异).而解的矩阵形式为 x x = − x h xh −1 ( ~ ) ~ (8) 其 中 x = （ T n l x , , x ) 1  − , x x x h h T n l n ( , , ) , ( ~ = − +1  = ) , 1, T hl 数值计算时 , 代入点 ( , , , , , , ) * * 1 * 1 * 1 ( ) i i i n i x x  x x x  x = − + 的值. 充分性的另一条件(上一章(14)式)变成 1 ( ) ( ) ( ) [ ( ) ( )] * ( ) * ( )  − −  −  −  T i T i x x F x x x F x F x (9) 其极限形式为 lim * x→x 0 ( ) ( ) ( ) ( ) * ( ) * =  −  −   T i T x x F x x x F x (10) 其中 T n l n l i x F x x F x x F x F x                = − − ( ) , ( ) , ( ) ( ) ( ) 2 (2) 1 (1) ( )  T i i i n l i x (x , x , x , x , x ) * * 1 * 1 * 1 ( ) =  − +  − 与 * x 仅第 i 个分量不同. 例 2 求 2 3 2 2 2 1 2 3 1 f (x , x , x ) = x + x + x 在条件 3 0 2 2 2 x1 + x − x = (11) x1 + x2 + x3 −1 = 0 下的极值. 解 用 Lagrange 乘数法可求得问题的稳定点为 , 2 3 2 1 3 *1 3 *1 2 *1 1 = − − + x = x = x

及 2=2+√3 把x2,x3看作是x1的函数,然后于(11)式对x求偏导数,可得 2x1+2x2 0 ax. ax =0 解得 2 2 x2+ 2x,+1 将上式代入(6)式,并代入x1,x2,x3之值,得 0(x1=x2 1 2-√3) 2 2 1-√3)5+2 0 lin (x1-x2)1+2x32) x1→1 2x2+1 2 自然成立.故知x”是极小值点,x”是极大值点(对于判断极大值点来讲,(5),(6)式中的不等号应反 号,而(9),(10)式中的不等号不变号) 对此例,由于消元后变成一元函数,(10)的极限必为1,故只需检验(6)式是否成立,即可作出判 断,而不必再检验(9)或(10)式成立 §2、乘子法 定理12给出了 Lagrange乘子的存在性,但如何寻找并未真正解决,这里介绍的乘子法恰好 给出一个如何寻找的方法。为此引入增广 Lagrange函数:

194 及 , 2 3 2 1 3 *2 3 *2 2 *2 1 = + − − x = x = x 把 2 3 x , x 看作是 x1 的函数,然后于(11)式对 x1 求偏导数,可得 2 2 0 1 3 1 2 1 2 =   −   + x x x x x x 1+ 0 1 3 1 2 =   +   x x x x 解得             + − + + =        − −         − =                 − 2 1 2( ) 2 1 2 1 1 2 1 1 2 1 2 1 2 2 1 1 1 2 1 3 1 2 x x x x x x x x x x x 将上式代入(6)式,并代入 * 3 * 2 * 1 x , x , x 之值,得 0 3 5 2 3 2 1 3 2 1  −         − + x − ( , 2 3 2 1 3 *1 3 *1 2 *1 1 = − − + x = x = x ) 0 3 5 2 3 2 1 3 2 1  − +         − − x − ( , 2 3 2 1 3 *2 3 *2 2 *2 1 = + − − x = x = x ) 再检验条件(10): 2 1 ( )(1 2 ) *1 2 *1 3 *1 1 2 lim* 1 1 + − + → x x x x x x 3 5 2 3 2 1 3 1 −         − + x − =1>0 2 1 ( )(1 2 ) *2 2 *2 3 *2 1 2 lim*2 1 1 + − + → x x x x x x 3 5 2 3 2 1 3 1 − +         − − x − =1>0 自然成立.故知 *1 x 是极小值点, *2 x 是极大值点(对于判断极大值点来讲,(5),(6)式中的不等号应反 号,而(9),(10) 式中的不等号不变号) 对此例,由于消元后变成一元函数,(10)的极限必为 1,故只需检验(6)式是否成立,即可作出判 断,而不必再检验(9)或(10)式成立. §2、乘子法 定理 1.2 给出了 Lagrange 乘子 *  的存在性，但如何寻找并未真正解决，这里介绍的乘子法恰好 给出一个如何寻找 *  的方法。为此引入增广 Lagrange 函数：

(x,1)=(x,4)+∑(h1(x)2=f(x)+∑孔h(x)+兰∑(h(x)2(12) 其中A1,…,为 Lagrange乘子,M为较大正数。由定理(1)对于局部最优解x*存在∈R!, 使(x*,)为L(x,)的稳定点。即V2L(x2)=0,而附加项兰∑(h(x)2在x*点的梯度为0, 因此,亦有Vo2(x,)=0,这样x*将是q(x,C)的极小点,而求解问题(1),便可转化为对x, 求(x,)的无约束极小了。如何求?设对∈R,求解mn(x,)得x,则 v,(x2,x)=V(x)+∑xwh(x)+M∑h(x)Wh(x)=0 Vf(x)+>(+Mh, (x'))Wh, (x)=0 与(2)相比,自然令 =2+Mm(x) (13) 来调整λ。那么迭代到什么时候才可以结束呢?下面的定理为我们提供了依据 定理3设(x,A)由(12)式定义,x2是无约束优化问题 min (x, 2) (14) 的最优解,则x是(1)的最优解,,…,为其相应的 Lagrange乘子的充要条件是 h,(x2)=0.j=1… 证:若x是(1)的最优解,则显然有h,(x)=0,j=1…,l。反之若x是(14)的最优解,且 h,(x)=0,j=1…,1,则以x都有 (x,x)≥(x5,2)=f(x2) 特别当x是(1)的可行解时,有 f(x)=(x,)≥f(x 故x是(1)的最优解,即x*=x*,同时应有

195    = = = = + = + + l j j M l j j j l j j M x L x h x f x h x h x 1 2 2 1 1 2 2 ( ,) ( ,) ( ( )) ( )  ( ) ( ( )) （12） 其中  l , , 1  为 Lagrange 乘子，M 为较大正数。由定理（1）对于局部最优解 x*存在 l  R *  ， 使（x*, ) *  为 L(x,) 的稳定点。即 ( , ) 0 * * xL x  = ，而附加项 = l j j M h x 1 2 2 ( ( )) 在 x*点的梯度为 0， 因此，亦有 ( , ) 0 * *  x x  = ，这样 x*将是 ( , ) *  x  的极小点，而求解问题（1），便可转化为对 *  ， 求 ( , ) *  x  的无约束极小了。如何求 *  ？设对 k l   R ，求解 min ( , ) k  x  得 x k ,则 ( , ) ( ) ( ) ( ) ( ) 0 1 1  =  +  +   = = = l j k j k j l j k j k j k k k x  x  f x  h x M h x h x 即 ( ) ( ( )) ( 0 1  + +  = = j k j k） l j k j k f x  Mh x h x 与（2）相比，自然令 ( ) 1 k j k j k j = + Mh x +   ，j=1,…, l (13) 来调整 k  。那么迭代到什么时候才可以结束呢？下面的定理为我们提供了依据。 定理 3 设 (x,) 由（12）式定义，x k 是无约束优化问题： min ( , ) k  x  （14） 的最优解，则 k x 是（1）的最优解， k l k 1 ,  , 为其相应的 Lagrange 乘子的充要条件是 h x j l k j ( ) = 0, =1,  , 证： 若 k x 是（1）的最优解，则显然有 h x j l k j ( ) = 0, =1,  , 。反之若 k x 是（14）的最优解，且 h x j l k j ( ) = 0, =1,  , ，则 x 都有 ( , ) ( , ) ( ) k k k k  x    x  = f x 特别当 x 是（1）的可行解时，有 ( ) ( , ) ( ) k k f x =  x   f x 故 k x 是（1）的最优解，即 k x =x*，同时应有

V,(x2,1)=V(x)+∑xvh(x)=0 这证明是与x4=x*对应的 Lagrange乘子 迭代应以(x)0,取M1>0,a∈[2,10],令 2°以x为初始点,求解mn(x,2)得解x,其中min(x,4)由(12)确定 若 <E,计算结束,取x为(1)的最优解,否则,令M=aM-1,转到第4步 计算 +Mh,(x2),j=1…, 令k=k+1,返回第一步 上述方法是 Hestenes于1969年提出来的,故称为 Hestenes乘子法。几乎同时, Powell t提出 种乘子法,它定义的增广目标函数为: F(x,o,a)=f(x)+2oth,(x)+a12 如果在上式中取=号和a1=%,则F(x,,a)只比q(x,2)多出与x无关的一个项,故两者 本质一致。 在一定条件下,可证迭代程序至少是线性收敛的。实际计算表明,随着罚参数M的增大乘子法 产生的点列比罚函数法F(x,M)=f(x)+M∑,x)2产生的点列更快地接近x,因而乘子法 般可避免因罚参数过于增大带来的数值困难 例3考察m{x2+xx1+x2=依次用罚函数和乘子法建立x'=(025075)7的选代点列 采用罚函数法,由 196

196 =  =  +  = l j j k j k k x x f x h x 1 * *  ( , ) ( )  ( ) 0 这证明 k  是与 k x =x*对应的 Lagrange 乘子。 迭代应以 ( )   k h x 结束。若 k  收敛慢，可适当增大 M，即将（13）中的 M 换成 Mk= Mk-1,   1。这样，用上述乘子法去求解（1）的迭代步骤为： 1° 给定初始点 。 x ，初始乘子向量 （可取 1  1 = 0）， 计算精度   0 ，取 M1  0， [2,10] ，令 k=1。 2° 以 k−1 x 为初始点，求解 min ( , ) k  x  得解 k x ，其中 min (x,) 由（12）确定。 3° 若 ( )   k h x ，计算结束，取 k x 为（1）的最优解，否则，令 Mk= Mk-1,转到第 4 。步。 4° 计算 M h x j l k k j k j k j ( ), 1, ,  +1 =  + =  令 k=k+1，返回第一步。 上述方法是 Hestenes 于 1969 年提出来的，故称为 Hestenes 乘子法。几乎同时，Powell 也提出 一种乘子法，它定义的增广目标函数为： = = + + l j j j j F x f x h x 1 2 ( ,,) ( )  [ ( )  ] 如果在上式中取 2 M  j = 和 j M  j  = ，则 F(x,,)只比（x,) 多出与 x 无关的一个项，故两者 本质一致。 在一定条件下，可证迭代程序至少是线性收敛的。实际计算表明，随着罚参数 Mk 的增大乘子法 产生的点列比罚函数法 = = + l j j F x M f x M h x 1 2 ( , ) ( ) [ ( )] 产生的点列更快地接近 x*，因而乘子法一 般可避免因罚参数过于增大带来的数值困难。 例 3 考察 min  1 2 1 2 6 2 2 1 2 1 1 x + x x + x = 。依次用罚函数和乘子法建立 T x (0.25,0.75) * = 的迭代点列 k x 和 k x 。 采用罚函数法，由

(x,Mk)=x2+x2+( 用解析法可求得无约束最优解为 采用 Hestenes乘子法,则由 0(x,)=x2+x2+(x1+x2-1)2+(x1 可得 ,2 其中+=2+M4( k≥0 选取M4=0.1×2,=0,所得结果见下表: x2(罚函数法 (乘子法 0(0071402142)00714,0.2142) 10.11l,0.3330.1507,04523) 2(0.153804615)0211806355 3k(0.19040.5714)(0.2409,0.7227 4(02162,06486)(02487,0.7463) 5(02318,06959)(0.24990.7497) 6(0.2406,0.7218(0.2499,0.7499) 15(0.2499,0.7499) 从表中可见x接近x*比x接近x*的速度快得多,用乘子法迭代6次就达到了罚函数法迭代15 次的结果。这里罚参数在罚函数中要增大到M5=32768,而在乘子法中只要增大到M6=6.4, 相比之下乘子法不需要过份地增大罚参数,从而改进了罚函数法 1973年, Rockfellar将乘子法推广到解不等式约束的优化问题: f( S.g1(x)≤0,i=1 其中∫,g;(=1,…m):Rn→>R 求解它的办法是引入松驰变量y:(=1…m)将不等式约束化为等式约束 g(x)+y2=0 (16) 然后再利用前面讲述的等式约束最优化问题的结果。这时(14)式具形式

197 2 2 1 2 2 6 2 2 1 2 1 1 min F(x,M ) = x + x + (x + x −1) Mk k x 用解析法可求得无约束最优解为 ( ) T M M M k M k k k k x 1 4 3 1 4 , = + + 采用 Hestenes 乘子法，则由 min ( , ) ( 1) ( 1) 1 2 2 2 1 2 2 6 2 2 1 2 1 1 x = x + x + x + x − + x + x − M k x k    可得 ( ) T M M M k M k k k k k k x 1 4 3( 1 4 , + − + − =   ） 其中 ( 1) 1 2 1 = + + − + k k k k k   M x x k  0 选取 0.1 2 , 0 0 =   = k M k ，所得结果见下表：    (0.2499 0.7499) (0.2499 0.7497) (0.2487 0.7463) (0.2409 0.7227) 0.2118 0.6355) 0.1507 0.4523) 0.0714 0.2142) (0.2499 0.7499 (0.2406 0.7218 (0.2318 0.6959 (0.2162 0.6486) (0.1904 0.5714) (0.1538 0.4615) 0.1111 0.3333) 0.0714 0.2142 ( 15 6 5 4 3 2 1 0 ， ， ， ， （ ， （ ， （ ， （乘子法） ， ） ， ） ， ） ， ， ， （ ， （ ， ） k 罚函数法） k k x x 从表中可见 k x 接近 x*比 k x 接近 x*的速度快得多，用乘子法迭代 6 次就达到了罚函数法迭代 15 次的结果。这里罚参数在罚函数中要增大到 M15 = 3276.8 ，而在乘子法中只要增大到 M6 = 6.4， 相比之下乘子法不需要过份地增大罚参数，从而改进了罚函数法。 1973 年，Rockfellar 将乘子法推广到解不等式约束的优化问题：    st g x  i = m f x i . . ( ) 0, 1, , min ( )  （15） 其中 f , gi (i =1, m): Rn → R 求解它的办法是引入松弛变量 y (i 1, m) i =  将不等式约束化为等式约束, gi (x) yi 0 i 1, ,m + 2 = =  (16) 然后再利用前面讲述的等式约束最优化问题的结果。这时（14）式具形式

mino(x,2,y)=f(x)+∑砖(g、(x)+y2)+(g,(x)+y2)2] (17) 而(13)式变成 2 +M(g (18) 其中M4>0,Mk→>+∞(k→∞) 设法消去松弛变量y不难证明(只须令V9(x,,y)=0)(17)右端的和式中的各项,当y满 足下式时取最小值: ∫一/M,当Mg(x)+才≤0 (x),当Mg,(x)+2>0 代入(17)得 ∑{对+Mg 代入(18)得: =mx对+Mg(x)}1=1…,m (21 而结束准则可采用 (g(x3)+y1)=∑|mxgx) 对于一般非线性优化问题,可类似地推出相应结果。 有人采用异于(13)的乘子迭代公式 k-1 +=x2+Mh(x2)+ h(r)-h(r-l)n(re) (23) 在加速迭代收敛方面取得了很好的计算结果 还有把乘子表示成ⅹ的函数的,如 Polak乘子法这里就不介绍了

198 min ( , , ) ( ) [ ( ( ) ) ( ( ) ) ] 2 2 2 2 1 i i M i i k i m i k x y = f x +  g x + y + g x + y =    （17） 而（13）式变成 M g x yi i m k k i k j k j ( ( ) ) 1, ,  +1 =  + + 2 =  （18） 其中 Mk  0,Mk → + (k → ). 设法消去松弛变量 y.不难证明（只须令  (x, , y) = 0 k y  ）（17）右端的和式中的各项，当 i y 满 足下式时取最小值：    +  − +  + = ( ), ( ) 0 / , ( ) 0 ( ) 2 k i i i k i i k i i i g x Mg x M Mg x g x y    当 当 （19） 代入（17）得    2 2 1 2 1 min ( ) max 0, ( ) ( ) k i i k i m i M  = f x +   + Mg x −  = （20） 代入（18）得：  M g x  i m K k i k i k i max 0, ( ) , 1, ,  +1 =  + =  （21） 而结束准则可采用 2 1 2 2 2 1 ( ( ) ) max( ( ), )           + =  − = = m i k k i i i k i m i M g x y g x （22） 对于一般非线性优化问题，可类似地推出相应结果。 有人采用异于（13）的乘子迭代公式： ( ) ( ) ( ) ( ) 1 1 1 k k k k k k k k h x h x h x Mh x − − + − − = + +     （23） 在加速迭代收敛方面取得了很好的计算结果。 还有把乘子表示成 x 的函数的，如 Polak 乘子法这里就不介绍了