1、 Content無約束非線性規劃問題無約束非線性規劃問題有約束非線性規劃問題有約束非線性規劃問題Matlab求解有約束非線性規劃問題求解有約束非線性規劃問題一一. .無約束問題無約束問題 一維搜索 指尋求一元函數在某區間上的最優值點的方法。這類方法不僅有實用 價值，而且大量多維最優化方法都依賴于一系列的一維最優化。 逐次插值逼近法逐次插值逼近法 近似黃金分割法（又稱近似黃金分割法（又稱0.6180.618法）法） 無約束最優化 指尋求 n元實函數f在整個n維向量空間Rn上的最優值點的方法。無約束最優化方法大多是逐次一維搜索的迭代算法。這些迭代算法的基本 思想是：在一個近似點處選定一個有利搜索方

2、向,沿這個方向進行一維尋查,得出新的近似點。然后對新點施行同樣手續，如此反復迭代,直到滿足預定的精度要求為止。根據搜索方向的取法不同，可以有各種算法。 最速下降法（負梯度法）最速下降法（負梯度法） NewtonNewton法法 共軛梯度法共軛梯度法 擬擬NewtonNewton法法 變尺度法變尺度法 二二. .有約束問題有約束問題（一）罰函數法（一）罰函數法（SUMTSUMT） 1 1、算法思想：、算法思想： 將有約束優化問題轉化為一系列無約束優化問題將有約束優化問題轉化為一系列無約束優化問題進行求解進行求解.(Sequential Unconstrained Minimization .(S

3、equential Unconstrained Minimization Technique-SUMTTechnique-SUMT） 2 2、算法類型：、算法類型：q 外點法（外懲法）外點法（外懲法） q 內點法（內懲法）內點法（內懲法）3 3、問題：、問題： 4.1 4.1、外點法（外部懲罰函數法）、外點法（外部懲罰函數法）：yesNo1, 0 1, 0,1)0(kx初始)1()( )()(min,kkkxxpxfx得到解為初始點以 )()1(kkxpopt )1(kx停kk 11 kk外點法框圖： 4.2 4.2、內點法（內部懲罰函數法）：、內點法（內部懲罰函數法）：SxtsxF. .),

4、(min算法：算法： （1） 給定初始內點給定初始內點Sx)0(，允許誤差，允許誤差 e0， 障礙參數障礙參數)1(，縮小系數，縮小系數) 1 , 0(b，置，置 k=1； （2） 以以)1( kx為初始點，求解下列規劃問題：為初始點，求解下列規劃問題： SxtsxBxfk. .)()(min)(，令，令)(kx為所求極小點為所求極小點 （3） 如果如果exBkk)()()(，則停止計算，得到結果，則停止計算，得到結果)(kx， （4） 否則令否則令)()1(kkb，置，置 k=k+1，返回（，返回（2） 。） 。 內點法框圖1 kkkk 1 )()1(kkxqyesNoopt )1( kx停

5、停1, 0 ,1 , 0 , 0,10)0( kSx )1()(0 , s.t.)()(min kkkxxSxxqxf求求得得出出發發從從 內點法的內點法的matlab程序：程序： m=zeros(1,50);a=zeros(1,50);b=zeros(1,50);f0=zeros(1,50); syms x1 x2 e; m(1)=1;c=0.2;a(1)=2;b(1)=-3; f=x12+x22-e*(1/(2*x1+x2-2)+1/(1-x1); f0(1)=15; fx1=diff(f,x1);fx2=diff(f,x2);fx1x1=diff(fx1,x1);fx1x2=diff(f

6、x1,x2);fx2x1 =diff(fx2,x1);fx2x2=diff(fx2,x2); for k=1:100 x1=a(k);x2=b(k);e=m(k); for n=1:100 f1=subs(fx1); f2=subs(fx2); f11=subs(fx1x1); f12=subs(fx1x2); f21=subs(fx2x1); f22=subs(fx2x2); if(double(sqrt(f12+f22)=0.002) a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f); break; else X=x1 x

7、2-inv(f11 f12;f21 f22)*f1 f2; x1=X(1,1);x2=X(2,1); end end if(double(sqrt(a(k+1)-a(k)2+(b(k+1)- b(k)2)=0.001)&(double(abs(f0(k+1)-f0(k)/f0(k)=0.001) a(k+1) b(k+1) k f0(k+1) break; else m(k+1)=c*m(k); end end 結果： ans = 1.0000 ans = -7.1594e-004 k = 14小結小結講解了兩個求解有約束非線性規劃問題的特點講解了兩個求解有約束非線性規劃問題的特點.易

8、于實現，方法簡單易于實現，方法簡單.沒有用到目標函數的導數沒有用到目標函數的導數.問題的轉化技巧（近似為一個無約束規劃）問題的轉化技巧（近似為一個無約束規劃）. （二）拉格朗日乘子法（二）拉格朗日乘子法 （三）可行方向法與廣義簡約梯度法（三）可行方向法與廣義簡約梯度法 （四）（四）SQPSQP方法方法三三.Matlab.Matlab求解有約束問題求解有約束問題運行輸出：運行輸出：x = 24.0000 12.0000 12.0000 fval = -3.4560e+03（二）非負條件下線性最小二乘（二）非負條件下線性最小二乘lsqnonneglsqnonneg（三）有約束線性最小二乘（三）有約束線性最小二