最優(yōu)化方法課程設(shè)計--可行方向法分析與實(shí)現(xiàn)

1、<p>　　《最 優(yōu) 化 方 法》</p><p><b>　　課 程 設(shè) 計</b></p><p>　　題 目：可行方向法分析與實(shí)現(xiàn) </p><p>　　院 系：數(shù)學(xué)與計算科學(xué)學(xué)院 </p><p>　　專 業(yè)： 統(tǒng)計學(xué) </p&g

2、t;<p>　　姓名學(xué)號： XXXX 12007XXXXX </p><p><b>　　摘 要</b></p><p>　　在各種優(yōu)化算法中,可行方向法是非常重要的一種。可行方向法是通過直接處理約束問題，得到一個下降可行方向，從而產(chǎn)生一個收斂于線性約束優(yōu)化問題的K-T點(diǎn)。本文主要介紹的Zoutendiji可行方向法是求解

3、約束優(yōu)化問題的一種有代表性的直接解法.在本次實(shí)驗(yàn)中，本人對該門課程中的線性約束非線性最優(yōu)化問題進(jìn)行了一定程度地了解和研究，而處理線性約束非線性最優(yōu)化問題的關(guān)鍵是在求解過程中，不僅要使目標(biāo)函數(shù)值單調(diào)下降，而且還要保證迭代點(diǎn)的搜索方向?yàn)橄陆悼尚蟹较颉Ｋ?，本人使用利用線性規(guī)劃方法來確定的可行方向法——Zoutendijk可行方向法進(jìn)行處理。本人通過數(shù)學(xué)軟件MATLAB探討了優(yōu)化設(shè)計的實(shí)現(xiàn)方法及實(shí)現(xiàn)驗(yàn)證的效果，更進(jìn)一步地加深了對它的理解也提高

4、了處理該問題的水平能力。而且該方法初始參數(shù)輸入簡單，編程工作量小，具有明顯的優(yōu)越性．</p><p>　　關(guān)鍵詞：Zoutendiji可行方向法，約束優(yōu)化問題，下降可行方向。</p><p><b>　　Abstract</b></p><p>　　In a variety of optimization algorithms, the fea

5、sible descent method is a very important one. The feasible direction method is by directly dealing with constraints, getting a feasible direction, to produce a convergence in the k-t point of the linear constrained optim

6、ization problems. Zoutendiji feasible direction method is mainly introduced in this paper to solve the constrained optimization problem of a kind of typical and direct solution.In this experiment, We have a certain degre

7、e of underst</p><p>　　Key words: Zoutendiji feasible direction method, Constrained optimization problems, Feasible direction.</p><p><b>　　目 錄</b></p><p><b>　　1、引言

8、1</b></p><p>　　2、可行方向法的描述1</p><p>　　2.1 可行方向法1</p><p>　　2.2線性不等式約束的Zoutendijk Method2</p><p>　　2.3 算法實(shí)現(xiàn)3</p><p><b>　　3、數(shù)值實(shí)驗(yàn)4</b><

9、;/p><p>　　3.1 代碼實(shí)現(xiàn)4</p><p>　　4、算法比較及缺點(diǎn)8</p><p>　　4.1 隨機(jī)方向搜索法8</p><p>　　4.2 復(fù)合型法8</p><p>　　4.3可行方向法9</p><p><b>　　4.4 缺點(diǎn)9</b><

10、/p><p><b>　　5、總結(jié)9</b></p><p>　　5.1 總結(jié)概括9</p><p>　　5.2 個人感言9</p><p><b>　　6、參考文獻(xiàn)：9</b></p><p><b>　　1、引言</b></p>&

11、lt;p>　　現(xiàn)在，可行方向法已發(fā)展成為求解約束優(yōu)化問題的一類重要方法，其基本思想是：給定一個可行點(diǎn)之后，用某種方法確定一個改進(jìn)的可行方向，然后沿方向，求解一個有約束的線搜索問題，得極小點(diǎn)，按迭代公式計算：，如果不是最優(yōu)解，則重復(fù)上述步驟。各種不同的可行方向法的主要區(qū)別在于：選擇可行方向的策略不同。大體上可分為三類：（1）用求解一個線性規(guī)劃方法來確定。（2）利用投影矩陣來直接構(gòu)造一個改進(jìn)的可行方向。（3）利用既約梯度，直接構(gòu)造一個

12、改進(jìn)的可行方向。其中Zoutendijk Method就是利用線性規(guī)劃方法來確定的。</p><p>　　2、可行方向法的描述</p><p><b>　　2.1 可行方向法</b></p><p>　　可行方向法是通過直接處理約束問題，得到一個下降可行方向，從而產(chǎn)生一個收斂于線性約束優(yōu)化問題的K-T點(diǎn)。一般地，求解約束優(yōu)化問題要比求解無約束優(yōu)

13、化問題復(fù)雜、困難，因?yàn)樵谇蠼膺^程中，不僅要使目標(biāo)函數(shù)值單調(diào)下降，而且還要保證迭代點(diǎn)滿足約束條件。因此，在求解過程中，要求產(chǎn)生的迭代點(diǎn)的搜索方向?yàn)橄陆悼尚蟹较?。由于這時的約束為線性函數(shù)，因而可通過利用線性代數(shù)的知識和無約束優(yōu)化方法來設(shè)計一些有效算法。</p><p>　　2.1.1非線性約束</p><p>　　Basic concept</p><p>　　Desc

14、ent direction d: </p><p>　　Feasible direction d: </p><p>　　定義：非零向量d稱為在點(diǎn)的一個可行方向,若 都有：。</p><p>　　d0稱為在點(diǎn)的一個改進(jìn)的可行方向,若 都有： ，</p><p>　　2.2 線性不等式約束的Zoutendijk Method</p>

15、<p>　　(P) </p><p><b>　　s.t. </b></p><p><b>　　Denote </b></p><p>　　Such that: </p><p>　　Obviously:</p><p>　　Descent d :

16、 </p><p>　　Feasible d : </p><p><b>　　Solving：</b></p><p>　　for solve(P) to obtain descent direction d.</p><p><b>　　Since </b></p><p&

17、gt;<b>　　then ,</b></p><p>　　so d is the descent direction. </p><p>　　for solve(P) to obtain feasible direction d.</p><p><b>　　since </b></p><p>

18、;<b>　　so </b></p><p><b>　　since ,</b></p><p><b>　　having </b></p><p>　　so d is the feasible direction. </p><p>　　set feasible direct

19、ion d ,solving </p><p><b>　　since ,</b></p><p><b>　　so .</b></p><p><b>　　since </b></p><p><b>　　so .</b></p><

20、;p>　　2.2.1 Subproblem(子問題)：</p><p><b>　?。↙P） </b></p><p><b>　　s.t. </b></p><p>　　Conclusions:</p><p>　　1、For (LP) with optima , 。</p>

21、<p>　　2、 if is a KKT point of (P)。</p><p>　　3、If then is a feasible descent direction at 。 </p><p><b>　　2.3 算法實(shí)現(xiàn)：</b></p><p><b>　　step0: </b></

22、p><p>　　step1: .</p><p>　　step2: the K-T point, stop!</p><p><b>　　step3: </b></p><p>　　step4: set </p><p>　　go to step1.</p><p&g

23、t;　　Note: How to get ?</p><p><b>　　ensure </b></p><p><b>　　i.e. </b></p><p><b>　　Due to </b></p><p><b>　　Hope: </b><

24、;/p><p><b>　　If </b></p><p><b>　　Then </b></p><p><b>　　Set </b></p><p><b>　　3、數(shù)值實(shí)驗(yàn)</b></p><p><b>　　3

25、.1 代碼實(shí)現(xiàn)</b></p><p>　　Zoutendijk法使用舉例：</p><p><b>　　matlab程序：</b></p><p><b>　　定義所求函數(shù)并賦值</b></p><p>　　function h= fun1(x)</p><p>

26、;<b>　　syms a b;</b></p><p><b>　　x1=[a b];</b></p><p>　　f=a^2+4*b^2;</p><p>　　h=subs(f,x1,x);</p><p><b>　　end</b></p><p>

27、;<b>　　求導(dǎo)函數(shù)dfx：</b></p><p>　　function dfx=dfxfun(x)</p><p><b>　　syms a b;</b></p><p><b>　　x1=[a b];</b></p><p>　　f=a^2+4*b^2;</p&g

28、t;<p>　　grad=jacobian(f,x1);</p><p>　　dfx=subs(grad,x1,x);</p><p><b>　　end</b></p><p><b>　　根據(jù)</b></p><p>　　function h=fun(lamda,d,x)</

29、p><p><b>　　syms a b;</b></p><p><b>　　x1=[a b];</b></p><p>　　f=a^2+4*b^2;</p><p>　　xx=x+lamda*d;</p><p>　　h=subs(f,x1,xx);</p>&

30、lt;p><b>　　end</b></p><p><b>　　主函數(shù)</b></p><p>　　function Zoutendijk(x0,A,b)</p><p><b>　　c=0;</b></p><p><b>　　kk=0;</b>

31、</p><p>　　options=optimset('Display','off'); </p><p><b>　　while c<5</b></p><p><b>　　c=c+1;</b></p><p><b>　　k=0;j=0;<

32、/b></p><p><b>　　kk=kk+1;</b></p><p>　　A1=[];b1=[];</p><p>　　A2=[];b2=[];</p><p>　　[m,n]=size(A);</p><p><b>　　for i=1:m</b></p

33、><p>　　C=A(i,:)*x0;</p><p>　　if C>=b(i)-1e-4 %不起作用約束A1,b1</p><p><b>　　k=k+1;</b></p><p>　　A1(k,:)=A(i,:);</p><p>　　b1(k,1)=b(i);</p>&

34、lt;p><b>　　end</b></p><p>　　if C<b(i)-1e-4 %起作用約束放到A2，b2</p><p><b>　　j=j+1;</b></p><p>　　A2(j,:)=A(i,:);</p><p>　　b2(j,1)=b(i);</p>

35、<p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　%A1,b1</b></p><p><b>　　%A2,b2</b></p><p>　　if isempty(A2) %A2為

36、0向量矩陣</p><p>　　f1=dfxfun(x0);</p><p>　　if (abs(f1)<=1e-4)</p><p><b>　　break</b></p><p>　　else d=-f1;</p><p><b>　　end</b></p&g

37、t;<p><b>　　else</b></p><p>　　lb=[-1 -1];</p><p><b>　　ub=[1 1];</b></p><p>　　b0=zeros(size(b1));</p><p>　　f1=dfxfun(x0);</p><p&

38、gt;　　[d,fval1]=linprog(f1,A1,b0,[],[],lb,ub); %求解最小化問題,得到可行方向d和最值</p><p>　　if fval1==0</p><p><b>　　break</b></p><p><b>　　end </b></p><p>&l

39、t;b>　　end</b></p><p><b>　　%pause</b></p><p><b>　　dd=A2*d;</b></p><p>　　bb=b2-A2*x0;</p><p>　　lamdmax=max(bb./dd);</p><p>　

40、　lamda=fminbnd(@(lamda)fun(lamda,d,x0),0,lamdmax,options); %求函數(shù)的局部極小值</p><p>　　if (isempty(lamda(:)))%〖f(x)〗^T d^k=0迭代結(jié)束</p><p><b>　　break</b></p><p><b>　　end<

41、;/b></p><p>　　x0=x0+lamda*d;%獲得新點(diǎn)</p><p><b>　　end</b></p><p>　　fprintf('可行方向法\n：迭代次數(shù)：kk=%d\n',kk);</p><p>　　fprintf('最優(yōu)解：\n');</p>

42、<p><b>　　x0 </b></p><p>　　fval3=fun1(x0);</p><p>　　fprintf('函數(shù)最值：\n');</p><p><b>　　fval3</b></p><p>　　%用非線性約束函數(shù)方法，檢驗(yàn)所得到的結(jié)果是否正確<

43、;/p><p><b>　　x0=[0;0];</b></p><p>　　[x,fval]=fmincon(@fun1,x0,A,b,[],[],[],[],[],options);%求解非線性問題</p><p>　　fprintf('用非線性約束規(guī)劃檢驗(yàn)：最優(yōu)解為：\n');</p><p><b

44、>　　x</b></p><p>　　fprintf('約束條件下函數(shù)最值：\n');</p><p><b>　　fval</b></p><p><b>　　end</b></p><p>　　command中輸入：</p><p>&l

45、t;b>　　x0=[0;0];</b></p><p>　　A=[2.0 -1.0;1.0 1.0;-1.0 0.0;0.0 -1.0];</p><p>　　b=[1.0;2.0;0.0;0.0];</p><p>　　>> zoutendijk(x0,A,b)</p><p>　　Optimization t

46、erminated.</p><p>　　Optimization terminated.</p><p>　　Optimization terminated.</p><p>　　Optimization terminated.</p><p>　　Optimization terminated.</p><p>&

47、lt;b>　　可行方向法：</b></p><p><b>　　迭代次數(shù)：kk=5</b></p><p><b>　　最優(yōu)解：</b></p><p><b>　　x0 =</b></p><p><b>　　0.5000</b><

48、;/p><p><b>　　1.5000</b></p><p><b>　　函數(shù)最值：</b></p><p><b>　　fval3 =</b></p><p><b>　　1.5001</b></p><p>　　Warning:

49、 Trust-region-reflective algorithm does not solve this type of problem, using active-set</p><p>　　algorithm. You could also try the interior-point or sqp algorithms: set the Algorithm option to</p>&l

50、t;p>　　>> In fmincon at 472</p><p>　　>> In zoutendijk at 61</p><p>　　用非線性約束規(guī)劃檢驗(yàn)：最優(yōu)解為：</p><p><b>　　x =</b></p><p><b>　　0.5000</b>&l

51、t;/p><p><b>　　1.5000</b></p><p>　　約束條件下函數(shù)最值：</p><p><b>　　fval =</b></p><p><b>　　1.5000</b></p><p><b>　　所得到結(jié)果為： </

52、b></p><p>　　根據(jù)數(shù)學(xué)解法，代入驗(yàn)證結(jié)果符合要求，表明可行方向法編程正確！</p><p><b>　　4、算法比較及缺點(diǎn)</b></p><p>　　4.1隨機(jī)方向搜索法</p><p>　　特點(diǎn)：簡單、方便，對目標(biāo)函數(shù)性態(tài)無特殊要求，收斂較快，但計算精度不高，對嚴(yán)重非線性問題一般只能提供較近似的最優(yōu)

53、解。</p><p>　　使用原則：適用于中小型無約束或有約束優(yōu)化問題。</p><p><b>　　4.2復(fù)合型法</b></p><p>　　特點(diǎn)：具有單純型法的特點(diǎn)，適合于求解n<20的規(guī)劃問題，但不能求解有等式約束的問題。對目標(biāo)函數(shù)和約束函數(shù)無特殊要求，不必計算目標(biāo)函數(shù)的梯度和二階導(dǎo)數(shù)矩陣，方法簡單、實(shí)用可靠、應(yīng)用較廣，有一定的收

54、斂精度，但收斂速度一般。</p><p>　　使用條件：不適于變量較多(n>15)和有等式約束的優(yōu)化，是求解非線性優(yōu)化的有效方法之一，在優(yōu)化設(shè)計中得到廣泛應(yīng)用。</p><p><b>　　4.3可行方向法</b></p><p>　　特點(diǎn)：1）可行方向法是用梯度去求解約束優(yōu)化設(shè)計問題的一種有代表性的直接搜索方法。2）收斂速度快，效果較好

55、，但程序比較復(fù)雜。</p><p>　　使用條件：適用于大中型約束優(yōu)化設(shè)計問題的求解。</p><p><b>　　4.4缺點(diǎn)：</b></p><p>　　由于Zoutendijk可行方向法是基于無約束優(yōu)化中的最速下降法，所以此算法具有最速下降法的一些缺點(diǎn)。以非典型的缺點(diǎn)就是“鋸齒現(xiàn)象”，從而，當(dāng)?shù)平怯行Ъs束邊界時可能會發(fā)生一些突然的變

56、化，使得收斂速度很慢，甚至不收斂于K-T點(diǎn)</p><p><b>　　5、總結(jié)</b></p><p><b>　　5.1 總結(jié)概括</b></p><p>　　求解最優(yōu)問題是一個艱難而具有挑戰(zhàn)性的過程，最優(yōu)化方法是近幾十年形成的一門運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)的學(xué)科，它涵蓋了無約

57、束最優(yōu)化問題、凸集與凸函數(shù)、等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題等知識點(diǎn)。本次課程設(shè)計，我對該門課程中的線性約束非線性最優(yōu)化問題進(jìn)行了一定程度地了解和研究，而處理線性約束非線性最優(yōu)化問題的關(guān)鍵是在求解過程中，不僅要使目標(biāo)函數(shù)值單調(diào)下降，而且還要保證迭代點(diǎn)的搜索方向?yàn)橄陆悼尚蟹较?。所以，我使用利用線性規(guī)劃方法來確定的可行方向法——Zoutendijk可行方向法進(jìn)行處理。我從理論的來源、推導(dǎo)過程以及算法出發(fā)進(jìn)行深入舉例求解，之后，我通過

58、數(shù)學(xué)軟件MATLAB實(shí)現(xiàn)驗(yàn)證的效果，更進(jìn)一步地加深了對它的理解也提高了處理該問題的水平能力。</p><p><b>　　5.2 個人感言</b></p><p>　　通過本次課設(shè)，我學(xué)會了應(yīng)該怎么從一個問題出發(fā)，對該問題進(jìn)行研究：首先要對問題有一個大概的了解，通過查閱資料，對問題有了深入了解，然后確定問題的研究方向，以及要研究方向所需要進(jìn)行的工作，然后一步步去完成。

59、</p><p><b>　　6、參考文獻(xiàn)：</b></p><p>　　[1] 唐煥文，秦學(xué)志.實(shí)用最優(yōu)化方法[M].大連：理工大學(xué)出版社，2004.</p><p>　　[2] 萬仲平，費(fèi)普生.優(yōu)化理論與方法[M].武漢：武漢大學(xué)教育出版社，2004.</p><p>　　[3] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M