沒(méi)有幻燈片標(biāo)題-read

1、用投影梯度法解不等式約束的線(xiàn)性規(guī)劃,考慮不等式約束的線(xiàn)性規(guī)劃,其中 ， ， 假設(shè)已有可行解 ，滿(mǎn)足,是列滿(mǎn)秩矩陣,由于 是方陣，所以存在 ，記,因?yàn)?，所以,采用投影梯度法，先計(jì)算,由于 ，所以 ，因此,因?yàn)?，只用考慮第二、

2、三種情況,首先考慮第三種情況,此時(shí) 已經(jīng)滿(mǎn)足K-T條件，下面分析這樣得到的是什么解？,原問(wèn)題,對(duì)偶問(wèn)題,現(xiàn)在已知 ，如果令,可知 是對(duì)偶問(wèn)題基可行解，目標(biāo)值為,原問(wèn)題的可行解 ，目標(biāo)函數(shù),小結(jié)：當(dāng)?shù)谌N情況出現(xiàn)時(shí)，可以得到,對(duì)偶問(wèn)題的基可行解 ，,目標(biāo)函數(shù),由弱對(duì)偶定理可知它們分別是原問(wèn)題和對(duì)偶問(wèn)題

3、的最優(yōu)解，并且 是原問(wèn)題的最優(yōu)的基可行解,再考慮第二種情況,取 ，,則,直線(xiàn)搜索問(wèn)題,因?yàn)?直線(xiàn)搜索問(wèn)題等價(jià)于,對(duì)直線(xiàn)搜索問(wèn)題,最優(yōu)解等于,改進(jìn)的可行解為,由于 原來(lái)的 個(gè)起作用約束只有一個(gè)變成不起作用約束，如果上面的最小值只在一個(gè)下標(biāo)達(dá)到（非退化），那么原來(lái)的不起作用約束只有一個(gè)變成起作用約束，新可

4、行解的起作用約束還是 個(gè)，可重復(fù)前面的過(guò)程,結(jié)論,用投影梯度法從滿(mǎn)足前面約定的初始可行解開(kāi)始求解線(xiàn)性不等式約束的線(xiàn)性規(guī)劃問(wèn)題,本質(zhì)上就是用對(duì)偶單純型法求解其下述標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題,用簡(jiǎn)約梯度法解標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題,已知可行解 滿(mǎn)足以下條件：,2) 的每個(gè)分量都大于零（非退化情況）,1) , 存在,考慮標(biāo)準(zhǔn)線(xiàn)性規(guī)劃問(wèn)題（ ）,于是 是下述問(wèn)

5、題可行解（ ）,并且， （對(duì)應(yīng)的約束是不起作用約束）,（檢驗(yàn)數(shù)）,因?yàn)?，所以簡(jiǎn)約梯度為,可行下降方向：,不等于零的條件： 或,（ 將增加）,（ 將減少）,當(dāng) 是基可行解時(shí),不等于零的條件： 或,不滿(mǎn)足檢驗(yàn)數(shù)條件的起作用約束變成不起

6、作用約束,和單純型法的區(qū)別：,一次迭代容許多個(gè)起作用約束變成不起作用約束,推導(dǎo)不等式約束Kuhn-Tucker定理的一般途徑,Gordan定理,任意給定一組向量 ，不存在,的充要條件是，存在一組不全為零的非負(fù)實(shí)數(shù),滿(mǎn)足,滿(mǎn)足,Gordan,Fritz John,Kuhn-Tucker,Gordan定理,對(duì)于一般性非線(xiàn)性不等式約束， 是局部最優(yōu)解,根據(jù)Gordan定理

7、，上述必要條件等價(jià)于存在不全,這里不需要梯度線(xiàn)性無(wú)關(guān)的條件,的必要條件是不存在 滿(mǎn)足,不等式Fritz John定理,為零的非負(fù)實(shí)數(shù) 滿(mǎn)足,Fritz John定理,不等式Kuhn-Tucker定理,由于進(jìn)一步假定 線(xiàn)性無(wú)關(guān),可以推定 ，否則有不全為0的

8、滿(mǎn)足,說(shuō)明有關(guān)梯度線(xiàn)性相關(guān)，矛盾,由于 ，令 ，可以將,Fritz John定理寫(xiě)成：存在非負(fù) 滿(mǎn)足,這就是不等式約束的Kuhn-Tucker定理,推導(dǎo)Gordan定理的一般途徑,凸集分離定理,對(duì)任意非空凸集 ，如果 為空集，則存

9、在超平面 滿(mǎn)足,幾何意義：,Gordan,凸集分離定理,,,用凸集分離定理導(dǎo)出Gordan定理,定義 如下：,無(wú)解,為空集,（凸集分離定理）,推導(dǎo)凸集分離定理的一般途徑,投影定理,對(duì)任意非空閉凸集 ，如果 ，則存在唯一的 滿(mǎn)足,幾何意