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

第四章不等式约束的优化 §1、最优性条件 考虑不等式约束的优化问题。 min f(x) lst.g,(x)≤0,i=1…,m 定义1设CcR”是非空集合,若Vx∈C及≥0,有Ax∈C,则称集合C为以原点为顶点的锥 如果锥C又是凸集,则称C为凸锥 定义2设ScR”非空,是可行解集,点x∈S闭包,若对某P∈R,P≠0,存在数δ〉0,使 V∈(0,δ),均有x+∈S,则称P为点x处的可行方向。 用D表示在S中从x出发的所有可行方向向量的集合,即 D={PP≠0且存在0,∈(0。)有+∈S 称为在点x处的可行方向锥。 若记F={pv(xyPp<o,则对局部最优解来说,必有 F∩D=d (2) 这是因为在最优点x*,不可能存在下降的可行方向,反之若于某点x*已不存在下降的可行方向,则 此点一定是局部最优解。 定义3若问题(1)的一个可行点x使某个不等式约束g1≤0变成等式即g(x)=0,则该约束称 为关于x的起作用约束(紧约束),否则,即g,(x)<0则称之为不起作用约束(松约束)。 用集合/={g(x)=0x∈S}表示在可行点的紧约束指标集。 定理1设x*是问题(1)的可行点,f和g,(∈D在x*可微,g(∈D在x*连续,如果x*是局部 最优解,则 F∩Gn=d (3) 其中G0=PVg(x)P<0,∈,称Gn为S在点x*处的局部约束方向锥(或内方向锥) 证明:(略)(提示:只需证GcD) 199

199 第四章 不等式约束的优化 §1、最优性条件 考虑不等式约束的优化问题。    st g x  i = m f x i . . ( ) 0, 1, , min ( )  （1） 定义 1 设 n C  R 是非空集合，若 xC 及   0 ，有 xC ，则称集合 C 为以原点为顶点的锥。 如果锥 C 又是凸集，则称 C 为凸锥。 定义 2 设 n S  R 非空，是可行解集，点 x S 闭包，若对某 P∈R n ,P≠0,存在数δ〉0，使   (0, ) ，均有 x + p  S, 则称 P 为点 x 处的可行方向。 用 D 表示在 S 中从 x 出发的所有可行方向向量的集合，即 D = P P  0且存在〉0， （0，）有x + PS 称为在点 x 处的可行方向锥。 若记 F0 = P f (x) P  0 T ，则对局部最优解来说，必有 F0  D =  （2） 这是因为在最优点 x*，不可能存在下降的可行方向，反之若于某点 x*已不存在下降的可行方向，则 此点一定是局部最优解。 定义 3 若问题（1）的一个可行点 x 使某个不等式约束 gi  0 变成等式即 gi (x) = 0 ，则该约束称 为关于 x 的起作用约束（紧约束），否则，即 gi (x)  0 则称之为不起作用约束（松约束）。 用集合 I = i gi (x) = 0, x S 表示在可行点 x 的紧约束指标集。 定理 1 设 x*是问题（1）的可行点， f g (i I) 和 i  在 x*可微， g (i I) i  在 x*连续，如果 x*是局部 最优解，则 F0 G0 =  （3） 其中 G P g x P i I T =  i ( )  0,  * 0 ，称 G0 为 S 在点 x*处的局部约束方向锥（或内方向锥） 证明：（略）(提示:只需证 G0  D )

条件(2)和(3)均为几何最优性条件,实际计算中不好用,下面由之引出经常使用的代数最 优性条件。 定理2( Fritz-John必要条件)设x*是(1)的可行解,∫,g(∈1)在x*可微, g(D)在x*连续,如果x*是局部最优解,则存在不全为0的数u和1(i∈D)使得 avf(x)+∑uVg(x’)=0 lo,l1≥0,vi∈I 通常称(4)为 Fritz-John必要条件,满足(4)的点称为 Fritz-John点,如果g(∈D)在x*也 可微,则有 V(x)+∑uVg,(x)=0 l181(x)=0,i=1…,m l0,u2≥0,.i=1,…,m 证:因x*是(1)的局部最优解,由定理1知F∩G0=Φ,即不存在向量p∈R使得Vf(x)P<0 和vg,(x)P<0(V∈i)同时成立,若Ⅰ={,2,…l},且记 (x)Vg(x)…V8n(x 于是AP<0无解。根据 Gordan定理(第一章定理8)存在非0向量y≥0,使Ay=0记 y=(ul,l12…,u1),则有 V(x)+∑uVg(x)=0 lo≥0,l1≥0.,i∈,且不全为0 这就证明了(4)。 如果g(运D也可微,只要令u1=0、(∈D)就有改述的 Fritz-John条件(5)。(5)中的第二式 又称为互补松弛条件。 在 Fritz-John条件中,当l=0时,目标函数梯度vf(x')消失,这不利于寻找最优点。例如问 题 200

200 条件（2）和（3）均为几何最优性条件，实际计算中不好用，下面由之引出经常使用的代数最 优性条件。 定理 2（Fritz-John 必要条件） 设 x*是（1）的可行解， f ,g (i I) i  在 x*可微， g (i I) i  在 x*连续，如果 x*是局部最优解，则存在不全为 0 的数 ( ), 0 u u i I 和 i  使得         +  =  u u i I u f x u g x i i I i i , 0, ( ) ( ) 0 0 * * 0 （4） 通常称（4）为 Fritz-John 必要条件，满足（4）的点称为 Fritz-John 点，如果 g (i I) i  在 x*也 可微，则有         = = =  +  = = u u i m u g x i m u f x u g x i i i m i i i , 0, 1, , ( ) 0, 1, , ( ) ( ) 0 0 * 1 * * 0   （5） 证：因 x*是（1）的局部最优解，由定理 1 知 F0 G0 =  ，即不存在向量 n p  R 使得 ( ) 0 * f x P  T 和 ( ) 0 * g x P  T i （ i ）同时成立，若 I = i 1 ,i 2 ,  ,i k  ，且记 ( ）) * * * ( ), ( ), , ( 1 A f x g x g x k i i T =     于是 AP<0 无解。根据 Gordan 定理（第一章定理 8）存在非 0 向量 y  0 ，使 A y = 0 T 记 ( , , , ) 0 1 k u ui ui y =  ，则有 0, 0, , 0 ( ) ( ) 0 0 * * 0 u u i I 且不全为 u f x u g x i i I i i     +  =  这就证明了(4)。 如果 g (i I) i  也可微，只要令 u 0,(i I) i =  就有改述的 Fritz-John 条件（5）。（5）中的第二式 又称为互补松弛条件。 在 Fritz-John 条件中，当 u0 = 0 时，目标函数梯度 ( ) * f x 消失，这不利于寻找最优点。例如问 题

(1-x1)3≤0 在最优点x=(10)处/={2},由FJ条件,有 l 0 1)(0 成立,仅当0=0(此时可以取l1=2=a>0,a任意)。为了保证40>0,需要再加一些约束 条件,这样一些附加约束条件通常称为约東规格,约束规格可以不同,下面定理所加约束规格是最 自然的和容易想到的。 定理3( Kuhn-Tucker必要条件)设x*是问题(1)的可行解,f,g,(i∈D)在x*可微,g,(d 在x*连续,再假设Vg,(x)i∈D线性无关,如果x*是局部最优解,则存在l1≥0(∈D)使得 v(x)+∑u1Vg(x)=0 通常称(6)式为Kuhn- Tucker条件,简称KT条件,满足这个条件的点称为KT点,如果再假 定g(百D)在x*也可微,则上述KT条件可写成 V(x)+∑nVgx)=0 (7) l1g1(x)=0,=1,…,m 0,i=1, 证:由定理2知,存在0,1(∈D)使 l6V(x)+∑g(x:)=0 ≥0,Vi∈I 由于Vg(x(∈D线性无关,故必l0≠0,从而u0>0,以u0除上式并令l1=l1/o,则l1≥0, 这说明(6)成立 如果g(百D)也可微,只要令l1=0,i∈就有改述的KT条件(7)。u称为 Lagrange乘子, (7)中的第二式称为互补松弛条件 201

201      −  − −  − 0 . . (1 ) 0 min 2 3 2 1 1 x st x x x 在最优点 ( ) T x 1,0 * = 处 I = 1,2 ，由 F-J 条件，有         =        − +        +       − 0 0 1 0 1 0 0 1 u0 u1 u2 成立，仅当 u0 = 0 （此时可以取 u1 = u2 =  0， 任意）。为了保证 u0  0 ，需要再加一些约束 条件，这样一些附加约束条件通常称为约束规格，约束规格可以不同，下面定理所加约束规格是最 自然的和容易想到的。 定理 3（Kuhn-Tucker 必要条件） 设 x*是问题（1）的可行解， f , g (i I) i  在 x*可微， g (i I) i  在 x*连续，再假设 ( )( ) * g x i I  i  线性无关，如果 x*是局部最优解，则存在 u 0(i I) i   使得 ( ( ) 0 * * f x +u gi x = i ） i （6） 通常称（6）式为 Kuhn-Tucker 条件，简称 K-T 条件，满足这个条件的点称为 K-T 点，如果再假 定 g (i I) i  在 x*也可微，则上述 K-T 条件可写成         = = =  +  = = u i m u g x i m f x u g x i i i m i i i 0, 1, , ( ) 0, 1, , ( ) ( ) 0 * 1 * *   （7） 证：由定理 2 知，存在 , ( ) 0 u u i I i  使          + =  u u i I u f x u g x i i I i i , 0, ( ) ( ) 0 0 * * 0 由于 ( )( ) * g x i I  i  线性无关，故必 u0  0 ，从而 u0  0 ，以 0 u 除上式并令 0 ui = ui / u ，则 ui  0 ， 这说明（6）成立。 如果 g (i I) i  也可微，只要令 u i I i = 0,  就有改述的 K-T 条件（7）。 i u 称为 Lagrange 乘子， （7）中的第二式称为互补松弛条件

KT条件有明显的几何意义:对于任意一组n1≥0∈1),向量∑uVg(x)属于起作用约束 函数梯度向量Vg(x')i∈D)所张成的锥,由(6)知 即目标函数的负梯度向量-Vf(x)属于这个锥。 若fx)是凸函数,则K-T条件还是充分的。 定理4(KT充分条件)若∫,g1,i=1,…,m是可微凸函数,可行点x*满足K-T条件,则x*是问 题(1)的全局最优解 证:令S={:(x)0=1…,m因为g,1=1…,m为凸函数,所以S为凸集,x∈S由的 凸性,有 f(x)>f(x)+Vf(x)(x-x) 由于在点x*满足KT条件,则有u1≥0(∈1),使得 f(x)≥f(x)-∑uvg(x)(x-x) 又由于g(x)是凸函数,故又有 g(x)≥g,(x)+Vg(x')(x-x'),Vx∈S 因当i∈l时,g(x)=0,g,(x)≤0,从而g,(x)≤g(x),进而vg(x)(x-x)≤0,故 f(x)≥f(x)Vx∈S 即x*是全局最优解。 定理4的条件可以减弱,利用伪凸和拟凸的概念,仿定理4的证明有以下结果 定理5若∫是伪凸函数,g,(=1,…,m)是可微拟凸函数,可行点x*满足KT条件,则x*是问题 (1)的全局最优解 定理条件还可以减弱为f在x*点伪凸,g;(=1,…,m)在点x*可微拟凸,则相应的结论成立 对于既有等式约束又有不等式约束的一般数学规划问题(8)

202 K-T 条件有明显的几何意义：对于任意一组 u 0(i I) i   ，向量    i I i i u g (x *） 属于起作用约束 函数梯度向量 ( )( ) * g x i I  i  所张成的锥，由（6）知   −  =  i I i i f (x * ) u g (x *） 即目标函数的负梯度向量 ( ) * − f x 属于这个锥。 若 f(x)是凸函数，则 K-T 条件还是充分的。 定理 4（K-T 充分条件） 若 f , gi ,i =1,  ,m 是可微凸函数，可行点 x*满足 K-T 条件，则 x*是问 题（1）的全局最优解。 证：令 S = x gi (x)  0,i =1,  ,m 因为 gi ,i =1,  ,m 为凸函数，所以 S 为凸集， xS,由f 的 凸性，有 ( ) ( ) ( ) ( ) * * * f x f x f x x x T  +  − 由于在点 x*满足 K-T 条件，则有 u 0(i I) i   ，使得 ( ) ( ) ( ) ( ) * * * f x f x u g x x x T i i i I  −   −  又由于 g (x) i 是凸函数，故又有 g x g x g x x x x S T i ( )  i ( ) +  i ( ) ( − ) ,   * * * 因当 i I 时， ( ) 0, ( ) 0 * gi x = gi x  ，从而 ( ) ( ) * g x g x i  i ，进而 ( ) ( ) 0 * * g x x − x  T i ，故 f (x)  f (x ) x  S * 即 x*是全局最优解。 定理 4 的条件可以减弱，利用伪凸和拟凸的概念，仿定理 4 的证明有以下结果。 定理 5 若 f 是伪凸函数， g (i 1, ,m) i =  是可微拟凸函数，可行点 x*满足 K-T 条件，则 x*是问题 （1）的全局最优解。 定理条件还可以减弱为 f 在 x*点伪凸， g (i 1, ,m) i =  在点 x*可微拟凸，则相应的结论成立。 对于既有等式约束又有不等式约束的一般数学规划问题（8）：

min f(x) g,(x)≤0, h,(x)=0, 只需令L(x,)=f(x)+∑b(x),然后考虑 1.g(x)≤0, 便会得到与定理2、3的相应结果,下面仅叙述相应的KT条件。 定理6(KT必要条件)设x*是问题(8)的可行解,J,g,(=1…,m),h(=1…,D)可微,再 假设Vg(x∈D和Vh(x)j=1,…线性无关,如果x是局部最优解则存在 0=1…,m)及x(=1…D,使得 )+Vg:(x)+∑Vh(x)=0 (9) igi 若问题是凸规划则亦可证KT条件是充分的。 可把 Botsko改进条件用于(1),有结果 定理7假定V(x)于O(x,5)/x上连续且0与(x)vmiI如果条件 af(x) 成立其中x=(x1,…x1,x1,x+1…xn)是可行解域,则x是问题(1)的严格局部最优解 证明:由 Taylor公式 f(x')=f(x)+V/(x)'(x-x)+o(x'-x 可有 f(x)=f(x)+∑(x (x;-x,) af(x)af(x) )+ (11) 当xx∈O(x,。)/x∩S且δ充分小时由于Vf(x)的连续性故有

203      = =  = h x j l st g x i m f x j i ( ) 0, 1, , . . ( ) 0, 1, , min ( )   （8） 只需令 = = + l j j j L x f x h x 1 ( ,) ( )  ( ) ，然后考虑 st g x i m L x . . i ( ) 0, 1, min ( , )  =  便会得到与定理 2、3 的相应结果，下面仅叙述相应的 K-T 条件。 定理 6（K-T 必要条件） 设 x*是问题（8）的可行解， f , g (i 1, ,m) i =  , h ( j 1, ,l) j =  可微，再 假设 ( ( ) * g x i I  i ）  和 h x j l j ( ) 1, ,  * =  线性无关，如果 * x 是局部最优解,则存在 u 0(i 1, ,m) i  =  ( j 1, ,l) 及 j =  ，使得      = =  +  +  = = = u g x i m f x u g x h x i i m i l j i i j j ( ) 0, 1, , ( ) ( ) ( ) 0 * 1 1 * * *   （9） 若问题是凸规划则亦可证 K-T 条件是充分的。 可把 Botsko 改进条件用于(1),有结果: 定理 7 假定 f (x) 于 * * (x , )/ x 上连续,且 0 ) (   * lim → x f x x .如果条件  =    − i n x x f x x x i i i i 0, 1, , ( ) ( ) ( ) *  * * (x , )/ x  S (10) 成立,其中 ( , , , , ) * * 1 * 1 * 1 ( ) i i i n i x x x x x x = − + ,S 是可行解域,则 * x 是问题(1)的严格局部最优解. 证明:由 Taylor 公式: ( ) ( ) ( ) ( ) ( ) * * * f x f x f x x x x x T = +  − +  − 可有 ) ( ) ( ) ( ) (x )( ( ) ( ) ( ) (x ) * n ( ) i 1 * i n ( ) i 1 * i * x x x f x x f x x x f x f x f x x i i i i i i i + −   −   − −   = +  −  = =  (11) 当 x,x (i)  * * (x , )/ x  S 且  充分小时,由于 f (x) 的连续性,故有

o(x)0(x)20=1.n 从而(1)式右边第三项亦是|-的高阶无穷小故(1)可写成 f(x)=f(x)+ 2 (x)+ (12) ax 其中第二项由于假定0(xmil,故其不是|-x的高阶无穷小且由于(10)成立故必有 f(x)<f(x),x∈O(x,o)/x∩s 这说明x是问题(1)的严格局部最优解,即在上述条件下、10)是取极值的充分条件 §2、可行方向法 最早的可行方向法是1960年由G、 Zoutendijk提出的,现在可行方向法已发展成求解约束优化 问题的一类重要方法。其基本思想是:在给定一个可行点x之后,用某种办法确定一个改进的可行 方向S,然后沿S求解一个有约束的线搜索问题,得极小点2,令x41=x+AS。若x仍不 是最优解,则重复上述步骤。各种不同的可行方向法的主要区别在于:选择可行方向sk的策略不同 大体可分为三类 1)用求解一个线性规划问题来确定S,如 Frank--Wole方法, Zoutendijk方法等 2)利用投影矩阵直接来构造一个改进可行方向S,如 Rosen投影梯度法 3)利用既约梯度直接构造出一个改进的可行方向Sk,如 Wolfe既约梯度法及其各种改进。 下面介绍其中的几种: 1° Frank-Wolfe方法 考虑非线性规划问题 min f(x) st.Ax≤b (13) Bx= d 其中A和B分别是m×n和×n阶矩阵,且B是行满秩的 b和d分别是m和1维列向量,令

204 lim * x→x i i i x f x x f x   −   ( ) ( ) ( ) =0,i=1, n 从而(11)式右边第三项亦是 x − x * 的高阶无穷小,故(11)可写成 ( ) ( ) ( ) ( ) (x ) * n ( ) i 1 * i * x x x f x f x f x x i i i + −   = +  − =  (12) 其中第二项由于假定 0 ) (   * lim → x f x x ,故其不是 x − x * 的高阶无穷小,且由于(10)成立,故必有 ( ) ( ), * f x  f x x * * (x , )/ x  S 这说明 * x 是问题(1)的严格局部最优解,即在上述条件下,(10)是取极值的充分条件. §2、可行方向法 最早的可行方向法是 1960 年由 G、Zoutendijk 提出的，现在可行方向法已发展成求解约束优化 问题的一类重要方法。其基本思想是：在给定一个可行点 x k 之后，用某种办法确定一个改进的可行 方向 S k，然后沿 S k 求解一个有约束的线搜索问题，得极小点 k  ,令 k k k k x = x +  S +1 。若 k+1 x 仍不 是最优解，则重复上述步骤。各种不同的可行方向法的主要区别在于：选择可行方向 S k 的策略不同， 大体可分为三类： 1) 用求解一个线性规划问题来确定 S k，如 Frank---Wolfe 方法，Zoutendijk 方法等。 2） 利用投影矩阵直接来构造一个改进可行方向 S k ,如 Rosen 投影梯度法。 3） 利用既约梯度直接构造出一个改进的可行方向 S k ,如 Wolfe 既约梯度法及其各种改进。 下面介绍其中的几种： 1°Frank—Wolfe 方法 考虑非线性规划问题      =  Bx d st Ax b f x . . min ( ) （13） 其中 A 和 B 分别是 m n和l  n 阶矩阵，且 B 是行满秩的。 b 和 d 分别是 m 和 l 维列向量，令

S=4x≤b,Bx=d,x∈Ry 表可行域,假定f(x)在包含S的某个开集D上是连续可微的函数 任取一初始可行点x∈S,在x处以f(x)的-阶 Taylor展开式作为f(x)的线性逼近函数: F(x)=f(x)+Vf(x)(x-x 求线性规划问题 的解显然等价于求解线性规划问题: min Vf(x)x (14) 为了保证(11)有有限解,假设对于任意可行点x∈S,线性函数vf(x)x在S上有下界 令(14)的最优解为y,下面分两种情形讨论。 )若Vf(x2)(y-x)=0,即x也是(14)的最优解,则迭代停止 2)若Vf(x2)(y2-x)≠0,此时必有 Vf(x)( )<0 则由第二章定理2,(y-x°)是∫(x)在x点的下降方向,又因y∈S,x∈S,且S为凸集,故 x+A(y-x)∈S(0<λ<1),从而y-x是可行方向。因此,从x出发,沿此方向进行一维搜 索,即求 min f(x+a (y-x)) 0<A<l 的最优解λ,令x=x+(y-x),则x是x与y连线上f(x)的最小值,且x3∈S,当A足 够小时有 f(x)≤f(x*+λ(y-x) =f(x)+avf(x)(y-x)+o xp<f(x) 得到x之后,再于x处线性逼近∫(x),重复上述步骤 注意:(14)是线性的,K-T条件中不含x,但是不同的x因松紧性不同,故有别。即只有最优解xk

205   n S = x Ax  b, Bx = d, x  R 表可行域，假定 f (x) 在包含 S 的某个开集 D 上是连续可微的函数。 任取一初始可行点 x  S 。 ，在 。 x 处以 f (x) 的一阶 Taylor 展开式作为 f (x) 的线性逼近函数： F（x）= f (x 。）+ f（x 。）（T x − x 。） 求线性规划问题 min F(x) xS 的解显然等价于求解线性规划问题： f x x T x S min  ( 。）  （14） 为了保证（11）有有限解，假设对于任意可行点 x  S 。 ，线性函数 f x x 。）T  ( 在 S 上有下界。 令（14）的最优解为 。 y ，下面分两种情形讨论。 1） 若  ( ）( − ）= 0 。 。 。 f x y x T ，即 。 x 也是（14）的最优解，则迭代停止。 2） 若  ( ）( − ） 0 。 。 。 f x y x T ，此时必有  ( ）( − ） 0 。 。 。 f x y x T 则由第二章定理 2， (y 。 − x 。） 是 f (x) 在 。 x 点的下降方向，又因 y  S x  S 。 。 , ，且 S 为凸集，故 x + (y − x） S(0    1) 。 。 。 ，从而 。 。 y − x 是可行方向。因此，从 。 x 出发，沿此方向进行一维搜 索，即求 f x 。 + （y 。 − x 。））     min ( 0 1 的最优解  ，令 x 1 = x 。 + （y 。 − x 。） ，则 x 1是 x 。与 y 。连线上 f (x) 的最小值，且 x  S 1 ，当  足 够小时有 ( ) ( ) f x 1  f x 。 + （y 。 − x 。） ( ) ( ( ) 。 。）（ 。 。） （ 。 。） 。 f x f x y x o y x f x T = +  − +  −  得到 x 1 之后，再于 x 1 处线性逼近 f (x) ，重复上述步骤。 注意：（14）是线性的，K-T 条件中不含 x，但是不同的 x 因松紧性不同，故有别。即只有最优解 x k

才与(13)有相同的KT条件 关于FW方法的收敛判别准则,有如下定理 定理8若(11最优解y满足Vf(x)(y2-x2)=0,则x是原问题(13)的KT点。 证:显然,此时x是(14)的最优解,从而也必是(14)的KT点,由(14)与(13)有相同的KT 条件,立即可知x是(13)的一个KT点。证毕。 F-W方法虽然收敛较慢,但由于迭代求解的每一线性子规划(14)都具有相同约束条件(即可 行域相同),因此可用灵敏度分析的手段处理一系列子规划问题(相当于目标函数系数变化→检验 数变化)这样,效果还是较好的 2° Zoutendijk可行方向法 对于问题(13)先介绍一个确定下降可行方向的充要条件: 定理9设x是(13)的可行解,在x点有Ax=b,4x<b,其中/≤/ A b么则非0向量S是点x处的可行方向的充要条件是 A1S≤0 (15) 证明:(简单从略) 由第二章定理2知,为使S又是下降方向,这需满足 (16) 因此在一点x0的下降方向可通过解下列线性规划问题来求得 min Vf(x s A1S≤0 st BS=0 (17) -1≤S,≤1j=1…,n 这里加约束-1≤s,≤1(j=1,…,n)是为了获得一个有限解,因若存在满足(15)和(16),则对 206

206 才与（13）有相同的 K-T 条件。 关于 F-W 方法的收敛判别准则，有如下定理： 定理 8 若(11)的最优解 y k 满足  ( ）( − ）= 0 k T k k f x y x ，则 k x 是原问题（13）的 K-T 点。 证：显然，此时 k x 是（14）的最优解，从而也必是(14)的 K-T 点，由（14）与（13）有相同的 K-T 条件，立即可知 k x 是（13）的一个 K-T 点。证毕。 F-W 方法虽然收敛较慢，但由于迭代求解的每一线性子规划（14）都具有相同约束条件（即可 行域相同），因此可用灵敏度分析的手段处理一系列子规划问题（相当于目标函数系数变化  检验 数变化）这样，效果还是较好的。 2° Zoutendijk 可行方向法 对于问题（13）先介绍一个确定下降可行方向的充要条件： 定理 9 设 x 。是（13）的可行解，在 x 。点有 1 1 2 2 A x = b , A x  b   ，其中         = 2 1 A A A ，         = 2 1 b b b ，则非 0 向量 S 0 是点 x 。处的可行方向的充要条件是： 0 , 0 0 0 A1S  BS = （15） 证明：（简单从略） 由第二章定理 2 知，为使 S 0 又是下降方向，这需满足 ( ) 0 0 0 f x S  T - （16） 因此在一点 x 0 的下降方向可通过解下列线性规划问题来求得      −   = =   S j n BS A S st f x S j 1 1 1, , 0 0 . . min ( ) 1 0  （17） 这里加约束 1 s 1( j 1, ,n) −  j  =  是为了获得一个有限解，因若存在 S 满足（15）和（16），则对

任意λ>0,AS亦满足这些条件,进而导致(17)目标函数无下界,无法确定有限解 在问题(1⑦)中,由于S=0是可行解,故最优值必定小于或等于0;若小于0,则最优解即为下 降可行方向:若等于0,则以下定理保证x0是KT点 定理10在无约束问题中,设x是可行解,且Ax°=b1,A2x°0,无解。即 B AS≤0,BS=0,Vf(x°)S<0无解,这等价于问题(17)的最优目标函数值等于0。所以x是 KT点的充要条件是(17)的最优值为0。证毕 求得第k步迭代的下降可行方向S后,其最优步长λk应满足 min f(x+2S") A(x+AS)≤b B(x+1S^)=d 由此出发不难推出(定理9)步长k可由如下有约束的一维搜索求得 min f(x+2S") 0≤A≤A 其中 207

207 任意   0,S 亦满足这些条件，进而导致（17）目标函数无下界，无法确定有限解 S. 在问题（17）中，由于 S=0 是可行解，故最优值必定小于或等于 0；若小于 0，则最优解即为下 降可行方向；若等于 0，则以下定理保证 x 0 是 K-T 点。 定理 10 在无约束问题中，设 x 0 是可行解，且 2 0 1 2 0 1 A x = b , A x  b ，其中，         = 2 1 A A A ，         = 2 1 b b b ，则 x 0 为 K-T 点的充要条件是问题（17）的目标函数等于 0。 证：注意到问题（13）是线性约束问题，依定义，x 0 为 K-T 点等价于存在向量 u  0 和 v ，使得 ( ) 0 T 1 0 f x + A u + B v = T 令向量 v = p − q,其中p  0,q  0, 于是 ( , , ) ( ), 0 0 1            = −           − q p u f x q p u A B B T T T 依 Farkas 定理，这个系统有解的充要条件是 0 1            − S B B A ， ( ) 0 0 − f x S  T ，无解。即 0, 0, ( ) 0 0 A1S  BS = f x S  T 无解，这等价于问题（17）的最优目标函数值等于 0。所以 x 0 是 K-T 点的充要条件是（17）的最优值为 0。 证毕。 求得第 k 步迭代的下降可行方向 S k 后，其最优步长 k 应满足 B x S d A x S b f x S k k k k k k + = +  + ( ) ( ) min ( )     由此出发不难推出（定理 9）步长 k 可由如下有约束的一维搜索求得 0 max min ( )      + k k f x S 其中

+ 当v≤0 b2-A2x>0 V=A,S 对于非线性约束问题(1),我们知道,如果 vf(x)ys<0,vg(x")s<0,v∈={g(x)=0}(18) 则S是下降可行方向 为求满足(18)的S,可解如下线性规划问题 mmn二 Vf(x3)S-z≤0 (x2)S (19) l≤S,≤1,j=1,…,m (19)是由 Zoutendijk首先提出,后来由 Topkis和 Vein等加以修正的可行方向法,可证由这种 算法产生的点列的任一聚点都是 Frita-John点。然后再验证(10)式成立,即知其为最优解。其特点 是在确定移动方向时,无论起作用约束和不起作用约東都用上了,从而不致于在达到不起作用约束 边界时,会使方向发生突然的变化 、 Rosen投影梯度法 这是 Rosen在1960年针对线性约束的优化问题(13)首先提出来的,后来他又将该法推广到非 线性约束情况,现已成为求解非线性规划的一类重要的有效方法 梯度投影法的基本思想是,当迭代点x在可行域内部时,取S*=-Vf(x2)为迭代方向,当作 无约束情形处理,当点x在可行域边界上而且负梯度指向可行域的外界时,就改变方向沿梯度在边 界上的投影搜索,使之成为可行方向,下边就问题(13)进行讨论。 设x是间题(13)的一个可行解,且使Ax=b,A2x<b2,这里A=/4 b 208

208          = = −       +           = k k i i i v A S u b A x v v v v u 2 2 2 max 0 0 min 0 0 当 当  对于非线性约束问题（1），我们知道，如果 ( ) 0, ( ) 0 ,  ( ) 0 0 0 0 f x S  g x S  i  I = i gi x = T i T （18） 则 S 是下降可行方向。 为求满足（18）的 S，可解如下线性规划问题      −   =  −  − =  −  S j m g x S z g x i m f x S z st z j k i k T i k T 1 1, 1, , ( ) ( ), 1, , ( ) 0 . . min   (19) (19)是由 Zoutendijk 首先提出，后来由 Topkis 和 Veino 等加以修正的可行方向法，可证由这种 算法产生的点列的任一聚点都是 Frita-John 点。然后再验证（10）式成立，即知其为最优解。其特点 是在确定移动方向时，无论起作用约束和不起作用约束都用上了，从而不致于在达到不起作用约束 边界时，会使方向发生突然的变化。 §3、Rosen 投影梯度法 这是 Rosen 在 1960 年针对线性约束的优化问题（13）首先提出来的，后来他又将该法推广到非 线性约束情况，现已成为求解非线性规划的一类重要的有效方法。 梯度投影法的基本思想是，当迭代点 k x 在可行域内部时，取 ( ) k k S = −f x 为迭代方向，当作 无约束情形处理，当点 k x 在可行域边界上而且负梯度指向可行域的外界时，就改变方向沿梯度在边 界上的投影搜索，使之成为可行方向，下边就问题（13）进行讨论。 设 x 是问题（13）的一个可行解，且使 1 1 2 2 A x = b , A x  b ，这里         = 2 1 A A A ，         = 2 1 b b b ，设