第1节最优性条件 Vg, g1 V62(X*) R Vf(r)!r Vg, (x*) X (X)=0 Vf(X*) g2 图7-2 图73 如上类推,可以得到 (x)-∑,(X)= 清华大学出版社
第1节 最优性条件 * * ( ) ( ) 0 j j j J f X g X − = 图7-2 如上类推，可以得到 图7-3 清华大学出版社
第1节最优性条件 为了把不起作用约束也包括进式(79)中,增加条件 y81(x)=0 ≥0 当g(X)=0时,y可不为零;当g(x)≠0时,必有y=0 如此即可得到著名的库恩一塔克(Kuhn- Tucker,筒写为K-T)条件。 库恩一塔克条件是非线性规划领域中最重要的理论成果之一,是确定 某点为最优点的必要条件。只要是最优点(而且该点起作用约束的梯度线性 无关。满足这种要求的点称为正则点),就必须满足这个条件。但一般说它 并不是充分条件,因而满足这个条件的点不一定就是最优点(对于凸规划, 它既是最优点存在的必要条件,同时也是充分条件)。 清华大学出版社
第1节 最优性条件 * ( ) 0 0 j j j g X = * ( ) 0 j g X = j * ( ) 0 j g X 0 j = 为了把不起作用约束也包括进式(7-9)中，增加条件 当 时， 可不为零；当 时，必有 如此即可得到著名的库恩－塔克(Kuhn－Tucker,简写为K-T)条件。 库恩－塔克条件是非线性规划领域中最重要的理论成果之一，是确定 某点为最优点的必要条件。只要是最优点(而且该点起作用约束的梯度线性 无关。满足这种要求的点称为正则点)，就必须满足这个条件。但一般说它 并不是充分条件，因而满足这个条件的点不一定就是最优点(对于凸规划， 它既是最优点存在的必要条件，同时也是充分条件)。 清华大学出版社
第1节最优性条件 库恩-塔克条件: 设Ⅹ*是非线性规划(7-3)式的极小点,而且在X*点的各起作用 约束的梯度线性无关,则存在向量r=(1,y2…),使下述条件成立: V(x)∑rVg/(X)=0 78/(X)=0,j=1,2,… 0(7-10) ≥0 j=1,2,…1 条件(7-10)式常简称为K-T条件。满足这个条件的点(它当然也满足非线 性规划的所有约束条件)称为库恩塔克点(或KT点 清华大学出版社
第1节 最优性条件 * * * * T 1 2 ( , , , )l = * * * 1 * * * ( ) ( ) 0 ( ) 0, 1,2, , 0, 1,2, , l j j j j j j f X g X g X j l j l = − = = = = 库恩-塔克条件： 设X*是非线性规划(7-3)式的极小点，而且在X*点的各起作用 约束的梯度线性无关，则存在向量 ，使下述条件成立： 条件(7-10)式常简称为K-T条件。满足这个条件的点(它当然也满足非线 性规划的所有约束条件)称为库恩-塔克点(或K-T点)。 (7-10) 清华大学出版社
第1节最优性条件 现考虑带有等约束非线性规划(7-1)式的库恩一塔克条件,我们用 -(X)≥0代替约束条件(X)=0 h(X)≥0 即可使用条件(7-10),得到库恩塔克条件如下: 设X*是非线性规划(7-1)式的极小点,而且X*点的所有起作用约束的梯度 Vh1(x')=12…m)和Vg,(X∈)线性无关,则存在向量 A=(1,22…n)和r=( Vx)∑w(x)2g(X)=0 使下述条件成立:8(X)=0=12… 00(7-11) y20 j=1,2, (7-10)式和(7)试中的A,1…m以及x六…称为广义拉格朗日乘子 清华大学出版社
第1节 最优性条件 ( ) 0 ( ) 0 i i h X h X − ( ) 0 i h X = * ( )( 1,2, , ) i = h X i m * ( )( ) j g X j J * * * * T * * * * T 1 2 1 2 = = (λ ,λ ,λ ) ( , , , ) 和 m l * * * * * 1 1 * * * ( ) λ ( ) ( ) 0 ( ) 0, 1, 2, , 0, 1, 2, , m m i i j j i j j j j f X h X g X g X j l j l = = − − = = = = * * * 1 1 λ , λ , ,λm * * * 1 1 , , , l 现考虑带有等约束非线性规划(7-1)式的库恩－塔克条件，我们用 代替约束条件 即可使用条件(7-10)，得到库恩-塔克条件如下： 设X*是非线性规划(7-1)式的极小点，而且X*点的所有起作用约束的梯度 和 线性无关，则存在向量 使下述条件成立： (7-10)式和(7-11)式中的 以及 称为广义拉格朗日乘子。 (7-11) 清华大学出版社
第1节最优性条件 例1用库恩一塔克条件解非线性规划 ∫mif(x)=(x-3)2 0≤x≤5 解:先将该非线性规划问题写成以下形式 min f(x)=(x-3) 81(x)=x≥0 g2(x)=5-x20 写出其目标函数和约束函数的梯度 vf(x)=2(x-3) g1(x)=1,Vg2(x)=-1 对第一个和第二个约束条件分别引入广义拉格朗日乘子,设KT点为X*, 则可以得到该问题的K-T条件。 清华大学出版社
第1节 最优性条件 2 min ( ) ( 3) 0 5 f x x x = − 2 1 2 min ( ) ( 3) ( ) 0 ( ) 5 0 f x x g x x g x x = − = = − 1 2 ( ) 2( 3), ( ) 1, ( ) 1 f x x g x g x = − = = − 例1 用库恩－塔克条件解非线性规划 解： 先将该非线性规划问题写成以下形式 写出其目标函数和约束函数的梯度： 对第一个和第二个约束条件分别引入广义拉格朗日乘子，设K-T点为X*， 则可以得到该问题的K-T条件。 清华大学出版社