優(yōu)化決策理論與方法(ppt 90頁).ppt

決策理論與方法 2 優(yōu)化決策理論與方法 合肥工業(yè)大學(xué)管理學(xué)院2020年3月14日 決策理論與方法 優(yōu)化決策理論與方法 確定性決策 確定性決策 指未來狀態(tài)是確定的 即只有一種狀態(tài) 一類決策問題 每一個(gè)行動方案對應(yīng)著一個(gè)確定的結(jié)果值 此時(shí)決策函數(shù)僅依賴于決策變量 特點(diǎn) 狀態(tài)是確定的 決策問題變?yōu)閮?yōu)化問題 決策的已知變量 決策變量及其取值范圍解決問題的主要理論方法 最優(yōu)化理論與方法注 最優(yōu)化理論與方法 數(shù)學(xué)規(guī)劃 也可以求解不確定性決策問題 隨機(jī)性決策問題 決策理論與方法 優(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)化問題的一般形式為 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化問題分類 可行點(diǎn)與可行域 滿足約束條件的x稱為可行點(diǎn) 所有可行點(diǎn)的集合稱為可行域 記為S 約束優(yōu)化與無約束優(yōu)化 當(dāng)S Rn時(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ī)劃 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化問題分類 整數(shù)規(guī)劃 當(dāng)決策變量的取值均為整數(shù)時(shí)稱為整數(shù)規(guī)劃 若某些變量取值為整數(shù) 而另一些變量取值為實(shí)數(shù) 則成為混合整數(shù)規(guī)劃 動態(tài)規(guī)劃與多層規(guī)劃 若決策是分成多個(gè)階段完成的 前后階段之間相互影響 則稱為動態(tài)規(guī)劃 若決策是分成多個(gè)層次完成的 不同層次之間相互影響 則稱為多層規(guī)劃 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 1 線性規(guī)劃2 非線性規(guī)劃 約束和非約束 3 多目標(biāo)規(guī)劃4 組合優(yōu)化與整數(shù)規(guī)劃 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 管理實(shí)例 食譜問題 假設(shè)市場上有n種不同的食物 第j種食物的單價(jià)為cj 人體正常活動過程中需要m種基本的營養(yǎng)成分 且每人每天至少需要攝入第i種營養(yǎng)成分bi個(gè)單位 已知第j種食物中包含第i種營養(yǎng)成分的量為aij個(gè)單位 問在滿足人體基本營養(yǎng)需求的前提下什么樣的配食方案最經(jīng)濟(jì) 設(shè)食譜中包含第j種食物的量為xj 則 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 標(biāo)準(zhǔn)型 決策理論與方法 優(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)解 決策理論與方法 優(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)算法的熱潮 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 內(nèi)點(diǎn)算法 內(nèi)點(diǎn)算法的思想已知線性規(guī)劃問題的可行域是一個(gè)多面體 最優(yōu)點(diǎn)在多面體的某個(gè)極點(diǎn)取到 在給定初始可行解后 沿著什么樣的路徑到達(dá)最優(yōu)解呢 單純形法是從某個(gè)基可行解開始 沿著多面體的邊移動最終找到最優(yōu)解 內(nèi)點(diǎn)算法的思想是從可行域內(nèi)的任意一點(diǎn) 任一可行解 出發(fā) 穿越可行域的內(nèi)部達(dá)到最優(yōu)解 N Karmarkar的投影尺度算法就是一種典型的內(nèi)點(diǎn)算法 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 內(nèi)點(diǎn)算法 可行域 內(nèi)點(diǎn) 初始基可行解 基可行解 目標(biāo)函數(shù) 目標(biāo)函數(shù)最速下降方向 決策理論與方法 優(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)算法 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 線性規(guī)劃 Matlab函數(shù)應(yīng)用 例 maxz x1 2x2S t x1 x2 402x1 x2 60 x1 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 80 x1 x2 x1 x2 40 2x1 x2 60 Z x1 2x2 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 1 線性規(guī)劃2 非線性規(guī)劃 約束和非約束 3 多目標(biāo)規(guī)劃4 組合優(yōu)化與整數(shù)規(guī)劃 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 標(biāo)準(zhǔn)型 Minf x x Rn其中f Rn R是一個(gè)非線性連續(xù)函數(shù) 對于任意點(diǎn)x Rn 它是函數(shù)f的最小點(diǎn) 或局部極小點(diǎn) 嗎 例如 minf x ex1 4x12 2x22 4x1x2 2x2 1 決策理論與方法 優(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 是半正定的 即 d Rn 有dT 2f x d 0 充分條件 設(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 決策理論與方法 優(yōu)化決策理論與方法 無約束非線性規(guī)劃 復(fù)習(xí) 梯度矩陣 Hesse矩陣 Taylor展開 決策理論與方法 優(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) 決策理論與方法 優(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 決策理論與方法 優(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) 決策理論與方法 優(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)書籍 決策理論與方法 優(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為初始解向量 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 標(biāo)準(zhǔn)型 其中f x 是目標(biāo)函數(shù) gi x 和hj x 為約束函數(shù) 約束條件 S x gi x 0 hj x 0 為可行域 有約束非線性規(guī)劃問題 COP 是指f x gi x hj x 至少有一個(gè)是非線性的 且I或 至少有一個(gè)為非空 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 幾個(gè)概念 積極 active 約束 設(shè)x0是COP問題的一個(gè)可行解 則它必須滿足所有約束條件 對于gi x0 0 或者等號成立 或者大于號成立 稱等號成立的約束為積極約束 有效約束 此時(shí) x0處于該約束條件形成的可行域邊界上 稱大于號成立的約束為非積極 inactive 約束 無效約束 此時(shí) x0不在該約束條件形成的可行域邊界上 顯然所有hj x0 約束均是積極約束 記J j gj x0 0 hj x0 0 稱為積極約束指標(biāo)集 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 幾個(gè)概念 可行方向 設(shè)x0為COP問題的任一可行解 對某一方向d來說 若 0 0使得對于任意 0 0 均有x0 d S 稱d為x0的一個(gè)可行方向 顯然若d滿足dT gi x 0 dT hj x 0 則d一定是可行方向 可用一階Taylor公式分析 下降方向 設(shè)x0 S 對某一方向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滿足dT f x0 0 有f x0 d f x0 則d一定是下降方向 可行下降方向 若x0的某一方向d既是可行方向又是下降方向則稱其為可行下降方向 這個(gè)方向就是我們從x0出發(fā)尋求最優(yōu)解的搜索方向 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 幾個(gè)概念 例 minf x x1 x2S t g x 1 x12 x22 0圖描述了該問題的相關(guān)概念 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 極小值存在條件 一階必要條件幾何特征 若x 是COP問題的局部極小點(diǎn)且函數(shù)f x gi x hj x 在x 處可微 則dT f 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ù) i 0 i I j R j 使得 f x i gi x i j hj x j gi x i 0 i 0 i I若x 滿足KKT條件 則稱x 為COP問題的一個(gè)KKT點(diǎn) i j稱為x 處的拉格朗日乘子 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 極小值存在條件 一階充分條件設(shè)x S 若函數(shù)f x gi x hj x 在x 處可微 且對于x 的任意可行方向d 有dT f 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) 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 極小值存在條件 二階必要條件設(shè)x 是COP問題的局部極小點(diǎn)且滿足KKT條件 若函數(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ù) 分別為對應(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 處二階可微 若dT xx2L x d 0 則x 為COP問題的一個(gè)嚴(yán)格局部極小點(diǎn) 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 極小值存在條件 例 minf x x12 x22S t x1 x2 4x1 x2 0解 g1 x x1 x2 4 0 g2 x x1 0 g3 x x2 0 f 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 x1 2 0 x2 3 0 i 0若 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) 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 可行方向法 上面例題介紹了通過求解KKT方程獲得問題解的方法 但KKT方程并不總是很好求解 下面介紹幾種約束優(yōu)化的求解方法 可行方向法 序列無約束化法和SQP法 可行方向法的應(yīng)用條件 要求所有約束均為線性約束 稱為線性約束的優(yōu)化問題 LCO 可行方向法的基本思想 當(dāng)某個(gè)可行方向同時(shí)也是目標(biāo)函數(shù)的下降方向時(shí) 沿此方向移動一定會在滿足可行性的情況下改進(jìn)迭代點(diǎn)的目標(biāo)函數(shù)值 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 可行方向法 x1 x2 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 可行方向法 LCO問題 Minf x S t aiTx bi i IajTx bj j 設(shè)x0是LCO的一個(gè)可行解 若d是可行域在x0點(diǎn)的可行方向 則d滿足AI x0 d 0 I x0 i aiTx0 bi i I A d 0 設(shè)x0是LCO的一個(gè)可行解 若d是可行域在x0點(diǎn)的下降方向 則d滿足dT f x0 0 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 可行方向法 Zoutendijk可行方向法 其核心思想是通過求解下列線性規(guī)劃問題 在可行方向的某個(gè)范圍內(nèi)獲得目標(biāo)函數(shù)的最速下降方向 MindT f x0 S t AI x0 d 0 I x0 i aiTx0 bi i I A d 0 d 1可以證明 當(dāng)x0取得KKT點(diǎn)時(shí)當(dāng)且僅當(dāng)dT f x0 的最優(yōu)值為零 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 序列無約束化法 求解約束優(yōu)化的一類重要方法是用一個(gè)無約束優(yōu)化問題的序列逼近約束優(yōu)化問題 通過無約束優(yōu)化問題的最優(yōu)解序列逼近約束優(yōu)化問題的最優(yōu)解 基本思想 將約束條件通過某種轉(zhuǎn)換與目標(biāo)函數(shù)合并形成一個(gè)無約束優(yōu)化問題 這種轉(zhuǎn)換隱含著某種懲罰 即x偏離約束條件越遠(yuǎn) 受到的懲罰越大 因此也將此類方法稱為罰函數(shù)法 所形成的無約束優(yōu)化函數(shù)成為罰函數(shù) 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 序列無約束化法 二次罰函數(shù)法 罰函數(shù) 其中 gi max 0 gi 稱為罰參數(shù) 且當(dāng) 0時(shí) Q x 的極小值趨于f x 的極小值 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 序列無約束化法 例 min f x 2 x 1 解 構(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 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 標(biāo)準(zhǔn)型 若有約束非線性規(guī)劃的目標(biāo)函數(shù)是決策變量x的二次函數(shù)且所有約束均為線性約束 稱此類非線性規(guī)劃問題為二次規(guī)劃 QuadraticProgramming QP 問題 其標(biāo)準(zhǔn)型為 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 標(biāo)準(zhǔn)型 其中Q QT Rn n n階對稱方陣 以aiT i I 為行向量的矩陣記為AI RI n 以ajT j 為行向量的矩陣記為A R n 對應(yīng)的向量記為bI b 若目標(biāo)函數(shù)的Hesse矩陣Q是半正定 或正定 的 則QP問題為 嚴(yán)格 凸二次規(guī)劃 CQP 我們僅討論凸二次規(guī)劃問題 因?yàn)榉峭苟我?guī)劃的Q存在負(fù)特征根 求解很困難 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 極小點(diǎn)存在條件 充要條件可行點(diǎn)x 是QP問題的局部極小點(diǎn)當(dāng)且僅當(dāng)x 為一個(gè)KKT點(diǎn)且對于任意非零可行方向d 有dTQd 0 對于凸二次規(guī)劃 x 為全局極小點(diǎn)當(dāng)且僅當(dāng)x 為局部極小點(diǎn) 當(dāng)且僅當(dāng)x 為KKT點(diǎn) 二次規(guī)劃的KKT定理形式為 Qx c AIT A T AIx bI 0二次規(guī)劃的求解本質(zhì)上就是求解上述KKT方程 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 SQP法 對于非線性約束優(yōu)化 COP 問題 若x 是COP問題的一個(gè)局部最優(yōu)解 則它對應(yīng)一個(gè)純等式約束優(yōu)化問題 決策理論與方法 優(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) 決策理論與方法 優(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ù)牛頓法 有 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 SQP法 上述迭代過程等價(jià)于如下的二次規(guī)劃的迭代 設(shè)給定迭代點(diǎn) xk k 則 決策理論與方法 優(yōu)化決策理論與方法 約束非線性規(guī)劃 Matlab函數(shù)應(yīng)用 OptimizationToolBoxMinf x s t c x 0ceq x 0A x bAeq x beqlb x ub x fval fmincon fun x0 A b Aeq beq lb ub nonlcon fun定義目標(biāo)函數(shù) x0定義初始可行解 nonlcon定義c x 和ceq x 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 Matlab函數(shù)應(yīng)用 OptimizationToolBoxMin0 5xTHx fTxs t A x bAeq x beqlb x ub x fval quadprog H f A b Aeq beq lb ub x0 x0定義初始可行解 可選 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 二次規(guī)劃 Matlab函數(shù)應(yīng)用 例 minf x 1 2x12 x22 x1x2 2x1 6x2 S t x1 x2 2 x1 2x2 22x1 x2 3x1 x2 0解 改寫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 不指派初始解 決策理論與方法 優(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 積極約束集方法 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 1 線性規(guī)劃2 非線性規(guī)劃 約束和非約束 3 多目標(biāo)規(guī)劃4 組合優(yōu)化與整數(shù)規(guī)劃 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 管理實(shí)例 物資調(diào)度 假設(shè)物資調(diào)度部門計(jì)劃將某種物資從若干個(gè)存儲倉庫調(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 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 管理實(shí)例 決策目標(biāo) 運(yùn)輸速度最快 可用噸公里數(shù) 可觀測變量 最小描述 總噸公里數(shù)為 i jdijxij 運(yùn)輸費(fèi)用最小 總運(yùn)輸費(fèi)用為 i jcijxij 約束條件每個(gè)倉庫的運(yùn)出量不超過倉庫的庫存量 jxij ai 運(yùn)到每個(gè)銷售網(wǎng)點(diǎn)的量與其銷售能力相匹配 ixij bj 每個(gè)倉庫的運(yùn)出量非負(fù) xij 0 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 管理實(shí)例 最后得到模型 模型包含2個(gè)目標(biāo) mn個(gè)決策變量 mn m n個(gè)約束 決策理論與方法 優(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 i Ihj x 0 j 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 Pareto最優(yōu)解 設(shè)x 是可行域S上的一個(gè)點(diǎn) 對于 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問題的有效解 或弱有效解 有效解通常也稱為Pareto最優(yōu)解 S x1 x2 f S f S f2 f2 f1 f1 絕對最優(yōu)解 有效解 弱有效解 決策理論與方法 優(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 決策理論與方法 優(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問題的有效解或弱有效解 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 求解方法 線性加權(quán)和法 Min Tf x k kfk x S t gi x 0 i Ihj x 0 j 權(quán)重設(shè)置要求 k k 1 k 0 k 1 2 p 主要目標(biāo)法 Minf x f1 x 不妨設(shè)f1 x 為主要目標(biāo) S t gi x 0 i Ihj x 0 j fk x uk k 2 puk為專家經(jīng)驗(yàn)值 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 求解方法 極小化極大法 在目標(biāo)函數(shù)f x 的p個(gè)分量中 極小化f x 的最大分量 即minx Smax1 j pfj x 理想點(diǎn)法 分別求出f x 中每個(gè)分量fj x 的極小點(diǎn)fj0 得到理想點(diǎn)f0 f10 fp0 T 然后求解單目標(biāo)優(yōu)化問題 minx S f x f0 為范數(shù)的階 可取1 2 決策理論與方法 優(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)解 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 求解方法 minf1 x x S 不妨設(shè)f1 x 為第一層目標(biāo) 得到最優(yōu)解集S1 第j層 minfj x x Sj 1 j 2 p最后將Sp中的點(diǎn)作為多目標(biāo)問題的最優(yōu)解 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 Matlab函數(shù)應(yīng)用 OptimizationToolBoxMinmax fi x s t c x 0ceq x 0A x bAeq x beqlb x ub x fval fminimax fun x0 A b Aeq beq lb ub nonlcon Fun定義目標(biāo)函數(shù) x0定義初始可行解 nonlcon定義c x 和ceq x 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 多目標(biāo)規(guī)劃 Matlab函數(shù)應(yīng)用 OptimizationToolBoxMinx s t F x weight goalc x 0ceq x 0A x bAeq x beqlb x ub 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)重向量 決策理論與方法 優(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 決策理論與方法 優(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 無約束 決策理論與方法 優(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 決策理論與方法 優(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 決策理論與方法 優(yōu)化決策理論與方法 優(yōu)化決策理論與方法 1 線性規(guī)劃2 非線性規(guī)劃 約束和非約束 3 多目標(biāo)規(guī)劃4 組合優(yōu)化與整數(shù)規(guī)劃 決策理論與方法 優(yōu)化決策理論與方