【正文】 : ‘mediumscale: activeset(積極約束集方法 )39。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Pareto最優(yōu)解 ?設 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)化問題的最優(yōu)解是 MOP問題的有效解或弱有效解。Aeq。A。minimax SQP, QuasiNewton, line_search‘ 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Matlab函數(shù)應用 ? 解 (2)：用 fgoalattain求解。 ? 解 ： as=(1 1 0 0 0)T； at=(0 0 0 1 1)T。x?b Aeq aij=1(vi為 ej的起點 )； aij=1(vi為 ej的終點 )； aij=0(其他情形 )。 ? 無約束。f(p)=f p(x) ? 創(chuàng)建另一個 matlab文件，如 function [c, ceq] = confun(x) c = c(x)。 ? 調(diào)用 fminimax并指定初始搜索點以及其他向量、矩陣。j?? fk(x)?uk, k=2,…, p ? uk為專家經(jīng)驗值。,1(0),1(),1(..m i n111 11 1njmixnjbxmiaxtsxcxdijmijijnjiijminjijijminjijij?????????????????????????? ?? ???? ?? ?2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 標準型 ?多目標規(guī)劃 (multiObjective Programming,MOP)就是指在決策變量滿足給定約束的條件下研究多個可數(shù)值化的目標函數(shù)同時極小化 (或極大化 )的問題。beq=[]。beq。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — Matlab函數(shù)應用 ? 調(diào)用有約束非線性規(guī)劃函數(shù) x0 = [1,1]。x=beq lb?x?ub ? [x,fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) ? fun定義目標函數(shù) ,x0定義初始可行解， nonlcon定義 c(x)和ceq(x)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 序列無約束化法 ?二次罰函數(shù)法 ： ? 罰函數(shù)： ? 其中 (gi)=max{0,gi}， ?稱為罰參數(shù)，且當 ?→ 0時， Q(x,?)的極小值趨于 f(x)的極小值。g2(x)=x1?0。 設 x0?S，對某一方向 d來說，若 ???00使得對于任意 ??[0,?0]，均有 f(x0+?d)f(x0)，則稱 d為 x0點的一個下降方向。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — Matlab函數(shù)應用 ? fminunc結(jié)果： ? x =[ ] ? fval = ? iterations: 8 ? algorithm: 39。但使用 Hesse矩陣的不足之處是計算量大，Hesse矩陣可能非正定等，準牛頓法 (QuasiNewton method)是對牛頓法的改進，目前被公認為是比較有效的無約束優(yōu)化方法。 x?Rn ?其中 f： Rn→R 是一個非線性連續(xù)函數(shù)。 ? 內(nèi)點算法的思想是從可行域內(nèi)的任意一點 (任一可行解 )出發(fā)，穿越可行域的內(nèi)部達到最優(yōu)解。 ? 最優(yōu)化問題的一般形式為： ??????jxhIixgtsxfjiRx n,0)(,0)(..)(m i n2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化問題分類 ?可行點 與 可行域 ：滿足約束條件的 x稱為可行點，所有可行點的集合稱為可行域，記為 S； ?約束優(yōu)化 與 無約束優(yōu)化 ：當 S?Rn時，稱為約束優(yōu)化；當 S=Rn時，稱為無約束優(yōu)化； ?多目標優(yōu)化 ：若 f是多個目標函數(shù)構成的一個向量值函數(shù)，則稱為多目標規(guī)劃； ?線性規(guī)劃 與 非線性規(guī)劃 ：當 f,g,h均為線性函數(shù)時稱為線性規(guī)劃，否則稱為非線性規(guī)劃。極點向量中，至少有nm個 0分量 )處取極值。2]。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 — 牛頓法 ?設 xk是第 k次迭代結(jié)果，記 gk=g(xk)=?f(xk)；Gk=G(xk)=?2f(xk)。 % Starting guess options = optimset(39。顯然所有 hj(x0)約束均是積極約束。 ? (凸規(guī)劃問題 )設 f(x)為凸函數(shù)， gi(x)為凹函數(shù)， hj(x)為線性函數(shù)。 ?設 x0是 LCO的一個可行解，若 d是可行域在 x0點的 下降方向 ，則 d滿足 dT?f(x0)0。 ? 二次規(guī)劃的 KKT定理形式為： Qx*+c=AIT?*+A?T?* (AIx*bI)?*=0 ?二次規(guī)劃的求解本質(zhì)上就是求解上述 KKT方程。beq。x?b Aeq2 1]。第 i個倉庫到第 j個銷售網(wǎng)點的距離為 dij，單位物資的運費為 cij。 ?基于一個單目標問題的方法 ：將原來的多目標規(guī)劃問題轉(zhuǎn)化成一個單目標優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標問題，所得解作為 MOP問題的最優(yōu)解。x?b Aeq??goal c(x)?0 ceq(x)=0 Aub。 ? 給定一個有限集 N={1,2,…,n} 和權函數(shù) c:N→R 。 ?線性混合整數(shù)規(guī)劃 (MILP)： max {cTx+hTy|Ax+Gy?b, x?Z+n, y?R+p} ? x,y為決策變量向量，其中 x包含 n個整數(shù)變量， y包含 p個實數(shù)變量； c為 n維向量； h為 p維向量； A為 m n階矩陣，G為 m p階矩陣。 ?整數(shù)規(guī)劃問題的可行解一定是松弛問題的可行解，但反之不一定。 ? 已經(jīng)證明：求解組合優(yōu)化問題的最優(yōu)解是 NP難的。weight [x,fval]=fgoalattain(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun) 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Matlab函數(shù)應用 ?例： min {f1,f2,f3,f4,f5} f(1)= 2*x(1)^2+x(2)^248*x(1)40*x(2)+304。x=beq lb?x?ub ? [x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) ? Fun定義目標函數(shù)； goal為理想點； x0定義初始可行解；nonlcon定義 c(x)和 ceq(x)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — Matlab函數(shù)應用 ? 用法 ? 創(chuàng)建一個 matlab文件，如 function f = myfun(x) f(1) = f1(x)。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 求解方法 ?線性加權和法 ： Min ?Tf(x)=?k?kfk(x)， . gi(x)?0。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 多目標規(guī)劃 — 管理實例 ?決策目標： ? 運輸速度最快，可用噸公里數(shù)（ 可觀測變量 ）最小描述。2。 ? 調(diào)用 quadprog并根據(jù)需要指定初始搜索點以及其他向量、矩陣。ub。 ?基本思想 ：在迭代點處構造一個二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個改進迭代點；不斷重復此過程，直到求出滿足一定要求的迭代點。 Min dT?f(x0) . AI(x0)d?0, I(x0)={i|aiTx0=bi,i?I} A?d=0 ||d||∞?1 ?可以證明：當 x0取得 KKT點時當且僅當 dT?f(x0)的最優(yōu)值為零。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 極小值存在條件 ? 二階必要條件 ? 設 x*是 COP問題的局部極小點且滿足 KKT條件。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 — 幾個概念 ? 可行方向 。,39。 ? 收斂性檢驗 ：計算 g(xk)，若 ||g(xk)||≤e，則算法終止；否則計算 G(xk)。60]。若是，算法結(jié)束；否則尋找下一個極點（確定 入基變量 和 出基變量 ），直至找到目標解。 ?特點 ：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。 2021年 6月 15日 1時 47分 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 — 內(nèi)點算法 ?內(nèi)點算法的思想 ? 已知線性規(guī)劃問題的可行域是一個多面體，最優(yōu)點在多面體的某個極點取到。2 1] [x, fval] = linprog(f,A,b,[],[],lb) x=[0。返回收斂性檢驗。 [x,fval] = fminunc(myfun,x0,options)。（可用一階 Taylor公式分析）。 ?*,?*分別為對應于 g(x)和 h(x)的拉格朗日乘子向量，且 函數(shù) f(x), gi(x), hj(x)在 x*處二階可微，若 dT?xx2L(x*,?*,?*)d0,則 x*為 COP問題的一個嚴格局部極小點。這種轉(zhuǎn)換隱含著某種懲罰，即 x偏離約束條件越遠，受到的懲罰越大。設給定迭代點(xk,?k)，則 0)()(..,)(),(21m