優(yōu)化決策理論與方法

優(yōu)化決策理論與方法第一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法確定性決策確定性決策：指未來狀態(tài)是確定的（即只有一種狀態(tài)）一類決策問題，每一個(gè)行動(dòng)方案對應(yīng)著一個(gè)確定的結(jié)果值，此時(shí)決策函數(shù)僅依賴于決策變量。特點(diǎn)：狀態(tài)是確定的；決策問題變?yōu)閮?yōu)化問題。決策的已知變量：決策變量及其取值范圍解決問題的主要理論方法：最優(yōu)化理論與方法注：最優(yōu)化理論與方法（數(shù)學(xué)規(guī)劃）也可以求解不確定性決策問題、隨機(jī)性決策問題第二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法確定性決策優(yōu)化決策方法的問題求解過程辨識目標(biāo)C，確定優(yōu)化的標(biāo)準(zhǔn)，如：利潤、時(shí)間、能量等確定影響決策目標(biāo)的決策變量x，形成目標(biāo)函數(shù)C=f(x)明確決策變量的取值范圍，形成約束函數(shù)設(shè)計(jì)求解算法，尋找決策目標(biāo)在決策變量所受限制的范圍內(nèi)的極小化或極大化。最優(yōu)化問題的一般形式為：第三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法優(yōu)化問題分類可行點(diǎn)與可行域：滿足約束條件的x稱為可行點(diǎn)，所有可行點(diǎn)的集合稱為可行域，記為S；約束優(yōu)化與無約束優(yōu)化：當(dāng)SRn時(shí)，稱為約束優(yōu)化；當(dāng)S=Rn時(shí)，稱為無約束優(yōu)化；多目標(biāo)優(yōu)化：若f是多個(gè)目標(biāo)函數(shù)構(gòu)成的一個(gè)向量值函數(shù)，則稱為多目標(biāo)規(guī)劃；線性規(guī)劃與非線性規(guī)劃：當(dāng)f,g,h均為線性函數(shù)時(shí)稱為線性規(guī)劃，否則稱為非線性規(guī)劃。第四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法優(yōu)化問題分類整數(shù)規(guī)劃：當(dāng)決策變量的取值均為整數(shù)時(shí)稱為整數(shù)規(guī)劃；若某些變量取值為整數(shù)，而另一些變量取值為實(shí)數(shù)，則成為混合整數(shù)規(guī)劃。動(dòng)態(tài)規(guī)劃與多層規(guī)劃：若決策是分成多個(gè)階段完成的，前后階段之間相互影響，則稱為動(dòng)態(tài)規(guī)劃；若決策是分成多個(gè)層次完成的，不同層次之間相互影響，則稱為多層規(guī)劃。第五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標(biāo)規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃第六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—管理實(shí)例(食譜問題)假設(shè)市場上有n種不同的食物，第j種食物的單價(jià)為cj。人體正常活動(dòng)過程中需要m種基本的營養(yǎng)成分，且每人每天至少需要攝入第i種營養(yǎng)成分bi個(gè)單位。已知第j種食物中包含第i種營養(yǎng)成分的量為aij個(gè)單位。問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經(jīng)濟(jì)？設(shè)食譜中包含第j種食物的量為xj，則：第七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—標(biāo)準(zhǔn)型第八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—單純形算法解空間分析可行域分析：n維空間；第一象限；m個(gè)超平面。最優(yōu)解分析：在端點(diǎn)(或稱為極點(diǎn)。極點(diǎn)向量中，至少有n-m個(gè)0分量)處取極值。單純形算法的基本思想從某個(gè)極點(diǎn)開始獲得一個(gè)可行解；判斷該可行解是不是目標(biāo)解。若是，算法結(jié)束；否則尋找下一個(gè)極點(diǎn)（確定入基變量和出基變量），直至找到目標(biāo)解。第九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—內(nèi)點(diǎn)算法1972年，V.Klee和G.L.Minty指出Dantzig的單純形算法的迭代次數(shù)為O(2n)，是一個(gè)指數(shù)時(shí)間算法，不是優(yōu)良算法。那么是否存在求解線性規(guī)劃問題的多項(xiàng)式時(shí)間算法？1984年，N.Karmarkar提出了一種投影尺度算法，其計(jì)算效果能夠同單純形法相比較，掀起了線性規(guī)劃內(nèi)點(diǎn)算法的熱潮。第十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法的思想已知線性規(guī)劃問題的可行域是一個(gè)多面體，最優(yōu)點(diǎn)在多面體的某個(gè)極點(diǎn)取到。在給定初始可行解后，沿著什么樣的路徑到達(dá)最優(yōu)解呢？單純形法是從某個(gè)基可行解開始，沿著多面體的邊移動(dòng)最終找到最優(yōu)解。內(nèi)點(diǎn)算法的思想是從可行域內(nèi)的任意一點(diǎn)(任一可行解)出發(fā)，穿越可行域的內(nèi)部達(dá)到最優(yōu)解。N.Karmarkar的投影尺度算法就是一種典型的內(nèi)點(diǎn)算法。第十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—內(nèi)點(diǎn)算法可行域內(nèi)點(diǎn)初始基可行解基可行解目標(biāo)函數(shù)目標(biāo)函數(shù)最速下降方向第十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—內(nèi)點(diǎn)算法投影尺度算法如何穿過可行域的內(nèi)部快速達(dá)到最優(yōu)解呢？Karmarkar發(fā)現(xiàn)：(1)如果一個(gè)內(nèi)點(diǎn)位于可行域(多胞形、多面體)的中心，那么目標(biāo)函數(shù)的最速下降方向是比較好的方向；(2)存在一個(gè)適當(dāng)?shù)淖儞Q，能夠?qū)⒖尚杏蛑薪o定的內(nèi)點(diǎn)置于變換后的可行域的中心?；谶@兩點(diǎn)，Karmarkar構(gòu)造了一種稱為投影尺度算法的內(nèi)點(diǎn)算法。第十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—內(nèi)點(diǎn)算法X空間內(nèi)點(diǎn)目標(biāo)函數(shù)目標(biāo)函數(shù)最速下降方向Y1空間中心點(diǎn)投影尺度變換1目標(biāo)函數(shù)最速下降方向Y2空間中心點(diǎn)投影尺度變換2第十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—Matlab函數(shù)應(yīng)用OptimizationToolBoxMinfTxS.t.A·x≤bAeq·x=beqlb≤x≤ub其中：f,x,b,beq,lb和ub均為向量；A和Aeq為矩陣。[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)第十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法線性規(guī)劃—Matlab函數(shù)應(yīng)用例：maxz=x1+2x2S.t.x1+x2≤402x1+x2≤60x1≥0;x2≥0解：將max變?yōu)閙in，min–z=-x1-2x2則：f=[-1;-2];b=[40;60];lb=zeros(2,1);A=[11;21][x,fval]=linprog(f,A,b,[],[],lb)x=[0;40],fval=-80x1x2x1+x2=402x1+x2=60Z=x1+2x2第十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標(biāo)規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃第十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—標(biāo)準(zhǔn)型Minf(x);xRn其中f：Rn→R是一個(gè)非線性連續(xù)函數(shù)。對于任意點(diǎn)x*Rn,它是函數(shù)f的最小點(diǎn)(或局部極小點(diǎn))嗎？例如：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)第十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—極小值存在條件必要條件。設(shè)x*是f(x)的局部極小點(diǎn)，則當(dāng)f(x)在x*點(diǎn)可微時(shí)，梯度f(x*)=0；當(dāng)f(x)在x*點(diǎn)二階可微時(shí)，Hesse矩陣▽2f(x*)是半正定的，即dRn，有dT2f(x*)d0。充分條件。設(shè)f(x)在x*點(diǎn)二階可微，若梯度f(x*)=0且Hesse矩陣2f(x*)是正定的，則x*是f(x)的一個(gè)嚴(yán)格局部極小點(diǎn)。充要條件。設(shè)f(x)是可微凸函數(shù)，則x*是f(x)的全局最小點(diǎn)，當(dāng)且僅當(dāng)梯度f(x*)=0。第十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—復(fù)習(xí)梯度矩陣Hesse矩陣Taylor展開第二十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—牛頓法基本思想：在一個(gè)點(diǎn)附近，用目標(biāo)函數(shù)f(x)的二階Taylor多項(xiàng)式近似f(x)，并用該Taylor多項(xiàng)式的最小點(diǎn)近似f(x)的最小點(diǎn)。如果近似誤差比較大，那么可在近似最小點(diǎn)附近重新構(gòu)造f(x)的二階Taylor多項(xiàng)式(迭代)，據(jù)此尋找新的近似最小點(diǎn)，重復(fù)以上過程直到求得滿足一定精度要求的迭代點(diǎn)。第二十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—牛頓法設(shè)xk是第k次迭代結(jié)果，記gk=g(xk)=f(xk)；Gk=G(xk)=2f(xk)。則f(x)=f(xk+p)≈k(p)=f(xk)+g(xk)Tp+1/2pTG(xk)p由于k(p)的最小點(diǎn)滿足g(xk)+G(xk)p=0，得p=x-xk=-G-1(xk)g(xk)因此，可近似得到迭代關(guān)系：xk+1=xk-G-1(xk)g(xk)第二十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—牛頓法牛頓迭代法步驟初始化：給定一個(gè)初始點(diǎn)x0以及參數(shù)e>0；記k=0。收斂性檢驗(yàn)：計(jì)算g(xk)，若||g(xk)||≤e，則算法終止；否則計(jì)算G(xk)。迭代改進(jìn)：計(jì)算新的迭代點(diǎn)xk+1，即xk+1=xk-G-1(xk)g(xk)。k+1→k。返回收斂性檢驗(yàn)。第二十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—準(zhǔn)牛頓法牛頓法算法的優(yōu)點(diǎn)是收斂速度快(利用了Hesse矩陣)。但使用Hesse矩陣的不足之處是計(jì)算量大，Hesse矩陣可能非正定等，準(zhǔn)牛頓法(Quasi-Newtonmethod)是對牛頓法的改進(jìn)，目前被公認(rèn)為是比較有效的無約束優(yōu)化方法。基本思想：在迭代過程中只利用目標(biāo)函數(shù)f(x)和梯度g(x)的信息，構(gòu)造Hesse矩陣的近似矩陣，由此獲得一個(gè)搜索方向，生產(chǎn)新的迭代點(diǎn)。具體內(nèi)容請參考相關(guān)書籍。第二十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用OptimizationToolBoxMinf(x)Matlab提供了兩個(gè)求解無約束非線性規(guī)劃的函數(shù)[x,fval]=fminunc(fun,x0)[x,fval]=fminsearch(fun,x0)用法相似，算法內(nèi)部的搜索策略不同。fun為f(x)的函數(shù)形式，x0為初始解向量。第二十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用用法創(chuàng)建一個(gè)matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);然后調(diào)用fminunc或fminsearch并指定初始搜索點(diǎn)。x0=[x1,x2,…,xn][x,fval]=fminunc(@myfun,x0)或[x,fval]=fminsearch(@myfun,x0)第二十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)解：創(chuàng)建一個(gè)matlab文件，如myfun.mfunctionf=myfun(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);調(diào)用無約束非線性規(guī)劃函數(shù)x0=[-1,1];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fminunc(@myfun,x0,options);或者[x,fval]=

fminsearch(@myfun,x0,options);第二十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法無約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用fminunc結(jié)果：x=[0.5000-1.0000]fval=1.0983e-015iterations:8algorithm:'medium-scale:Quasi-Newtonlinesearch‘

fminsearch結(jié)果：x=[0.5000-1.0000]fval=5.1425e-010iterations:46algorithm:'Nelder-Meadsimplexdirectsearch'第二十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—標(biāo)準(zhǔn)型其中f(x)是目標(biāo)函數(shù)，gi(x)和hj(x)為約束函數(shù)(約束條件)。S={x|gi(x)0hj(x)=0}為可行域。有約束非線性規(guī)劃問題(COP)是指f(x),gi(x),hj(x)至少有一個(gè)是非線性的，且I或至少有一個(gè)為非空。第二十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—幾個(gè)概念積極(active)約束：設(shè)x0是COP問題的一個(gè)可行解，則它必須滿足所有約束條件。對于gi(x0)0，或者等號成立，或者大于號成立。稱等號成立的約束為積極約束(有效約束)，此時(shí)，x0處于該約束條件形成的可行域邊界上；稱大于號成立的約束為非積極(inactive)約束(無效約束)，此時(shí)，x0不在該約束條件形成的可行域邊界上。顯然所有hj(x0)約束均是積極約束。記J={j|gj(x0)=0hj(x0)=0}，稱為積極約束指標(biāo)集。第三十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—幾個(gè)概念可行方向。設(shè)x0為COP問題的任一可行解，對某一方向d來說，若0>0使得對于任意[0,0]，均有x0+dS，稱d為x0的一個(gè)可行方向。顯然若d滿足dTgi(x)0，dThj(x)=0，則d一定是可行方向。（可用一階Taylor公式分析）。下降方向。設(shè)x0S，對某一方向d來說，若0>0使得對于任意[0,0]，均有f(x0+d)<f(x0)，則稱d為x0點(diǎn)的一個(gè)下降方向。由f(x0+d)=f(x0)+(f(x0))Td+o()可知：若d滿足dTf(x0)<0，有f(x0+d)<f(x0)，則d一定是下降方向?？尚邢陆捣较?。若x0的某一方向d既是可行方向又是下降方向則稱其為可行下降方向。這個(gè)方向就是我們從x0出發(fā)尋求最優(yōu)解的搜索方向！第三十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—幾個(gè)概念例：minf(x)=x1+x2S.t.g(x)=1-x12-x220圖描述了該問題的相關(guān)概念。x1x2第三十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件一階必要條件幾何特征：若x*是COP問題的局部極小點(diǎn)且函數(shù)f(x),gi(x),hj(x)在x*處可微，則dTf(x*)0。d為x*的任意可行方向。f(x*+d)=f(x*)+(f(x*))Td+o()代數(shù)特征(KKT定理)：若x*是COP問題的局部極小點(diǎn)且函數(shù)f(x),gi(x),hj(x)在x*處可微，則存在實(shí)數(shù)i0(iI),jR(j)，使得：f(x*)=igi(x*)i+jhj(x*)j；gi(x*)i=0；i0，iI若x*滿足KKT條件，則稱x*為COP問題的一個(gè)KKT點(diǎn)，i,j稱為x*處的拉格朗日乘子。第三十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件一階充分條件設(shè)x*S，若函數(shù)f(x),gi(x),hj(x)在x*處可微，且對于x*的任意可行方向d，有dTf(x*)>0，則x*為COP問題的一個(gè)嚴(yán)格局部極小點(diǎn)。(凸規(guī)劃問題)設(shè)f(x)為凸函數(shù)，gi(x)為凹函數(shù)，hj(x)為線性函數(shù)。對于x*S，若函數(shù)f(x),gi(x)在x*處可微，且KKT條件成立，則x*為COP問題的全局最小點(diǎn)。第三十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件二階必要條件設(shè)x*是COP問題的局部極小點(diǎn)且滿足KKT條件。若函數(shù)f(x),gi(x),hj(x)在x*處二階可微，則必有：dTxx2L(x*,*,*)d0

其中，L(x,,)=f(x)-g(x)T-h(x)T,g(x),h(x)分別為由gi(x)和hj(x)構(gòu)成的向量值函數(shù)，,分別為對應(yīng)于g(x)和h(x)的拉格朗日乘子向量。二階充分條件設(shè)x*是COP問題的KKT點(diǎn)。*,*分別為對應(yīng)于g(x)和h(x)的拉格朗日乘子向量，且函數(shù)f(x),gi(x),hj(x)在x*處二階可微，若dTxx2L(x*,*,*)d>0,則x*為COP問題的一個(gè)嚴(yán)格局部極小點(diǎn)。第三十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—極小值存在條件例：minf(x)=x12+x22S.t.x1+x24x1,x20解：g1(x)=x1+x2-40;g2(x)=x10;g3(x)=x20f(x)=[2x1,2x2]T,g1(x)=[1,1]T,g2(x)=[1,0]T,g3(x)=[0,1]T,得到：2x1=1+22x2=1+3又(x1+x2-4)1=0；x12=0；x23=0；i0若1=0，則x1=x2=0，與題意不符；若1>0，則x1+x2-4=0，x1>0,x2>0。因此有2=3=0，所以x1=x2=1/2，得x1=x2=2，x*=[2,2]T為該問題的唯一KKT點(diǎn)。根據(jù)凸規(guī)劃充分條件知x*為全局最小點(diǎn)。第三十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法上面例題介紹了通過求解KKT方程獲得問題解的方法，但KKT方程并不總是很好求解。下面介紹幾種約束優(yōu)化的求解方法：可行方向法、序列無約束化法和SQP法。可行方向法的應(yīng)用條件：要求所有約束均為線性約束（稱為線性約束的優(yōu)化問題，LCO）?？尚蟹较蚍ǖ幕舅枷耄寒?dāng)某個(gè)可行方向同時(shí)也是目標(biāo)函數(shù)的下降方向時(shí)，沿此方向移動(dòng)一定會(huì)在滿足可行性的情況下改進(jìn)迭代點(diǎn)的目標(biāo)函數(shù)值。第三十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法x1x2第三十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法LCO問題：

Minf(x)S.t.aiTxbi,iI

ajTx=bj,j設(shè)x0是LCO的一個(gè)可行解，若d是可行域在x0點(diǎn)的可行方向，則d滿足AI(x0)d0(I(x0)={i|aiTx0=bi,iI})，Ad=0。設(shè)x0是LCO的一個(gè)可行解，若d是可行域在x0點(diǎn)的下降方向，則d滿足dTf(x0)<0。第三十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—可行方向法Zoutendijk可行方向法：其核心思想是通過求解下列線性規(guī)劃問題，在可行方向的某個(gè)范圍內(nèi)獲得目標(biāo)函數(shù)的最速下降方向。MindTf(x0)S.t.AI(x0)d0,I(x0)={i|aiTx0=bi,iI}Ad=0||d||∞1可以證明：當(dāng)x0取得KKT點(diǎn)時(shí)當(dāng)且僅當(dāng)dTf(x0)的最優(yōu)值為零。第四十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法求解約束優(yōu)化的一類重要方法是用一個(gè)無約束優(yōu)化問題的序列逼近約束優(yōu)化問題，通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解?；舅枷耄簩⒓s束條件通過某種轉(zhuǎn)換與目標(biāo)函數(shù)合并形成一個(gè)無約束優(yōu)化問題。這種轉(zhuǎn)換隱含著某種懲罰，即x偏離約束條件越遠(yuǎn)，受到的懲罰越大。因此也將此類方法稱為罰函數(shù)法，所形成的無約束優(yōu)化函數(shù)成為罰函數(shù)。第四十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法二次罰函數(shù)法：罰函數(shù)：其中(gi)-=max{0,-gi}，稱為罰參數(shù)，且當(dāng)→0時(shí)，Q(x,)的極小值趨于f(x)的極小值。第四十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法例：minf=x1+x2S.t.x1-x22=0解：對于>0，定義二次罰函數(shù)MinQ(x,)=x1+x2+(2)-1(x1-x22)2Q’x1=1+(x1-x22)/=0Q’x2=1-2x2(x1-x22)/=0解得：x*=(1/4-,-1/2)T,Q*=-1/4-/2當(dāng)→0時(shí)得，x*=(1/4,-1/2)T,f*=-1/4第四十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法對數(shù)障礙函數(shù)法：障礙函數(shù)：其中稱為障礙參數(shù)，且當(dāng)→0時(shí)，P(x,)的極小值趨于f(x)的極小值。該方法的適用性：COP問題僅包含不等式約束函數(shù)，且可行域存在內(nèi)點(diǎn)。即S0={x|g(x)>0}≠第四十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—序列無約束化法例：min{f=x/2|x1}解：構(gòu)造對數(shù)障礙函數(shù)P(x,)=x/2-ln(x-1)P’x=1/2-/(x-1)=0，得x*=1+2，P*=1/2+-ln2當(dāng)→0時(shí)得x*=1，f*=1/2第四十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—標(biāo)準(zhǔn)型若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量x的二次函數(shù)且所有約束均為線性約束，稱此類非線性規(guī)劃問題為二次規(guī)劃(QuadraticProgramming,QP)問題。其標(biāo)準(zhǔn)型為：第四十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—標(biāo)準(zhǔn)型其中Q=QTRn×n（n階對稱方陣）；以aiT(iI)為行向量的矩陣記為AIRI×n；以ajT(j)為行向量的矩陣記為AR×n；對應(yīng)的向量記為bI,b。若目標(biāo)函數(shù)的Hesse矩陣Q是半正定(或正定)的，則QP問題為(嚴(yán)格)凸二次規(guī)劃(CQP)。我們僅討論凸二次規(guī)劃問題，因?yàn)榉峭苟我?guī)劃的Q存在負(fù)特征根，求解很困難。第四十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—極小點(diǎn)存在條件充要條件可行點(diǎn)x*是QP問題的局部極小點(diǎn)當(dāng)且僅當(dāng)x*為一個(gè)KKT點(diǎn)且對于任意非零可行方向d，有dTQd0。對于凸二次規(guī)劃，x*為全局極小點(diǎn)當(dāng)且僅當(dāng)x*為局部極小點(diǎn)，當(dāng)且僅當(dāng)x*為KKT點(diǎn)。二次規(guī)劃的KKT定理形式為：Qx*+c=AIT*+AT*(AIx*-bI)*=0二次規(guī)劃的求解本質(zhì)上就是求解上述KKT方程。第四十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法對于非線性約束優(yōu)化(COP)問題，若x*是COP問題的一個(gè)局部最優(yōu)解，則它對應(yīng)一個(gè)純等式約束優(yōu)化問題第四十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法因此如果事先知道積極約束指標(biāo)集，那么帶有不等式約束優(yōu)化問題就可以轉(zhuǎn)化為純等式約束優(yōu)化問題，并可用準(zhǔn)牛頓法求解，這就是逐次二次規(guī)劃(SequentialQuadraticProgramming，SQP)法。基本思想：在迭代點(diǎn)處構(gòu)造一個(gè)二次規(guī)劃子問題，近似原來的約束優(yōu)化問題；然后通過求解該二次規(guī)劃子問題獲得約束優(yōu)化問題的一個(gè)改進(jìn)迭代點(diǎn)；不斷重復(fù)此過程，直到求出滿足一定要求的迭代點(diǎn)。第五十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法對于等式約束優(yōu)化問題Minf(x)S.t.h(x)=0拉格朗日函數(shù)記為L(x,)=f(x)-Th(x)則L(x,)=(f(x)-h(x),-h(x))T=0，顯然問題的最優(yōu)解(x*,*)滿足此式。設(shè)(xk,k)是第k次迭代結(jié)果，根據(jù)牛頓法，有：第五十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—SQP法上述迭代過程等價(jià)于如下的二次規(guī)劃的迭代。設(shè)給定迭代點(diǎn)(xk,k)，則第五十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用OptimizationToolBoxMinf(x)s.t.c(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)fun定義目標(biāo)函數(shù),x0定義初始可行解，nonlcon定義c(x)和ceq(x)。第五十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用用法創(chuàng)建一個(gè)matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);創(chuàng)建另一個(gè)matlab文件，如confun.mfunction[c,ceq]=confun(x)c=c(x);ceq=ceq(x);調(diào)用fmincon并指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;[x,fval]=fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@confun)第五十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)S.t.x1x2-x1-x2-1.5x1x2-10解：創(chuàng)建一個(gè)matlab文件，如myfun.mfunctionf=myfun(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);創(chuàng)建另一個(gè)matlab文件，如confun.mfunction[c,ceq]=confun(x)c=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];ceq=[];第五十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法約束非線性規(guī)劃—Matlab函數(shù)應(yīng)用調(diào)用有約束非線性規(guī)劃函數(shù)x0=[-1,1];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fmincon(@objfun,x0,[],[],[],[],[],[],@confun,options)運(yùn)行結(jié)果：x=[-9.54741.0474]fval=0.0236iterations:8algorithm:'medium-scale:SQP,Quasi-Newton,line-search'第五十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數(shù)應(yīng)用OptimizationToolBoxMin0.5xTHx+fTxs.t.A·xbAeq·x=beqlbxub[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)x0定義初始可行解(可選)第五十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數(shù)應(yīng)用用法首先要將目標(biāo)函數(shù)轉(zhuǎn)換成二次規(guī)劃標(biāo)準(zhǔn)型，從而得到H和f兩個(gè)矩陣。調(diào)用quadprog并根據(jù)需要指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)第五十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數(shù)應(yīng)用例：minf(x)=1/2x12+x22-x1x2-2x1-6x2)S.t.x1+x22

-x1+2x22

2x1+x23x1,x20解：改寫f(x)=1/2(x12+2x22-x1x2-x1x2)-2x1-6x2得：H=[1-1;-12],f=[-2;-6],x=[x1;x2];表示其它矩陣或向量A=[11;-12;21];b=[2;2;3];lb=[0;0];Aeq=[];beq=[];ub=[]。不指派初始解。第五十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法二次規(guī)劃—Matlab函數(shù)應(yīng)用調(diào)用二次規(guī)劃函數(shù)[x,fval]=quadprog(H,f,A,b,[],[],lb)運(yùn)行結(jié)果：x=[0.6667;1.3333]fval=-8.2222iterations:3algorithm:‘medium-scale:active-set(積極約束集方法)'第六十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標(biāo)規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃第六十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—管理實(shí)例(物資調(diào)度)假設(shè)物資調(diào)度部門計(jì)劃將某種物資從若干個(gè)存儲(chǔ)倉庫調(diào)運(yùn)到若干個(gè)銷售網(wǎng)點(diǎn)銷售?？紤]到物資的時(shí)效性和銷售效益，調(diào)度部門希望物資在運(yùn)輸過程中盡可能快地到達(dá)目的地；同時(shí)，考慮到運(yùn)輸成本，調(diào)度部門還希望物資的總運(yùn)輸費(fèi)用最小。試建立描述物資調(diào)運(yùn)過程的數(shù)學(xué)模型。解：設(shè)共有m個(gè)倉庫，第i個(gè)倉庫的物資庫存量為ai噸；有n個(gè)銷售網(wǎng)點(diǎn)，第j個(gè)銷售網(wǎng)點(diǎn)的銷售量為bj噸。第i個(gè)倉庫到第j個(gè)銷售網(wǎng)點(diǎn)的距離為dij，單位物資的運(yùn)費(fèi)為cij。設(shè)從第i個(gè)倉庫運(yùn)到第j個(gè)銷售網(wǎng)點(diǎn)的物資量為xij。第六十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—管理實(shí)例決策目標(biāo)：運(yùn)輸速度最快，可用噸公里數(shù)（可觀測變量）最小描述?？倗嵐飻?shù)為ijdijxij；運(yùn)輸費(fèi)用最小?？傔\(yùn)輸費(fèi)用為ijcijxij；約束條件每個(gè)倉庫的運(yùn)出量不超過倉庫的庫存量：jxijai；運(yùn)到每個(gè)銷售網(wǎng)點(diǎn)的量與其銷售能力相匹配：ixij=bj；每個(gè)倉庫的運(yùn)出量非負(fù)：xij0。第六十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—管理實(shí)例最后得到模型：模型包含2個(gè)目標(biāo)；mn個(gè)決策變量；mn+m+n個(gè)約束。第六十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—標(biāo)準(zhǔn)型多目標(biāo)規(guī)劃(multi-ObjectiveProgramming,MOP)就是指在決策變量滿足給定約束的條件下研究多個(gè)可數(shù)值化的目標(biāo)函數(shù)同時(shí)極小化(或極大化)的問題。其一般形式如下：Minf(x)=(f1(x),f2(x),…,fp(x))T，S.t.gi(x)0;iIhj(x)=0;j。第六十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Pareto最優(yōu)解設(shè)x*是可行域S上的一個(gè)點(diǎn)，對于xS，均有：fi(x*)fi(x)(i=1,…,p)，稱x*為MOP問題的絕對最優(yōu)解；若不存在xS，使得fi(x)fi(x*)(或fi(x)<fi(x*))(i=1,…,p)，則稱x*為MOP問題的有效解(或弱有效解)。有效解通常也稱為Pareto最優(yōu)解。Sx1x2f(S)f(S)f2f2f1f1絕對最優(yōu)解有效解弱有效解第六十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Pareto最優(yōu)解存在條件(必要條件)假設(shè)向量值函數(shù)f=[f1(x),…,fp(x)]T,g=[g1(x),…,g|I|(x)]T,h=[h1(x),…,h||(x)]T在x*S處可微，若x*是MOP問題的有效解或弱有效解，則存在向量R+p，R+|I|，R+||，使得(,,)≠0，且f(x*)=g(x*)+h(x*)Tg(x*)=0。第六十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—求解方法直接求解多目標(biāo)規(guī)劃問題的有效解集是NP-難問題。下面介紹多目標(biāo)規(guī)劃問題的間接解法，基本思路都是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為一個(gè)或多個(gè)單目標(biāo)優(yōu)化問題。基于一個(gè)單目標(biāo)問題的方法：將原來的多目標(biāo)規(guī)劃問題轉(zhuǎn)化成一個(gè)單目標(biāo)優(yōu)化問題，然后利用非線性優(yōu)化算法求解該單目標(biāo)問題，所得解作為MOP問題的最優(yōu)解。關(guān)鍵問題在于：保證所構(gòu)造的單目標(biāo)問題的最優(yōu)解是MOP問題的有效解或弱有效解。第六十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—求解方法線性加權(quán)和法：MinTf(x)=kkfk(x)，S.t.gi(x)0;iIhj(x)=0;j權(quán)重設(shè)置要求：kk=1,k0(k=1,2,…,p)。主要目標(biāo)法：Minf(x)=f1(x)，(不妨設(shè)f1(x)為主要目標(biāo))S.t.gi(x)0;iIhj(x)=0;jfk(x)uk,k=2,…,puk為專家經(jīng)驗(yàn)值。第六十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—求解方法極小化極大法：在目標(biāo)函數(shù)f(x)的p個(gè)分量中，極小化f(x)的最大分量，即minxSmax1jpfj(x)理想點(diǎn)法：分別求出f(x)中每個(gè)分量fj(x)的極小點(diǎn)fj0，得到理想點(diǎn)f0=(f10,…,fp0)T；然后求解單目標(biāo)優(yōu)化問題：minxS||f(x)-f0||。為范數(shù)的階，可取1，2，∞。第七十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—求解方法基于多個(gè)單目標(biāo)問題的方法：將原來的多目標(biāo)規(guī)劃問題轉(zhuǎn)化成具有一定次序的多個(gè)單目標(biāo)優(yōu)化問題，然后依次求解這些單目標(biāo)優(yōu)化問題，并把最后一個(gè)單目標(biāo)優(yōu)化問題的解作為MOP問題的最優(yōu)解。關(guān)鍵問題在于：保證最后一個(gè)單目標(biāo)優(yōu)化問題的最優(yōu)解是MOP問題的有效解或弱有效解。分層排序法：將目標(biāo)函數(shù)按重要度依次排序，然后在前一個(gè)目標(biāo)函數(shù)的最優(yōu)解集中尋找下一個(gè)目標(biāo)的最優(yōu)解集，并把最后一個(gè)目標(biāo)的最優(yōu)解作為MOP問題的最優(yōu)解。第七十一頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—求解方法minf1(x)，xS（不妨設(shè)f1(x)為第一層目標(biāo)），得到最優(yōu)解集S1;第j層：minfj(x),xSj-1，j=2,…,p最后將Sp中的點(diǎn)作為多目標(biāo)問題的最優(yōu)解。第七十二頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用OptimizationToolBoxMinmax{fi(x)}s.t.c(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)Fun定義目標(biāo)函數(shù)；x0定義初始可行解；nonlcon定義c(x)和ceq(x)。第七十三頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用用法創(chuàng)建一個(gè)matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);…;f(p)=fp(x)創(chuàng)建另一個(gè)matlab文件，如confun.mfunction[c,ceq]=confun(x)c=c(x);ceq=ceq(x);調(diào)用fminimax并指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;[x,fval]=fminimax(@myfun,x0,A,b,Aeq,beq,lb,ub,@confun)第七十四頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用OptimizationToolBoxMinx,

s.t.F(x)-weight·goalc(x)0ceq(x)=0A·xbAeq·x=beqlbxub[x,fval]=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)Fun定義目標(biāo)函數(shù)；goal為理想點(diǎn)；x0定義初始可行解；nonlcon定義c(x)和ceq(x)。weight為各目標(biāo)的權(quán)重向量。第七十五頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用用法創(chuàng)建一個(gè)matlab文件，如myfun.mfunctionf=myfun(x)f(1)=f1(x);f(2)=f2(x);…;f(p)=fp(x)創(chuàng)建另一個(gè)matlab文件，如confun.mfunction[c,ceq]=confun(x)c=c(x);ceq=ceq(x);調(diào)用fgoalattain并設(shè)定理想點(diǎn)、權(quán)重向量，指定初始搜索點(diǎn)以及其他向量、矩陣。x0=[x1,x2,…,xn];A;b;Aeq;beq;lb;ub;goal;weight[x,fval]=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,@confun)第七十六頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用例：min{f1,f2,f3,f4,f5}f(1)=2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304;f(2)=-x(1)^2-3*x(2)^2;f(3)=x(1)+3*x(2)-18;f(4)=-x(1)-x(2);f(5)=x(1)+x(2)-8;無約束。第七十七頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用解(1)：用fminimax求解。定義myfun.m指定初始搜索點(diǎn)：x0=[0.1;0.1]調(diào)用[x,fval]=fminimax(@myfun,x0)結(jié)果：x=[4.00004.0000]fval=[0.0000-64.0000-2.0000-8.0000-0.0000]iterations:7algorithm:'minimaxSQP,Quasi-Newton,line_search‘第七十八頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法多目標(biāo)規(guī)劃—Matlab函數(shù)應(yīng)用解(2)：用fgoalattain求解。定義myfun.m指定初始搜索點(diǎn)：x0=[0.1;0.1]指定理想點(diǎn)：goal=[1-60-5-10-1]指定權(quán)重：weight=abs(goal)調(diào)用[x,fval]=fgoalattain(@myfun,x0,goal,weight)結(jié)果：x=[3.97983.9596]fval=[1.9395-62.8754-2.1412-7.9395-0.0605]iterations:7algorithm:'goalattainmentSQP,Quasi-Newton,line_search'第七十九頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法優(yōu)化決策理論與方法1、線性規(guī)劃2、非線性規(guī)劃（約束和非約束）3、多目標(biāo)規(guī)劃4、組合優(yōu)化與整數(shù)規(guī)劃第八十頁，共八十八頁，編輯于2023年，星期五*-優(yōu)化決策理論與方法組合優(yōu)化