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

第三章等式约束的优化 §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(x12=x2 x32=2+√3) 再检验条件(10) (x1-x2)1+2x3) -1+√3)5-23 lim 1>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*，同时应有