約束最優(yōu)化方法課件

1、約束最優(yōu)化方法約束最優(yōu)化方法 問題 min f(x) s.t. g(x) 0 分量形式略 h(x)=0 約束集 S=x|g(x) 0 , h(x)=0 1 Kuhn-Tucker 條件一、等式約束性問題的最優(yōu)性條件： 考慮 min f(x) s.t. h(x)=0 回顧高等數(shù)學(xué)中所學(xué)的條件極值： 問題 求z=f(x,y)極值 min f(x,y) 在(x,y)=0的條件下。 S.t. (x,y)=0 引入Lagrange乘子： Lagrange函數(shù) L(x,y;)= f(x,y)+ (x,y)(fgh)(fh)即一、等式約束性問題的最優(yōu)性條件： (續(xù))若(x*,y*)是條件極值，則存在* ，使

2、 fx(x*,y*)+ * x (x*,y*) =0 fy(x*,y*)+ * y(x*,y*) =0 (x*,y*)=0 推廣到多元情況，可得到對于(fh)的情況： min f(x) s.t. hj(x)=0 j=1,2, ,l 若x*是(fh)的l.opt. ,則存在* Rl使 矩陣形式：分量形式：一、等式約束性問題的最優(yōu)性條件： (續(xù)) 幾何意義是明顯的：考慮一個約束的情況： 最優(yōu)性條件即：-f( ) h( )h(x)-f(x*)h(x*)這里 x* -l.opt. f(x*)與h(x*) 共線，而非l.opt.f( )與h( )不共線。二、不等式約束問題的Khun-Tucker條件：考

3、慮問題 min f(x) s.t. gi(x) 0 i=1,2, ,m 設(shè) x*S=x|gi(x) 0 i=1,2, ,m 令 I=i| gi(x*) =0 i=1,2, ,m 稱I為 x*點(diǎn)處的起作用集（緊約束集）。 如果x*是l.opt. ,對每一個約束函數(shù)來說，只有當(dāng)它是起作用約束時，才產(chǎn)生影響，如：(fg)g2(x)=0 x*g1(x)=0g1(x*)=0, g1為起作用約束Kuhn-Tucker 條件二、不等式約束問題的Khun-Tucker條件： （續(xù)） 特別 有如下特征：如圖 在x* ： f(x*)+u* g(x*)=0 u*0 要使函數(shù)值下降，必須使g(x)值變大，則 在 點(diǎn)使

4、f(x)下降的方向（- f( ) 方向）指向約束集合內(nèi)部，因此不是l.opt. 。g( )-f( )X*-f(x*)g(x*)二、不等式約束問題的Khun-Tucker條件： （續(xù)） 定理（最優(yōu)性必要條件）： （K-T條件） 問題(fg), 設(shè)S=x|gi(x) 0,x*S,I為x*點(diǎn)處的起作用集，設(shè)f, gi(x) ,i I在x*點(diǎn)可微， gi(x) ,i I在x*點(diǎn)連續(xù)。 向量組gi(x*), i I線性無關(guān)。 如果x*-l.opt. 那么， u*i0, i I使二、不等式約束問題的Khun-Tucker條件： （續(xù)）123412g1=0g2=0g4=0 x1g3=0 x2x*g2(x*)

5、g1(x*)-f(x*)(3,2)T二、不等式約束問題的Khun-Tucker條件： （續(xù)）用K-T條件求解：二、不等式約束問題的Khun-Tucker條件： （續(xù)）二、不等式約束問題的Khun-Tucker條件： （續(xù)）可能的K-T點(diǎn)出現(xiàn)在下列情況： 兩約束曲線的交點(diǎn)：g1與g2,g1與g3,g1與g4,g2與g3,g2與g4,g3與g4。 目標(biāo)函數(shù)與一條曲線相交的情況： g1，g2, g3, g4 對每一個情況求得滿足(1)(6)的點(diǎn)(x1,x2)T及乘子u1,u2,u3,u4,驗證當(dāng)滿足可得，且ui 0時，即為一個K-T點(diǎn)。下面舉幾個情況： g1與g2交點(diǎn)：x=(2,1)TS ,I=1,

6、2 則u3=u4=0 解二、不等式約束問題的Khun-Tucker條件： （續(xù)）二、不等式約束問題的Khun-Tucker條件： （續(xù)）三、一般約束問題的Kuhn-Tucker 條件三、一般約束問題的Kuhn-Tucker 條件 (續(xù))一、解線性約束問題的既約梯度法一、解線性約束問題的既約梯度法 （續(xù)）一、解線性約束問題的既約梯度法 （續(xù)）一、解線性約束問題的既約梯度法 （續(xù)）一、解線性約束問題的既約梯度法 （續(xù)）一、解線性約束問題的既約梯度法 （續(xù)）算法：x(1)S, k=1k=k+1Jk=j|xj為x(k)中最大m個正分量之一B=,aj(jJk),N=,aj(jJk),YNT=NfT(x(

7、k)- BfT(x(k)B-1NdB=-B-1NdN解得 x(k+1)=x(k)+kdd=0?YNStop;x(k)K-T點(diǎn) 一、解線性約束問題的既約梯度法 （續(xù)）二、廣義既約梯度法 （續(xù)）二、廣義既約梯度法 （續(xù)）3罰函數(shù)法 1.罰函數(shù)概念 （續(xù)）3 罰函數(shù)法 1.罰函數(shù)概念 （續(xù)）圖示3罰函數(shù)法2.罰函數(shù)法： （fgh）3罰函數(shù)法2.罰函數(shù)法： （續(xù)）3 罰函數(shù)法 2.罰函數(shù)法： （續(xù)）算法：初始x(1), 10, 1, 0,k=1以x(k)為初始點(diǎn)，解min f(x)+ (x)得到，x(k+1)k (x(k+1)0, 0,1, 0,k=1min f(x)+ k B(x)s.t. x S0從x(k）出發(fā)，求得，x(k+1)k B(x(k+1) yes停；x(k+1)解Nok+1 = k k=k+13 罰函數(shù)法 3.閘函數(shù)法： （續(xù)）3 罰函數(shù)法4.罰函