第2章 最優(yōu)化的基本理論和基本方法 最優(yōu)性條件 22 有約束優(yōu)化(第5次課 等式約束優(yōu)化,作業(yè)問題講解)

1、第2章最優(yōu)化的基本理論和基本方法2 有約束最優(yōu)化問題：min f(x), xRn (2-1) st ci(x1, x2, ., xn) = 0, i E ci(x1, x2, ., xn) 0, i I其中E和I分別表示等式和不等式約束的指標集, E= 1, 2, ., l I= l +1, l +2, ., l +m E I = （空集）考慮問題的局部解?？紤]最優(yōu)性條件考慮問題的局部解?？紤]最優(yōu)性條件。2.1 等式約束情況問題： min f(x), xRn (2-2) st ci(x1, x2, ., xn) = 0, iE其中E = 1, 2, ., l 為等式約束的指標集。 考慮問題的局

2、部解考慮問題的局部解。拉格朗日函數(shù)和拉格朗日乘子法(學過？)其中x= ， ， i，i= 1, 2, ., l為拉格朗日乘子（或乘數(shù)）。)()()()(),(1xcxfxcxfxLTliiil21n21xxx)()()()(21xcxcxcxcl拉格朗日乘子法ci(x) = 0, i=1, 2, ., l 。 空格空格解上述方程組，得x*即是可能的局部解。（式一是L(x, )對各個xi 的偏導數(shù)為0， 視為常數(shù)）局部解的必要條件。局部解的必要條件。0)()(),(1xcxfxLiliix例例：按照該方法或該必要條件求可能局部解 min f(x) = x1 + x2 st c1(x) = 2 -

3、x12 - x2 2 = 0解：c1(x) = 2 - x12 - x2 2 = 0解得x1=-1，x2 =-1，1=-1/2； x1=1，x2 =1，1=1/2 。它們是可能的可能的局部解。)2()()(),(222112111xxxxxcxfxL)()(),(11xcxfxLx02211121xx f(x*) c1(x*)x* f(x)f(x) = x1 + x2 = -2O c1(x)圖解：圖解：在局部解x*(也是最優(yōu)解)處，f(x*)和c1(x*)平行平行，所以有某個數(shù)*，使得此例說明：拉格朗日定理是正確的。對于此例， * = -1/2。（可看到: 等式約束時等式約束時Lamda不必不

4、必0。后面有用。）0*)(*)(1*xcxf高維例子高維例子P240，薛毅 c1(x*), c2(x*), f(x*)共面共面（都和切線（都和切線T垂直）垂直）交線交線D為可行域為可行域設設x*為局部解。為局部解。x*處處D的切線為的切線為T。等值面等值面min f(x)=f(x1, x2, x3)st c1(x)=c1(x1, x2, x3)=0 c2(x)=c2(x1, x2, x3)=0拉格朗日定理定理定理 對于等式約束最優(yōu)化問題(2-2)，設f(x)、 ci(x)在x*處有連續(xù)偏導數(shù)，又設下面的l個n維向量ci(x*), iE線性無關。那么，如果x=x*為問題的局部解，則存在向量使得：

5、*21l0*)(*)(1*xcxfilii方法/定理正確性的舉例說明-證明難懂。 min f(x) = x1 + x2 st c1(x) = 2 - x12 - x2 2 = 0局部解的必要條件局部解的必要條件對等式約束最優(yōu)化問題(2-2)，設滿足拉格朗日定理的條件，如果x=x*為問題的局部解，則存在常數(shù)向量 * =(1*, 2*, , l*)T，有和和ci(x*) = 0, i=1, 2, ., l。 這是拉格朗日乘子法的基礎，拉格朗日定理的重復。0*)(*)(1*xcxfilii局部解的二階必要條件和充分條件局部解的二階必要條件和充分條件 (選學選學)預備：拉格朗日函數(shù)的海賽矩陣海賽矩陣定

6、義集合這是與每個約束函數(shù)梯度或法向量都正交的向量的集合。 0)()(1xcxfilii, 2 , 1, 0)(,|)(lizxcRzzxZTin)()(),(2122xcxfxLiliix),(xLxliiixcxfxL1)()(),(局部解局部解二二階必要條件階必要條件(選學選學)定理定理 對于等式約束最優(yōu)化問題 min f(x), xRn , st ci(x1, x2, ., xn) = 0, iE設f(x)、ci(x)在x*處有連續(xù)偏導數(shù)，而且l個n維向量ci(x*), iE 是線性無關的。設x=x*為問題的局部解，*=(1*, 2*, , l*)T滿足 , 即拉格朗日乘子.則對當 時，

7、有 。 【這里這里 】, 2 , 1, 0*)(,|*)(lizxcRzzxZTin*)(*)(*)*,(21*22xcxfxLiliix0*)*,(2zxLzxT*)(xZz0*)(*)(1*xcxfilii*)*,(xLx局部解的充分條件局部解的充分條件 (選學選學) 定理定理 對于等式約束最優(yōu)化問題 min f(x), xRn, st ci(x1, x2, ., xn) = 0, iE設存在可行解x*和向量* =(1*, 2*, , l*)T，使得定義集合 令 如果對所有 有則 x=x*為問題的局部解。0*)(*)(1*xcxfilii, 2 , 1, 0*)(,|*)(lizxcRzz

8、xZTin*)(*)(*)*,(21*22xcxfxLiliix0*)*,(2zxLzxT0*),(zxZz*),(xLx先滿足先滿足一階一階 必要必要 條件條件例 min f(x) = x1 + x2 st c1(x) = 2 - x12 - x2 2 = 0 對于可能的局部解x1=-1，x2 =-1，1=-1/2為正定，所以這是一個局部解這是一個局部解。l 對于另一個可能的局部解x1=1，x2 =1，1=1/2 負定。z=(1,-1)Tz(x*),z0.根據(jù)二階必要條件， 不是局部解。1001*)(*)(*)*,(21*22xcxfxLiliix0)(2xf2002)(12xc1001*)

9、*,(2xLx已經求出了已經求出了可能的局部解可能的局部解0*)*,(2zxLzxT例子(選學選學)o 薛毅p259【例8.3.1】需要去求定理中的集合Z，因為矩陣2L不是正定的。如果矩陣2L是正定的，則不必去求集合Z。簡單。覺得困難的同學掌握到這種程度即可。凸優(yōu)化情況（等式約束時） (重點重點)o 定理 設問題(2-2)為一個凸優(yōu)化問題（即 可行域D是凸集，目標函數(shù)f是D上的凸函數(shù)），又設目標函數(shù)f(x)和約束函數(shù)ci(x)都存在一階連續(xù)偏導數(shù)。如果存在可行解x*和常數(shù)向量 * =(1*, 2*, , l*)T，使得則x*是問題的最優(yōu)解。-似也有稱之為駐點的。0*)(*)(1*xcxfilii例 min (x1 2) 2 + (x2 1) 2 st x1 + x2+5=0 求解 和約束組成的方程組，得x1=-2，x2 =-3，1=8由于是凸優(yōu)化問題，所以它是最優(yōu)解。0)()(xcxf作業(yè)o8.17題, p267, 薛毅 min x1x2, st x12 + x2 2 = 1n求滿足一階必要條件的點(可能的局部解)。n上面