第8章约束极值问题 第1节最优性条件 第2节二次规划 第3节可行方向法 ■第4节制约函数法 清华大学出版社
第8章 约束极值问题 ◼第1节 最优性条件 ◼第2节 二次规划 ◼第3节 可行方向法 ◼第4节 制约函数法 清华大学出版社
第1节最优性条件 大多数极值问题其变量的取值都会受到一定限制,这种限制由约束 条件来体现。带有约束条件的极值问题称为约束极值问题。非线性 规划的一般形式为 min f(X h(X)=0,i=1,2…,m 00(7-1) g,(X)≥0,j=1,2,…,l 或 f(X) 8(X)≥0,j=1,2, 0(7-2) 问题(7-2)也常写成 minf(X),X∈RcEn 1R={x(x)≥0j=12… 0(7-3) 清华大学出版社
第1节 最优性条件 min ( ) ( ) 0, 1,2, , ( ) 0, 1,2, , i j f X h X i m g X j l = = = min ( ) ( ) 0, 1,2, , j f X g X j l = min ( ), ( ) 0, 1,2, , j f X X R En R X g X j l = = 大多数极值问题其变量的取值都会受到一定限制，这种限制由约束 条件来体现。带有约束条件的极值问题称为约束极值问题。非线性 规划的一般形式为 或 问题(7-2)也常写成 (7-1) (7-2) (7-3) 清华大学出版社
第1节最优性条件 11起作用约束和可行下降方向的概念 现考虑上述一般非线性规划,假定(1、h(X和(X)1=12…m,/=12,… 具有一阶连续偏导数。 设ⅹ媞非线性规划的一个可行解。现考虑某一不等式约束条件 g/(X)≥0 x满足它有两种可能:其一为8(X)>0这时,点xo 不是处于由这一约束条件形成的可行域边界上,因而这一约束对x 点的微小摄动不起限制作用,从而称这个约束条件是X 点的不起作用约束或无效约束);其二是8(X)=0,这时Xo 点处于该约束条件形成的可行域边界上,它对x0 的摄动起到了某种限制作用,故称这个约束是X0) 点的起作用约束(有效约束) 显而易见,等式约束对所有可行点来说都是起作用约束。 清华大学出版社
第1节 最优性条件 ( )( 1,2, , ; 1,2, , ) j g X i m j l = = (0) X ( ) 0 j g X (0) X ( ) 0 j g X (0) X (0) X (0) X (0) g Xj ( ) 0 = (0) X (0) X (0) X 1.1 起作用约束和可行下降方向的概念 现考虑上述一般非线性规划，假定f(X)、hi (X)和 具有一阶连续偏导数。 设 是非线性规划的一个可行解。现考虑某一不等式约束条件 满足它有两种可能：其一为 ，这时，点 不是处于由这一约束条件形成的可行域边界上，因而这一约束对 点的微小摄动不起限制作用，从而称这个约束条件是 点的不起作用约束(或无效约束)；其二是 ，这时 点处于该约束条件形成的可行域边界上，它对 的摄动起到了某种限制作用，故称这个约束是 点的起作用约束(有效约束)。 显而易见，等式约束对所有可行点来说都是起作用约束。 清华大学出版社
第1节最优性条件 假定0是非线性规划(7-3)式的一个可行点,现考虑此点的 某一方向D,若存在实数A0>0,使对任意∈[0]均有 X0)+D∈R 就称方向D是X0点的一个可行方向。 清华大学出版社
第1节 最优性条件 0 λ 0 λ0,λ0 (0) X D R + λ 假定X (0)是非线性规划(7-3)式的一个可行点，现考虑此点的 某一方向D，若存在实数 ，使对任意 均有 就称方向D是X (0)点的一个可行方向。 清华大学出版社
第1节最优性条件 若D是可行点X处的任一可行方向,则对该点的所有起作用约束 8(X)≥0 ⑩(7-5) 均有 g1(X)=0 g(X0)D≥0,j∈J vg2(Xo) 其中/为这个点所有起作用约束下标的集合。 R 另一方面,由泰勒公式 g(X0+D)=g,(X0)+g,(X0)D+0(0) Vg, (Xo) 对所有起作用约束,当心>0足够小时,只要 g(X0)D>0,j∈J⑩(7-6)g2(x)=0 就有8(X+AD)≥0,j∈J 图7-1 此外,对XO)点的不起作用约束,由约束函数的连续性,当入>0足够小时亦有 上式成立。从而,只要方向D满足(7-6)式,即可保证它是X0点的可行方向。 清华大学出版社
第1节 最优性条件 ( ) 0 j g X (0) T ( ) 0, j g X D j J (0) (0) (0) T ( λ ) ( ) λ ( ) (λ) j j j g X D g X g X D o + = + + (0) T ( ) 0, j g X D j J (0) ( λ ) 0, j g X D j J + 若D是可行点X(0)处的任一可行方向，则对该点的所有起作用约束 均有 其中J为这个点所有起作用约束下标的集合。 另一方面，由泰勒公式 对所有起作用约束，当λ>0足够小时，只要 就有 此外，对X(0)点的不起作用约束，由约束函数的连续性，当λ>0足够小时亦有 上式成立。从而，只要方向D满足(7-6)式，即可保证它是X(0)点的可行方向。 图7-1 （7-5） （7-6） 清华大学出版社