第1节最优性条件 该问题的KT条件为:(n 2x-3)-n+n2=0 0 712(5-x)=0 y1,y2 0 为解上述方程组,考虑以下几种情形 (1)令n≠0.,2≠0,无解 (2)令x≠0,n=0,解之,得x=0,x=-6,不是KT点 (3)令1=0,y2≠0,解之,得x=5,y2=-4,不是KT点。 (4)令n=n2=0,解之,得x=3,此为KT点,其目标函数值f(x)=0 由于该非线性规划问题为凸规划,故x=3就是其全局极小点。该点 是可行域的内点,它也可直接由梯度等于零的条件求出 清华大学出版社
第1节 最优性条件 该问题的K-T条件为： * * * 1 2 * * 1 * * * 1 2 * * 1 2 2( 3) 0 0 (5 ) 0 ³, 0 x x x − − + = = − = * * 1 2 0, 0 * * 1 2 = 0, 0 * * 1 x = = − 0, 6 * * 1 2 = 0, 0 * * 2 x = = − 5, 4 * * 1 2 = = 0 * x = 3 * f x( ) 0 = * x = 3 为解上述方程组，考虑以下几种情形： (1) 令 (2) 令 ，解之，得 ，不是K-T点。 (3) 令 ，解之，得 ，不是K-T点。 (4) 令 ，解之，得 ，此为K-T点，其目标函数值 由于该非线性规划问题为凸规划，故 就是其全局极小点。该点 是可行域的内点，它也可直接由梯度等于零的条件求出。 ，无解。 清华大学出版社
第2节二次规划 若非线性规划的目标函数为自变量X的二次函数,约束条件全是线 性的,称这种规划为二次规划。二次规划的数学模型为: mif(x)=∑cx+∑∑ =1k=1 C/x(712 C k=1,2,…n (7-13) ∑ax+b≥0,1=12,…m (7-14) ≥0 (7-12)式右端的第二项为二次型。如果该二次型正定(或半正定),则目标 函数为严格凸函数(或凸函数);此外,二次规划的可行域为凸集,因而, 上述规划属于凸规划。第6章已指岀:凸规划的局部极值即为全局极值。 对于这种问题,库恩-塔克条件不但是极值点存在的必要条件,而且也是 充分条件。 清华大学出版社
第2节 二次规划 若非线性规划的目标函数为自变量X的二次函数，约束条件全是线 性的，称这种规划为二次规划。二次规划的数学模型为： 1 1 1 1 1 min ( ) 2 , 1, 2, , 0, 1, 2, , 0, 1, 2, , = = = = = + = = + = = n n n j j j k j k j j k j k k j n i j j i j j f X c x c x x c c k n a x b i m x j n (7-12)式右端的第二项为二次型。如果该二次型正定(或半正定)，则目标 函数为严格凸函数(或凸函数)；此外，二次规划的可行域为凸集，因而， 上述规划属于凸规划。第6章已指出：凸规划的局部极值即为全局极值。 对于这种问题，库恩-塔克条件不但是极值点存在的必要条件，而且也是 充分条件。 （7-12） （7-13） （7-14） 清华大学出版社
第2节二次规划 将库恩一塔克条件(7-10)式中的第一个条件应用于二次规划(7-12) 式至(7-14)式,并用y代替库恩-塔克条件中的γ,即可得到 ∑cx+∑a,y+y1=c,j=1,2…n(715) 在(7-13试式中引入松弛变量Xn+,(7-13)式即变为(假定b20) ∑a1x1-xm+b=0,=12…m (7-16) 再将库恩一塔克条件中的第二个条件应用于上述二次规划,并考虑 到(7-16)式,这就得到 xy=0.,j=1,2,…,n+m (7-17) 此外还有x20,y≥0,j=12,,n+m (7-18) 清华大学出版社
第2节 二次规划 1 1 , 1,2, , + = = − + + = = n m j k k i j n i j j k i c x a y y c j n n i x + 0 i b 1 0, 1,2, , + = − + = = n i j j n i i j a x x b i m 将库恩－塔克条件(7-10)式中的第一个条件应用于二次规划(7-12) 式至(7-14)式，并用y代替库恩-塔克条件中的γ，即可得到 在(7-13)式中引入松弛变量 ，(7-13)式即变为(假定 ) （7-16） （7-15） 0, 1,2, , j j x y j n m = = + 0, 0, 1,2, , j j x y j n m = + 再将库恩－塔克条件中的第二个条件应用于上述二次规划，并考虑 到(7-16)式，这就得到 此外还有 （7-18） （7-17） 清华大学出版社
第2节二次规划 联立求解(7-15)式和(7-16)式,如果得到的解也满足(7-17)式和(7-18)式,则 这样的解就是原二次规划问题的解。但是,在(7-15)式中,c可能为正,也 可能为负。为了便于求解,先引入人工变量z(z≥0),其前面的符号可取正 或负,以便得出可行解),这样(7-15)式就变成 ∑aJm+y-∑cx+sg(c,)==c,j=12 (7-19) 其中sgn(c)为符号函数,当20时,Sgn(c)=1;当=<0 时,Sgn(c)=-1。这样一来,可立刻得到初始基本可行解如下 2=Sgn(c)c,j=1,2,…n i=1.2.…m 0, =1,2 =0. j=1,2,…,n+m 清华大学出版社
第2节 二次规划 1 1 sgn( ) , 1,2, , + = = + − + = = m n i j n i j j k k j j j i k a y y c x c z c j n sgn( )j c 0 j z sgn( ) 1 j c = 0 j z sgn( ) 1 j c = − sgn( ) , 1,2, , , 1,2, , 0, 1,2, , 0, 1,2, , j j j n i i j j z c c j n x b i m x j n y j n m + = = = = = = = = + 联立求解(7-15)式和(7-16)式，如果得到的解也满足(7-17)式和(7-18)式，则 这样的解就是原二次规划问题的解。但是，在(7-15)式中，cj可能为正，也 可能为负。为了便于求解，先引入人工变量zj (zj≥0) ，其前面的符号可取正 或负，以便得出可行解)，这样(7-15)式就变成了 （7-19） 为符号函数，当 时， ；当 时， 。这样一来，可立刻得到初始基本可行解如下： 其中 清华大学出版社