Zoutendijk可行方向法(0002)課件

第九章可行方向法第四部分約束最優(yōu)化問題的解法第十章罰函數(shù)法和廣義乘子法可行方向法：在可行域內(nèi)尋找使目標(biāo)函數(shù)下降的點列.廣義乘子法:在罰函數(shù)法的基礎(chǔ)上，借助Lagrange乘子來構(gòu)造罰函數(shù).罰函數(shù)法:利用原問題的目標(biāo)函數(shù)和約束條件構(gòu)造新的目標(biāo)函數(shù)--罰函數(shù),把約束最優(yōu)化問題轉(zhuǎn)化為相應(yīng)的罰函數(shù)的無約束最優(yōu)化問題來求解.改進第四部分約束最優(yōu)化問題的解法

第九章可行方向法

(FeasibleDirectionMethods)可行方向法是其中的一類求解(線性)約束最優(yōu)化問題的方法．此類方法可看做無約束下降算法的自然推廣．可行方向法的基本思想是從可行點出發(fā)，沿可行下降方向進行搜索，求出使目標(biāo)函數(shù)值下降的新的可行點．算法包括選擇搜索方向和確定搜索步長兩個主要方面．

搜索方向的選擇方式不同就形成不同的可行方向法．

Zoutendijk可行方向法梯度投影法(GradientProjectionMethod)

既約梯度法

(ReducedGradientMethod)Frank-Wolfe方法

第九章可行方向法簡介Zoutendijk可行方向法

Zoutendijk可行方向法是Zoutendijk于1960年提出的.

Zoutendijk可行方向法中選擇搜索方向包括:

起作用約束構(gòu)造可行方向和ε起作用約束構(gòu)造可行方向.

Zoutendijk可行方向法可以求解線性約束優(yōu)化問題和

非線性約束優(yōu)化問題.線性約束情形Zoutendijk可行方向法考慮線性約束問題線性約束情形Zoutendijk可行方向法基本原理

(1)

利用起作用約束構(gòu)造可行下降方向

(2)

確定一維搜索步長線性約束情形Zoutendijk可行方向法基本原理

(2)

確定一維搜索步長

帶約束的一維優(yōu)化問題

利用可行方向條件與起作用約束簡化(9.1.11)線性約束情形Zoutendijk可行方向法基本原理

(2)

確定一維搜索步長

(a)簡化(a)(9.1.5)線性約束情形Zoutendijk可行方向法基本原理

(2)

確定一維搜索步長分兩種情況討論(9.1.5):(9.1.14)的約束條件問題(9.1.11)一維搜索問題線性約束情形算法步驟Step1Step2Step3Step4Step5Zoutendijk可行方向法線性約束情形舉例Zoutendijk可行方向法

參見P243例9.1.1非線性約束情形Zoutendijk可行方向法非線性約束情形基本原理

(1)

利用起作用約束構(gòu)造可行下降方向定理1.2.3定理3.3.2點x處的可行下降方向d滿足：線性規(guī)劃問題

結(jié)論(9.1.22)Zoutendijk可行方向法非線性約束情形基本原理

(1)

利用起作用約束構(gòu)造可行下降方向

(2)

確定一維搜索步長非線性約束情形算法步驟Step1Step2

束Step3Step4Step5Zoutendijk可行方向法非線性約束情形算法特點

計算實踐和理論分析表明，該算法可能失效或出現(xiàn)鋸齒現(xiàn)象，使算法收斂很慢甚至不收斂到最優(yōu)點或K—T點．Zoutendijk法的改進

對于線性和非線性不等式約束問題，前面我們僅使用起作用約束來確定搜索方向．當(dāng)某迭代點在一個約束的邊界上時，如果可行方向取得不恰當(dāng)，那么沿該方向可能因接近另一個約束邊界而只能作一個微小的移動，否則，就會使迭代點跑出邊界．為防止這一現(xiàn)象發(fā)生，設(shè)想在約束條件的邊界上設(shè)立一道“安全帶”，迭代點進入“安全帶”時，只允許它往可行域內(nèi)部移動，而不許向邊界靠近．為此引入ε起作用約束的概念，即在構(gòu)造可行方向時，既把通過當(dāng)前迭代點的約束邊界看作起作用約束，也把充分家近當(dāng)前這代點的邊界約束考慮在內(nèi)．問題的提出Zoutendijk可行方向法定義Zoutendijk法的改進–ε

起作用約束可行方向法εk

起作用約束指標(biāo)集.ε起作用約束可行方向算法步驟Zoutendijk法的改進Step1Step2Step3Step4Step6Step5Zoutendijk可行方向法簡介Zoutendijk法的改進–Topkis-Veinott可行方向法

為防止鋸齒現(xiàn)象，還可考慮起作用約束和不起作用約束在確定搜索方向中都起作用．這種全作用約束方向法是Topkis和Veinott(1967)提出并保證收斂于Fritz-John點．基本原理Zoutendijk可行