【正文】 規(guī)劃 — 可行方向法v LCO問題： Min f(x) . aiTx?bi, i?I ajTx=bj, j??v 設(shè) x0是 LCO的一個(gè)可行解，若 d是可行域在 x0點(diǎn)的 可行方向 ，則 d滿足 AI(x0)d?0(I(x0)={i|aiTx0=bi,i?I})，A?d=0。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 一階充分條件? 設(shè) x*?S，若 函數(shù) f(x), gi(x), hj(x)在 x*處可微，且對(duì)于 x*的任意可行方向 d，有 dT?f(x*)0，則 x*為 COP問題的一個(gè)嚴(yán)格局部極小點(diǎn)。稱等號(hào)成立的約束為積極約束 (有效約束 )，此時(shí)， x0處于該約束條件形成的可行域邊界上；稱大于號(hào)成立的約束為非積極(inactive)約束 (無效約束 )，此時(shí)， x0不在該約束條件形成的可行域邊界上。? 調(diào)用無約束非線性規(guī)劃函數(shù) x0 = [1,1]。如果近似誤差比較大，那么可在近似最小點(diǎn)附近重新構(gòu)造 f(x)的二階 Taylor多項(xiàng)式(迭代 )，據(jù)此尋找新的近似最小點(diǎn)，重復(fù)以上過程直到求得滿足一定精度要求的迭代點(diǎn)。 x2≥0解 ：將 max變?yōu)?min， min –z=x12x2則： f=[1。? 最優(yōu)解分析 ：在端點(diǎn) (或稱為極點(diǎn)。v 動(dòng)態(tài)規(guī)劃 與 多層規(guī)劃 ：若決策是分成多個(gè)階段完成的，前后階段之間相互影響，則稱為動(dòng)態(tài)規(guī)劃；若決策是分成多個(gè)層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃?；谶@兩點(diǎn)， Karmarkar構(gòu)造了一種稱為 投影尺度算法 的內(nèi)點(diǎn)算法。v 充分條件 。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x)v Matlab提供了兩個(gè)求解無約束非線性規(guī)劃的函數(shù)? [x,fval] = fminunc(fun,x0)? [x,fval] = fminsearch(fun,x0)v 用法相似，算法內(nèi)部的搜索策略不同。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型v 其中 f(x)是目標(biāo)函數(shù)， gi(x)和 hj(x)為約束函數(shù) (約束條件 )。若 x0的某一方向 d既是可行方向又是下降方向則稱其為可行下降方向。v 根據(jù)凸規(guī)劃充分條件知 x*為全局最小點(diǎn)。即 S0={x|g(x)0}≠?決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 例 ： min{f=x/2|x?1}v 解：構(gòu)造對(duì)數(shù)障礙函數(shù) P(x,?)=x/2?ln(x1)? P’x=1/2?/(x1)=0，得 x?*=1+2?， P*=1/2+??ln2?? 當(dāng) ?→0 時(shí)得 x*=1， f*=1/2決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 標(biāo)準(zhǔn)型v 若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量 x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃 (Quadratic Programming, QP)問題。 ceq = ceq(x)。,39。[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用v 例 ： min f(x)=1/2x12+x22x1x22x16x2 . x1+x2?2 x1+2x2?2 2x1+x2?3 x1, x2?0v 解 ：? 改寫 f(x)=1/2(x12+2x22x1x2x1x2)2x16x2得： H=[1 1。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用? 調(diào)用二次規(guī)劃函數(shù)[x,fval]=quadprog(H,f,A,b,[],[],lb)? 運(yùn)行結(jié)果 ：x =[。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Pareto最優(yōu)解v 設(shè) x*是可行域 S上的一個(gè)點(diǎn)，對(duì)于 ?x?S，均有：fi(x*)?fi(x)(i=1,…, p)，稱 x*為 MOP問題的絕對(duì)最優(yōu)解；若不存在 x?S，使得 fi(x)?fi(x*)(或 fi(x)fi(x*)) (i=1,…, p)，則稱 x*為 MOP問題的有效解 (或弱有效解 )。 關(guān)鍵問題在于 ：保證最后一個(gè)單目標(biāo)優(yōu)化問題的最優(yōu)解是 MOP問題的有效解或弱有效解。Aeq。A。minimax SQP, QuasiNewton, line_search‘決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (2)：用 fgoalattain求解。v 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。b=[]。x?b Aeq aij=1(vi為 ej的起點(diǎn) )； aij=1(vi為 ej的終點(diǎn) )； aij=0(其他情形 )。? 無約束。f(p)=f p(x)? 創(chuàng)建另一個(gè) matlab文件，如 function [c, ceq] = confun(x)c = c(x)。? 調(diào)用 fminimax并指定初始搜索點(diǎn)以及其他向量、矩陣。j?? fk(x)?uk, k=2,…, p? uk為專家經(jīng)驗(yàn)值。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 標(biāo)準(zhǔn)型v 多目標(biāo)規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個(gè)可數(shù)值化的目標(biāo)函數(shù)同時(shí)極小化 (或極大化 )的問題。Aeq=[]。Aeq。ceq = []。x?b Aeq因此也將此類方法稱為 罰函數(shù)法 ，所形成的無約束優(yōu)化函數(shù)成為 罰函數(shù) 。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 例： min f(x)=x12+x22 . x1+x2?4 x1,x2?0v 解： g1(x)=x1+x24?0。v 下降方向 ?；蛘?[x,fval] = fminsearch(myfun,x0,options)。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 準(zhǔn)牛頓法v 牛頓法算法的優(yōu)點(diǎn)是收斂速度快 (利用了 Hesse矩陣)。40], fval= 80x1x2x1+x2=402x1+x2=60Z=x1+2x2決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型v Min f(x)。在給定初始可行解后，沿著什么樣的路徑到達(dá)最優(yōu)解呢？? 單純形法是從某個(gè)基可行解開始，沿著多面體的邊移動(dòng)最終找到最優(yōu)解。v 特點(diǎn) ：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。決策理論與方法 優(yōu)化決策理論與方法線性規(guī)劃 — 內(nèi)點(diǎn)算法v1972年， V. Klee和 G. L. Minty指出 Dantzig的單純形算法的迭代次數(shù)為 O(2n)，是一個(gè)指數(shù)時(shí)間算法，不是優(yōu)良算法。 lb=zeros(2,1)。? 迭代改進(jìn) ：計(jì)算新的迭代點(diǎn) xk+1，即 xk+1=xkG1(xk)g(xk)。off39。設(shè) x0為 COP問題的任一可行解，對(duì)某一方向 d來說，若 ???00使得對(duì)于任意 ??[0,?0]，均有 x0+?d?S，稱 d為x0的一個(gè)可行方向。若函數(shù)f(x), gi(x), hj(x)在 x*處二階可微，則必有：dT?xx2L(x*,?*,?*)d?0 其中， L(x,?,?)=f(x)g(x)T?h(x)T?, g(x),h(x)分別為由 gi(x)和 hj(x)構(gòu)成的向量值函數(shù)， ?,?分別為對(duì)應(yīng)于 g(x)和 h(x)的拉格朗日乘子向量。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 求解約束優(yōu)化的一類重要方法是用一個(gè)無約束優(yōu)化問題的序列 逼近 約束優(yōu)化問題，通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — SQP法v 對(duì)于等式約束優(yōu)化問題Min f(x). h(x)=0v 拉格朗日函數(shù)記為 L(x,?)=f(x)?Th(x)v 則 ?L(x,?)=(?f(x)?h(x)?, h(x))T=0，顯然問題的最優(yōu)解(x*,?*)滿足此式。[x,fval]=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,confun)決策理論與方法