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

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

（約束條件）

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

（非負(fù)條件）

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

線(xiàn)性無(wú)關(guān)

定義：

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

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

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

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

起作用的約束不起作用的約束（1）搜索方向線(xiàn)性約束問(wèn)題的Zoutendijk可行方向法起作用的約束不31非線(xiàn)性約束問(wèn)題的Zoutendijk可行方向法

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

迭代步長(zhǎng)搜索方向Topkis–Veinott全約束可行方向法迭代步34梯度投影法梯度投影法35可行方向法梯度投影法課件36可行方向法梯度投影法課件37可行