可行方向法梯度投影法課件

有約束優(yōu)化問題非線性優(yōu)化問題線性優(yōu)化問題非線性約束優(yōu)化問題線性約束優(yōu)化問題（目標(biāo)函數(shù)—非線性）（目標(biāo)函數(shù)—線性）（約束—線性）（目標(biāo)函數(shù)—非線性）（約束—非線性）（目標(biāo)函數(shù)—非線性）（約束—線性）有約束優(yōu)化問題非線性優(yōu)化問題線性優(yōu)化問題非線性約束優(yōu)化問題線1K-K-T條件（1）K-K-T條件K-K-T條件（梯度條件）

（約束條件）

（松弛互補(bǔ)條件）

（非負(fù)條件）

（正則條件或約束規(guī)格）

線性無關(guān)

定義：

K-K-T條件（1）K-K-T條件K-K-T條件（梯度條件）2可行方向法梯度投影法課件3最優(yōu)點(diǎn)，一定在與之間，所以可以起作用的非負(fù)線性組合表示。起作用的約束經(jīng)過最優(yōu)點(diǎn)，最優(yōu)點(diǎn)滿足所有的約束條件，這就是K-K-T條件，最優(yōu)點(diǎn)，一定在4約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步長(zhǎng)；受約束條件的限制。（一）基本概念：（1）起作用的約束：起到限制性作用的約束。（2）可行方向：點(diǎn)在可行域內(nèi)的點(diǎn)，方向迭代后的新的點(diǎn)也是可行域內(nèi)的點(diǎn)，則搜索方向稱為可行方向。（3）可行下降方向：使目標(biāo)函數(shù)下降的可行方向，稱為可行下降方向。起作用的約束約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步5將每一個(gè)函數(shù)在處對(duì)函數(shù)進(jìn)行taylor展開，取一次近四，則；（1）如果或，則搜索方向是下降方向。（2）如果在可行域內(nèi)，，則總可取步長(zhǎng)，得，使仍在可行域內(nèi)，即任意搜索方向是可行方向。（3）如果在邊界上，，則對(duì)某個(gè)步長(zhǎng)來說，如果，則在可行域內(nèi)，故可行的。（4）如果(3)的情況下，，或則位于在點(diǎn)的切平面上，只有為現(xiàn)行時(shí)，才是可行點(diǎn)。線性條件下非線性條件下線性條件下將每一個(gè)函數(shù)在處對(duì)函數(shù)進(jìn)行tayl6線性約束條件下搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約束條件：約束條件搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約束條件：線性約束條件下搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約7二次規(guī)劃可行方向法二次規(guī)劃可行方向法8線性約束問題的Zoutendijk可行方向法

解析搜索法：可行方向法起作用的約束不起作用的約束線性約束問題的Zoutendijk可行方向法解析搜索法：可9解析搜索法：可行方向法解析搜索法：可行方向法10解析搜索法：可行方向法解析搜索法：可行方向法11解析搜索法：可行方向法解析搜索法：可行方向法12解析搜索法：可行方向法解析搜索法：可行方向法13解析搜索法：可行方向法解析搜索法：可行方向法14解析搜索法：可行方向法解析搜索法：可行方向法15解析搜索法：可行方向法解析搜索法：可行方向法16非線性約束問題的Zoutendijk可行方向法

解析搜索法：可行方向法-非線性約束問題的Zoutendijk可行方向法解析搜索法：17解析搜索法：可行方向法解析搜索法：可行方向法18解析搜索法：可行方向法解析搜索法：可行方向法19解析搜索法：可行方向法解析搜索法：可行方向法20起作用約束可行方向法解析搜索法：可行方向法起作用約束可行方向法解析搜索法：可行方向法21解析搜索法：可行方向法解析搜索法：可行方向法22解析搜索法：可行方向法解析搜索法：可行方向法23Topkis–Veinott全約束可行方向法

解析搜索法：可行方向法Topkis–Veinott全約束可行方向法解析搜24解析搜索法：可行方向法解析搜索法：可行方向法254.非線性結(jié)構(gòu)優(yōu)化4.5梯度投影法4.非線性結(jié)構(gòu)優(yōu)化4.5梯度投影法26投影矩陣的基本概念解析搜索法：梯度投影法投影矩陣的基本概念解析搜索法：梯度投影法27解析搜索法：梯度投影法解析搜索法：梯度投影法28解析搜索法：梯度投影法解析搜索法：梯度投影法29約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步長(zhǎng)；受約束條件的限制。搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約束條件：線性約束條件下搜索方向約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步30線性約束問題的Zoutendijk可行方向法

起作用的約束不起作用的約束（1）搜索方向線性約束問題的Zoutendijk可行方向法起作用的約束不31非線性約束問題的Zoutendijk可行方向法

搜索方向迭代步長(zhǎng)非線性約束問題的Zoutendijk可行方向法搜索方向迭代32起作用約束可行方向法迭代步長(zhǎng)搜索方向起作用約束可行方向法迭代步長(zhǎng)搜索方向33Topkis–Veinott全約束可行方向法

迭代步長(zhǎng)搜索方向Topkis–Veinott全約束可行方向法迭代步34梯度投影法梯度投影法35可行方向法梯度投影法課件36可行方向法梯度投影法課件37可行方向法梯度投影法課件38可行方向法梯度投影法課件39可行方向法梯度投影法課件40可行方向法梯度投影法課件41解析搜索法：梯度投影法解析搜索法：梯度投影法42解析搜索法：梯度投影法解析搜索法：梯度投影法43解析搜索法：梯度投影法解析搜索法：梯度投影法44有約束優(yōu)化問題非線性優(yōu)化問題線性優(yōu)化問題非線性約束優(yōu)化問題線性約束優(yōu)化問題（目標(biāo)函數(shù)—非線性）（目標(biāo)函數(shù)—線性）（約束—線性）（目標(biāo)函數(shù)—非線性）（約束—非線性）（目標(biāo)函數(shù)—非線性）（約束—線性）有約束優(yōu)化問題非線性優(yōu)化問題線性優(yōu)化問題非線性約束優(yōu)化問題線45K-K-T條件（1）K-K-T條件K-K-T條件（梯度條件）

（約束條件）

（松弛互補(bǔ)條件）

（非負(fù)條件）

（正則條件或約束規(guī)格）

線性無關(guān)

定義：

K-K-T條件（1）K-K-T條件K-K-T條件（梯度條件）46可行方向法梯度投影法課件47最優(yōu)點(diǎn)，一定在與之間，所以可以起作用的非負(fù)線性組合表示。起作用的約束經(jīng)過最優(yōu)點(diǎn)，最優(yōu)點(diǎn)滿足所有的約束條件，這就是K-K-T條件，最優(yōu)點(diǎn)，一定在48約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步長(zhǎng)；受約束條件的限制。（一）基本概念：（1）起作用的約束：起到限制性作用的約束。（2）可行方向：點(diǎn)在可行域內(nèi)的點(diǎn)，方向迭代后的新的點(diǎn)也是可行域內(nèi)的點(diǎn)，則搜索方向稱為可行方向。（3）可行下降方向：使目標(biāo)函數(shù)下降的可行方向，稱為可行下降方向。起作用的約束約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步49將每一個(gè)函數(shù)在處對(duì)函數(shù)進(jìn)行taylor展開，取一次近四，則；（1）如果或，則搜索方向是下降方向。（2）如果在可行域內(nèi)，，則總可取步長(zhǎng)，得，使仍在可行域內(nèi)，即任意搜索方向是可行方向。（3）如果在邊界上，，則對(duì)某個(gè)步長(zhǎng)來說，如果，則在可行域內(nèi)，故可行的。（4）如果(3)的情況下，，或則位于在點(diǎn)的切平面上，只有為現(xiàn)行時(shí)，才是可行點(diǎn)。線性條件下非線性條件下線性條件下將每一個(gè)函數(shù)在處對(duì)函數(shù)進(jìn)行tayl50線性約束條件下搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約束條件：約束條件搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約束條件：線性約束條件下搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約51二次規(guī)劃可行方向法二次規(guī)劃可行方向法52線性約束問題的Zoutendijk可行方向法

解析搜索法：可行方向法起作用的約束不起作用的約束線性約束問題的Zoutendijk可行方向法解析搜索法：可53解析搜索法：可行方向法解析搜索法：可行方向法54解析搜索法：可行方向法解析搜索法：可行方向法55解析搜索法：可行方向法解析搜索法：可行方向法56解析搜索法：可行方向法解析搜索法：可行方向法57解析搜索法：可行方向法解析搜索法：可行方向法58解析搜索法：可行方向法解析搜索法：可行方向法59解析搜索法：可行方向法解析搜索法：可行方向法60非線性約束問題的Zoutendijk可行方向法

解析搜索法：可行方向法-非線性約束問題的Zoutendijk可行方向法解析搜索法：61解析搜索法：可行方向法解析搜索法：可行方向法62解析搜索法：可行方向法解析搜索法：可行方向法63解析搜索法：可行方向法解析搜索法：可行方向法64起作用約束可行方向法解析搜索法：可行方向法起作用約束可行方向法解析搜索法：可行方向法65解析搜索法：可行方向法解析搜索法：可行方向法66解析搜索法：可行方向法解析搜索法：可行方向法67Topkis–Veinott全約束可行方向法

解析搜索法：可行方向法Topkis–Veinott全約束可行方向法解析搜68解析搜索法：可行方向法解析搜索法：可行方向法694.非線性結(jié)構(gòu)優(yōu)化4.5梯度投影法4.非線性結(jié)構(gòu)優(yōu)化4.5梯度投影法70投影矩陣的基本概念解析搜索法：梯度投影法投影矩陣的基本概念解析搜索法：梯度投影法71解析搜索法：梯度投影法解析搜索法：梯度投影法72解析搜索法：梯度投影法解析搜索法：梯度投影法73約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步長(zhǎng)；受約束條件的限制。搜索方向需要滿足的條件：目標(biāo)函數(shù)下降的條件：約束條件：線性約束條件下搜索方向約束優(yōu)化問題：（1）搜索方向；受約束條件的限制。（2）迭代步74線性約束問題的Zoutendijk可行方向法

起作用的約束不起作用的約束（1）搜索方向線性約束問題的Zoutendijk可行方向法起作用的約束不75非線性約束問題的Zoutendijk可行方向法

搜索方向迭代步長(zhǎng)非線性約束問題的Zoutendijk可行方向法搜索方向迭代76起作用約束可行方向法迭代步長(zhǎng)搜索方向起作