第三章等式约束的优化 §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 乘子法这里就不介绍了