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

第四章不等式约束的优化 §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) 的连续性,故有