用投影梯度法解不等式約束的線性規(guī)劃市公開課金獎市賽課一等獎?wù)n件

用投影梯度法解不等式約束線性規(guī)劃第1頁第1頁考慮不等式約束線性規(guī)劃其中，，假設(shè)已有可行解，滿足是列滿秩矩陣由于是方陣，因此存在，記由于，因此第2頁第2頁采用投影梯度法，先計算由于，因此，因此由于，只用考慮第二、三種情況首先考慮第三種情況此時已經(jīng)滿足K-T條件，下面分析這樣得到是什么解？第3頁第3頁原問題對偶問題現(xiàn)在已知，假如令可知是對偶問題基可行解，目的值為第4頁第4頁原問題可行解，目的函數(shù)小結(jié)：當(dāng)?shù)谌N情況出現(xiàn)時，能夠得到對偶問題基可行解，目的函數(shù)由弱對偶定理可知它們分別是原問題和對偶問題最優(yōu)解，并且是原問題最優(yōu)基可行解第5頁第5頁再考慮第二種情況取，則直線搜索問題第6頁第6頁由于直線搜索問題等價于第7頁第7頁對直線搜索問題最優(yōu)解等于改進(jìn)可行解為由于本來個起作用約束只有一個變成不起作用約束，假如上面最小值只在一個下標(biāo)達(dá)到（非退化），那么本來不起作用約束只有一個變成起作用約束，新可行解起作用約束還是個，可重復(fù)前面過程第8頁第8頁結(jié)論用投影梯度法從滿足前面商定初始可行解開始求解線性不等式約束線性規(guī)劃問題本質(zhì)上就是用對偶單純型法求解其下述原則線性規(guī)劃問題第9頁第9頁用簡約梯度法解原則線性規(guī)劃問題第10頁第10頁已知可行解滿足下列條件：2)每個分量都不小于零（非退化情況）1),存在考慮原則線性規(guī)劃問題（）于是是下述問題可行解（）并且，（相應(yīng)約束是不起作用約束）第11頁第11頁（檢查數(shù)）由于，因此簡約梯度為可行下降方向：不等于零條件：

或（將增長）（將減少）第12頁第12頁當(dāng)是基可行解時不等于零條件：

或不滿足檢查數(shù)條件起作用約束變成不起作用約束和單純型法區(qū)別：一次迭代允許多個起作用約束變成不起作用約束第13頁第13頁推導(dǎo)不等式約束Kuhn-Tucker定理普通路徑Gordan定理任意給定一組向量，不存在充要條件是，存在一組不全為零非負(fù)實(shí)數(shù)滿足滿足GordanFritzJohnKuhn-Tucker第14頁第14頁Gordan定理對于普通性非線性不等式約束，是局部最優(yōu)解依據(jù)Gordan定理，上述必要條件等價于存在不全這里不需要梯度線性無關(guān)條件必要條件是不存在滿足不等式FritzJohn定理為零非負(fù)實(shí)數(shù)滿足第15頁第15頁FritzJohn定理不等式Kuhn-Tucker定理由于進(jìn)一步假定線性無關(guān)能夠推定，不然有不全為0滿足闡明相關(guān)梯度線性相關(guān)，矛盾由于，令，能夠?qū)ritzJohn定理寫成：存在非負(fù)滿足這就是不等式約束Kuhn-Tucker定理第16頁第16頁推導(dǎo)Gordan定理普通路徑凸集分離定理對任意非空凸集，假如為空集，則存在超平面滿足幾何意義：Gordan凸集分離定理第17頁第17頁用凸集分離定理導(dǎo)出Gordan定理定義下列：無解為空集（凸集分離定理）第18頁第18頁第19頁第19頁推導(dǎo)凸集分離