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

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

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

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

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

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

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

8、滿足,說明有關梯度線性相關，矛盾,由于 ，令 ，可以將,Fritz John定理寫成：存在非負 滿足,這就是不等式約束的Kuhn-Tucker定理,推導Gordan定理的一般途徑,凸集分離定理,對任意非空凸集 ，如果 為空集，則存

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