【正文】 (x*)?i=0； ?i?0， ?i?I? 若 x*滿足 KKT條件，則稱 x*為 COP問題的一個 KKT點，?i, ?j稱為 x*處的拉格朗日乘子。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 例： min f(x)=x12+x22 . x1+x2?4 x1,x2?0v 解： g1(x)=x1+x24?0。v 可行方向法的基本思想 ：當(dāng)某個可行方向同時也是目標(biāo)函數(shù)的下降方向時，沿此方向移動一定會在滿足可行性的情況下改進迭代點的目標(biāo)函數(shù)值。因此也將此類方法稱為 罰函數(shù)法 ，所形成的無約束優(yōu)化函數(shù)成為 罰函數(shù) 。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 極小點存在條件v 充要條件? 可行點 x*是 QP問題的局部極小點當(dāng)且僅當(dāng) x*為一個 KKT點且對于任意非零可行方向 d，有 dTQd?0。x?b Aeqb。ceq = []。mediumscale: SQP, QuasiNewton, linesearch39。Aeq。? 表示其它矩陣或向量A=[1 1。Aeq=[]。試建立描述物資調(diào)運過程的數(shù)學(xué)模型。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 標(biāo)準(zhǔn)型v 多目標(biāo)規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數(shù)值化的目標(biāo)函數(shù)同時極小化 (或極大化 )的問題。下面介紹多目標(biāo)規(guī)劃問題的間接解法，基本思路都是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為一個或多個單目標(biāo)優(yōu)化問題。j?? fk(x)?uk, k=2,…, p? uk為專家經(jīng)驗值。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin max {fi(x)}. c(x)?0 ceq(x)=0 A? 調(diào)用 fminimax并指定初始搜索點以及其他向量、矩陣。[x,fval]=fminimax(myfun,x0,A,b,Aeq,beq,lb,ub,confun)決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMinx,? ?. F(x)weightf(p)=f p(x)? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x)c = c(x)。lb。? 無約束。決策理論與方法 優(yōu)化決策理論與方法優(yōu)化決策理論與方法線性規(guī)劃非線性規(guī)劃（約束和非約束）多目標(biāo)規(guī)劃組合優(yōu)化與整數(shù)規(guī)劃決策理論與方法 優(yōu)化決策理論與方法組合優(yōu)化 — 基本概念v 組合優(yōu)化問題 是指從一個有限的可行解集中尋找使某個性能函數(shù)取極值的最優(yōu)解。 aij=1(vi為 ej的起點 )； aij=1(vi為 ej的終點 )； aij=0(其他情形 )。線性 (混合 )整數(shù)規(guī)劃問題 是指在等式或不等式的線性約束下，極大化 (或極小化 )某個線性函數(shù)，其中要求某些變量必須取整數(shù)。x?b Aeq0 1 1 0 1]。b=[]。所以整數(shù)規(guī)劃問題的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解。v 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。設(shè)計各類 貪婪算法 是求解組合優(yōu)化問題常用的思路。minimax SQP, QuasiNewton, line_search‘決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Matlab函數(shù)應(yīng)用v 解 (2)：用 fgoalattain求解。 f(2)= x(1)^2 3*x(2)^2。A。 weight為各目標(biāo)的權(quán)重向量。Aeq。f(2)=f2(x)。 關(guān)鍵問題在于 ：保證最后一個單目標(biāo)優(yōu)化問題的最優(yōu)解是 MOP問題的有效解或弱有效解。i?I hj(x)=0。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — Pareto最優(yōu)解v 設(shè) x*是可行域 S上的一個點，對于 ?x?S，均有：fi(x*)?fi(x)(i=1,…, p)，稱 x*為 MOP問題的絕對最優(yōu)解；若不存在 x?S，使得 fi(x)?fi(x*)(或 fi(x)fi(x*)) (i=1,…, p)，則稱 x*為 MOP問題的有效解 (或弱有效解 )。決策理論與方法 優(yōu)化決策理論與方法多目標(biāo)規(guī)劃 — 管理實例v 決策目標(biāo)：? 運輸速度最快，可用噸公里數(shù)（ 可觀測變量 ）最小描述。決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — Matlab函數(shù)應(yīng)用? 調(diào)用二次規(guī)劃函數(shù)[x,fval]=quadprog(H,f,A,b,[],[],lb)? 運行結(jié)果 ：x =[。2。[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。? 調(diào)用 quadprog并根據(jù)需要指定初始搜索點以及其他向量、矩陣。,39。ub。 ceq = ceq(x)。v 基本思想 ：在迭代點處構(gòu)造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重復(fù)此過程，直到求出滿足一定要求的迭代點。即 S0={x|g(x)0}≠?決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 序列無約束化法v 例 ： min{f=x/2|x?1}v 解：構(gòu)造對數(shù)障礙函數(shù) P(x,?)=x/2?ln(x1)? P’x=1/2?/(x1)=0，得 x?*=1+2?， P*=1/2+??ln2?? 當(dāng) ?→0 時得 x*=1， f*=1/2決策理論與方法 優(yōu)化決策理論與方法二次規(guī)劃 — 標(biāo)準(zhǔn)型v 若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量 x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃 (Quadratic Programming, QP)問題。Min dT?f(x0). AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1v 可以證明：當(dāng) x0取得 KKT點時當(dāng)且僅當(dāng) dT?f(x0)的最優(yōu)值為零。v 根據(jù)凸規(guī)劃充分條件知 x*為全局最小點。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 極小值存在條件v 二階必要條件? 設(shè) x*是 COP問題的局部極小點且滿足 KKT條件。若 x0的某一方向 d既是可行方向又是下降方向則稱其為可行下降方向。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 幾個概念v 可行方向 。決策理論與方法 優(yōu)化決策理論與方法約束非線性規(guī)劃 — 標(biāo)準(zhǔn)型v 其中 f(x)是目標(biāo)函數(shù)， gi(x)和 hj(x)為約束函數(shù) (約束條件 )。,39。決策理論與方法 優(yōu)化決策理論與方法無約束非線性規(guī)劃 — Matlab函數(shù)應(yīng)用v Optimization ToolBoxMin f(x)v Matlab提供了兩個求解無約束非線性規(guī)劃的函數(shù)? [x,fval] = fminunc(fun,x0)? [x,fval] = fminsearch(fun,x0)v 用法相似，算法內(nèi)部的搜索策略不同。? 收斂性檢驗 ：計算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計算 G(xk)。v 充分條件 。60]。基于這兩點， Karmarkar構(gòu)造了一種稱為 投影尺度算法 的內(nèi)點算法。若是，算法結(jié)束；否則尋找下一個極點（確定 入基變量 和 出基變量 ），直至找到目標(biāo)解。v 動態(tài)規(guī)劃 與 多層規(guī)劃 ：若決策是分成多個階段完成的，前后階段之間相互影響，則稱為動態(tài)規(guī)劃；若決策是分成多個層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。v 決策的已知變量 ：? 決策變量及其取值范圍v 解決問題的主要理論方法 ：最優(yōu)化理論與方法v 注： 最優(yōu)化理論與方法（數(shù)學(xué)規(guī)劃）也可以求解不確定性決策問題、隨機性決策問題決策理論與方法 優(yōu)化決策理論與方法確定性決策v 優(yōu)化決策方法的問題求解過程? 辨識目標(biāo) C，確定優(yōu)化的標(biāo)準(zhǔn)，如：利潤、時間、能量等? 確定影響決策目標(biāo)的決策變量 x，形成目標(biāo)函數(shù) C=f(x)