總復(fù)習(xí)_464601449

1、 考試時間：考試時間： 2013年年1月月10日上午日上午8：0010：00 考試地點：考試地點： 二教二教401 20102104432012210639 二教二教402 20122106402012310148 二教二教403 20123101602012311809 請大家務(wù)必按照要求到相應(yīng)的考場參加考試！請大家務(wù)必按照要求到相應(yīng)的考場參加考試！ 答疑時間：答疑時間： 2013年年1月月9日上午日上午8：3011：30 2013年年1月月9日下午日下午2：305：00 答疑地點：三教答疑地點：三教3202 1.攜帶研究生證，以備查對。攜帶研究生證，以備查對。 2提前十分鐘進入考場?？荚囬_

2、始十五分鐘后，不準再提前十分鐘進入考場?？荚囬_始十五分鐘后，不準再進入考場，逾時以曠考論。題卷發(fā)出十五分鐘后，方可交進入考場，逾時以曠考論。題卷發(fā)出十五分鐘后，方可交卷離場。卷離場。 3除答卷必需用的文具及教師指定的考試用具外，書包、除答卷必需用的文具及教師指定的考試用具外，書包、書籍、筆記、紙張等一律按監(jiān)考教師要求集中放置。書籍、筆記、紙張等一律按監(jiān)考教師要求集中放置。 4不允許攜帶具有信息傳遞或存儲功能的工具（如不允許攜帶具有信息傳遞或存儲功能的工具（如BP機、機、手機等）進入考場。手機等）進入考場。 5答卷一般用鋼筆或圓珠筆（藍色或黑色，不得用紅答卷一般用鋼筆或圓珠筆（藍色或黑色，不得用

3、紅色），不得用鉛筆（畫圖或外語考試選擇題等指定用鉛筆色），不得用鉛筆（畫圖或外語考試選擇題等指定用鉛筆除外）。除外）。 6答卷時不準互借文具（包括計算器、計算尺等）。答卷時不準互借文具（包括計算器、計算尺等）。 7嚴禁以任何理由左顧右盼、交頭接耳、抄襲或看別人嚴禁以任何理由左顧右盼、交頭接耳、抄襲或看別人答卷等各種形式的作弊行為。答卷等各種形式的作弊行為。 8答卷時，不得中途離場后再行返回。如有特殊原因需答卷時，不得中途離場后再行返回。如有特殊原因需離場者，必須經(jīng)監(jiān)考教師準許。答卷一經(jīng)考生帶出考場，離場者，必須經(jīng)監(jiān)考教師準許。答卷一經(jīng)考生帶出考場，即行作廢。即行作廢。 9在規(guī)定的時間內(nèi)答卷，不

4、得拖延。交卷時間到，考生在規(guī)定的時間內(nèi)答卷，不得拖延。交卷時間到，考生須在原座位安靜地等候監(jiān)考教師收卷后，方可離場。須在原座位安靜地等候監(jiān)考教師收卷后，方可離場。 一一.凸集與凸函數(shù)凸集與凸函數(shù) 1凸集的定義、性質(zhì)凸集的定義、性質(zhì);)4(;,|)3(;,|)2(;|) 1 (212)2(1)1()2()1(212)2(1)1()2()1(211121是凸集是凸集是凸集是凸集實數(shù)，則是兩個凸集，和設(shè)SSSxSxxxSSSxSxxxSSSxxSSS2. 極點和極方向的定義極點和極方向的定義的極點。是凸集，則稱推出，必假設(shè)不同點的凸組合，即若中兩個不能表示成，若是非空集合，設(shè)SxxxxxxxSxSx

5、S)2()1()2()1()1 (要求：會證明或判斷一個點是否是極點要求：會證明或判斷一個點是否是極點.(1)(2)(1)(2)(1)(2)|0SdSxxdSdSddSddddSddS設(shè) 是閉凸集， 為非零向量，如果對 中的每一個 ，有，則稱 是 的方向；又設(shè)和是 的兩個方向，若對任何正數(shù) ，有，則稱和是兩個不同的方向，若 的方向 不能表示成該集合的兩個不同方向的正的線性組合，則稱 為 的極方向。要求：會證明或判斷一個非零向量是否是方向或極方向要求：會證明或判斷一個非零向量是否是方向或極方向.。且的方向的充要條件是是非零向量，則是為非空集合，設(shè)000,|AddSddxbAxxS結(jié)論：結(jié)論：了解

6、表示定理了解表示定理2凸集分離定理凸集分離定理（1）會應(yīng)用凸集分離定理）會應(yīng)用凸集分離定理 （2）掌握）掌握Farkas定理和定理和Gordan定理和證明方法，定理和證明方法， 會應(yīng)用這兩個定理證明相應(yīng)的題目。會應(yīng)用這兩個定理證明相應(yīng)的題目。 3凸函數(shù)凸函數(shù)(凹函數(shù)凹函數(shù)) 要求：掌握凸要求：掌握凸(凹凹)函數(shù)的定義、性質(zhì)及判斷方法，會證函數(shù)的定義、性質(zhì)及判斷方法，會證明或判斷一個函數(shù)是否是凸明或判斷一個函數(shù)是否是凸(凹凹)函數(shù)函數(shù) 。 凸規(guī)劃：求凸函數(shù)在凸集上的極小點。凸規(guī)劃：求凸函數(shù)在凸集上的極小點。min( ). .( )0,1,( )0,1,ijf xstg ximh xjl( )(

7、)(1,)( )(1, )ijf xg x imh xjl若是凸函數(shù)，是凹函數(shù)，是線性函數(shù)，則原問題為凸規(guī)劃。性質(zhì)：凸規(guī)劃的局部極小點就是整體極小點，性質(zhì)：凸規(guī)劃的局部極小點就是整體極小點，且極小點的集合為凸集。且極小點的集合為凸集。 要求：會判斷一個模型是否為凸規(guī)劃要求：會判斷一個模型是否為凸規(guī)劃1、極小化型、極小化型2、約束方程為等式、約束方程為等式3、所有的決策變量為非負值、所有的決策變量為非負值4、約束方程的右端項系數(shù)為非負值、約束方程的右端項系數(shù)為非負值11min . 1, 01,njjjnijjijjzc xsta xbimxjn111min 0 0nm nmnzcxc s.t.

8、Axb Abxx 1基本概念基本概念: 可行域可行域(線性規(guī)劃的可行域是凸集線性規(guī)劃的可行域是凸集). 解的情形解的情形:無解無解(無可行解無可行解)、無界解、無界解(不存在不存在有限的最優(yōu)解有限的最優(yōu)解)、最優(yōu)解、最優(yōu)解(最優(yōu)解與最優(yōu)值的最優(yōu)解與最優(yōu)值的區(qū)別區(qū)別)、局部最優(yōu)解與全局最優(yōu)解、局部最優(yōu)解與全局最優(yōu)解. 可行解、基本解、基、基變量、非基變量、可行解、基本解、基、基變量、非基變量、基本可行解、非退化（退化）的基本可行解。基本可行解、非退化（退化）的基本可行解。 2基本性質(zhì)：基本性質(zhì)： 線性規(guī)劃存在有限最優(yōu)解的充要條件是所線性規(guī)劃存在有限最優(yōu)解的充要條件是所有有cd(j)為非負數(shù)，其中

9、為非負數(shù)，其中d(j)為可行域的極方向。為可行域的極方向。 若線性規(guī)劃問題存在有限最優(yōu)解，則目標若線性規(guī)劃問題存在有限最優(yōu)解，則目標函數(shù)的最優(yōu)值可在某個極點達到。函數(shù)的最優(yōu)值可在某個極點達到。 基本可行解與可行域極點之間的關(guān)系基本可行解與可行域極點之間的關(guān)系-等等價。價。 基本可行解的存在問題：有可行解，一定基本可行解的存在問題：有可行解，一定有基本可行解。有基本可行解。 min. .0fxcxs tAxbx11.0.BB b存在初始基 ，使得如何判斷該問題是否有最優(yōu)解？如何判斷該問題是否有最優(yōu)解？如何判斷一個基是否為最優(yōu)基？如何判斷一個基是否為最優(yōu)基？如何判斷該問題是否有無窮多最優(yōu)解？如何判

10、斷該問題是否有無窮多最優(yōu)解？用單純形表求解問題：用單純形表求解問題： xB xN 右端右端xBIm B-1N B-1b0 cBB-1N-cN cBB-1b 110BNc B Nc若極小化問題 ，則現(xiàn)行基本可行解為最優(yōu)解。110,0BNbB bxB bxx假設(shè)有一基本可行解主元消去法主元消去法 120.Bjjc B Pc若存在，用求改進的基本可行解2尋找初始基本可行解尋找初始基本可行解 min. .0fxcxs tAxbx兩階段法兩階段法大大M法法min. .111,0TaTaae xs tAxxbex x1min. .11100TaTamcxMe xs tAxxbeMx min max 變變

11、0 約約 量量 0 束束 無限制無限制 = 方方 程程 約約 0 束束 0 變變 方方 = 無限制無限制 量量 程程 會寫各種形式（對稱、非對稱、一般形會寫各種形式（對稱、非對稱、一般形式）的對偶問題；式）的對偶問題； 掌握弱對偶定理和強對偶定理及其相關(guān)掌握弱對偶定理和強對偶定理及其相關(guān)推論；推論； 會用互補松弛定理求原問題或?qū)ε紗栴}會用互補松弛定理求原問題或?qū)ε紗栴}的解；的解；小結(jié)小結(jié)原問題原問題(min) 對應(yīng)關(guān)系對應(yīng)關(guān)系 對偶問題對偶問題(max) 有最優(yōu)解有最優(yōu)解無界解不可行不可行無界解 掌握對偶單純形方法（對偶可行的基本掌握對偶單純形方法（對偶可行的基本解，如何求初始對偶可行的基本解

12、）。解，如何求初始對偶可行的基本解）。 與原單純形法的區(qū)別：與原單純形法的區(qū)別： 原單純形法保持原問題的可行性，對偶單原單純形法保持原問題的可行性，對偶單純形法保持所有檢驗數(shù)純形法保持所有檢驗數(shù)wPj-cj 0，即保持對，即保持對偶問題的可行性。偶問題的可行性。 特點：先選擇出基變量，再選擇進基變特點：先選擇出基變量，再選擇進基變 量。量。 5靈敏度分析靈敏度分析 改變非基變量和基變量價格系數(shù)后，原問改變非基變量和基變量價格系數(shù)后，原問題最優(yōu)解和最優(yōu)值的改變，會求最優(yōu)解不題最優(yōu)解和最優(yōu)值的改變，會求最優(yōu)解不變時價格系數(shù)的變化范圍；變時價格系數(shù)的變化范圍； 右端向量改變對最優(yōu)解及最優(yōu)值的影響，右

13、端向量改變對最優(yōu)解及最優(yōu)值的影響，會求最優(yōu)基不變時，右端向量的變化范圍；會求最優(yōu)基不變時，右端向量的變化范圍； 會判斷增加新的約束后，原問題最優(yōu)解是會判斷增加新的約束后，原問題最優(yōu)解是否發(fā)生變化否發(fā)生變化 理想值理想值 正、負偏差變量正、負偏差變量 會建目標規(guī)劃模型會建目標規(guī)劃模型 無約束問題的極值條件：無約束問題的極值條件：. 0)()()(1xfxxxf是局部極小點，則若處可微，在點設(shè)函數(shù)一階必要條件：定理是半正定的。矩陣，且極小點，則是局部處二階可微，若在設(shè)二階必要條件：定理)(0)()(22xfHessianxfxxxf是嚴格局部極小點。正定，則矩陣且處二次可微，若梯度在點：設(shè)函數(shù)定理

14、xxfHessianxfxxf)(, 0)()(32223( )( )0,( )( )f xxf xHessianf xxxxf xx定理 ：設(shè)函數(shù)在點 的鄰域內(nèi)二次可微，若梯度且矩陣在該鄰域內(nèi)半正定，則 是局部極小點。特別地，對于鄰域內(nèi)的任意點，若是正定矩陣，則 是一個嚴格的局部極小點.*)(21)(1bAxAcxbAxxxfTT，有唯一極小點對稱正定數(shù)推論：對于正定二次函. 0)(,)(4xfxExExfnn件是為整體極小點的充要條則上的可微凸函數(shù)，是定義在：設(shè)定理min( )00(0, ),()( )( )nnx Ef xxEdf xdf xdf xx對，設(shè)是任給一點，若存在，使得對任意

15、的有，則稱 為在點 處的下降方向(descent direction)。0)(0dxfdFT處的下降方向集。稱為點x定義定義:,0,(0,)nSExclS dxdSdSx設(shè)集合為非零向量，若存在數(shù)使得對任意，都有則稱 為集合 在 的可行方向(feasible direction)。SdxclSxddD有), 0(, 0, 0處的可行方向錐。xmin( )2(. .( )0,1,( )0,1, |( )0. ,()()(1, )( )( )|,1, ,(1, )(ijiiijijijf xKKTstg ximh xjlxIi g xf g iIxg iIxhjlxg xh xiI jlxw iI

16、vjlf定理必要條件）考慮問題設(shè) 為可行點在 處可微，在 連續(xù)，在 連續(xù)可微，向量集，線性無關(guān)，若 是局部最優(yōu)解，則存在數(shù)和，使得1)( )( )0.0().liijji Ijixwg xvh xwiI1min( )2(. .( )0,1,( )0,1, |( )0. ,(1, )( )( )|,1, ,(1, )( )( )ijiijijijmiiif xKKTstg ximh xjlxIi g xf gxhjlxg xh xiI jlxw iIvjlf xwg x定理必要條件）考慮問題設(shè) 為可行點在 處可微，在 連續(xù)可微，向量集，線性無關(guān)，若 是局部最優(yōu)解，則存在數(shù)和，使得1( )0( )

17、0,1,2,01,2,.ljjjiiivh xw g ximwim定義廣義的定義廣義的Lagrange函數(shù)函數(shù):.)(,),()()(,),()(),(),()()()()()()(),(11212111TlTmTlTmTTljjjmiiixhxhxhxgxgxgvvvvwwwwxhvxgwxfxhvxgwxfvwxL其中乘子向量乘子向量min( )2(. .( )0,1,( )0,1, |( )0. ,(1, )( )( )|,1, 0, ,( , )0ijiijijxf xKKTstg ximh xjlxIi g xf gxhjlxg xh xiI jlxwvL x w v定理必要條件）考

18、慮問題設(shè) 為可行點在 處可微，在 連續(xù)可微，向量集，線性無關(guān)，若 是局部最優(yōu)解，則存在乘子向量使得為整體極小點。條件成立，則處且在連續(xù)，在點連續(xù)，在點可微，在點和。，為可行域，是線性函數(shù)，是凹函數(shù)，是凸函數(shù)，中，設(shè)問題一階充分條件定理xKKTxxIigxljhxIigfxgiISxSljhmigfljxhmixgtsxfijiijiji)(), 2 , 1()(0)(|), 2 , 1(), 2 , 1(, 2 , 10)(, 2 , 10)(. .)(min)(3點。是是整體最優(yōu)解是凸規(guī)劃，則：設(shè)推論KKTxSxNP)(12()(1,)(1, )( ),( ),1, ,( , , )()(

19、, , )( )0,0( )0,0( )0,ijijxTiiTiiTjxNPfg imhjlxg x iIh xjlw vx w vLML x w vGg xdiIwGdg xdiIwh xdj定理（二階必要條件）：設(shè) 是的局部最優(yōu)解， ，和二次連續(xù)可微，且在 處，為線性無關(guān)組，則存在，使為的解且矩陣在子空間 上是半正定的，其中且且.1,2,l2(1,)(1, ),( , , )()( , , )( )0,00( )0,0 .( )0,1,2,ijxTiiTiiTjfg imhjlxw vx w vLML x w vGxg xdiIwGdg xdiIwh xdjl定理（二階充分條件）：設(shè) ，和

20、是二次連續(xù)可微函數(shù)， 為可行解，若存在，使為的解且矩陣在子空間 上是正定的，則 是嚴格局部極小點。且其中且Lagrange對偶問題對偶問題Dxljxhmixgtsxfji, 1, 0)(, 1, 0)(. .)(min(1)定義定義(1)的對偶問題的對偶問題:0. .),(maxwtsvw(2)Dxxhvxgwxfvwljjjmiii11)()()(inf),(其中對偶函數(shù)。稱為時，令若上式不存在有限下界Lagrangevwvw),(.),(推論推論1:.0| ),(sup, 0)(, 0)(| )(infwvwDxxhxgxf，必有對于原問題和對偶問題推論推論2:題的最優(yōu)解。分別是原問題和對

21、偶問和，則為原問題的可行解，其中若),(0),()(vwxwxvwxf推論推論3:。，有則對若),(0, 0)(, 0)(| )(infvwwDxxhxgxf推論推論4:sup( , )|0w vw 如果，則原問題沒有可行解。定理定理1(弱對偶定理弱對偶定理)。題的可行解，則分別是原問題和對偶問和設(shè)),()(),(vwxfvwx 閉映射的定義閉映射的定義 會判斷一個具體的算法映射在某個點是否會判斷一個具體的算法映射在某個點是否具有閉的性質(zhì)。具有閉的性質(zhì)。 二次終止性的定義：若某個算法對于任意二次終止性的定義：若某個算法對于任意的正定二次函數(shù)，從任意的初始點出發(fā)，的正定二次函數(shù)，從任意的初始點出

22、發(fā)，都能經(jīng)有限步迭代達到其極小點，則稱該都能經(jīng)有限步迭代達到其極小點，則稱該算法具有二次終止性。算法具有二次終止性。 一維搜索的定義一維搜索的定義 一維搜索的性質(zhì)：一維搜索的性質(zhì)：。則有由下列規(guī)則產(chǎn)生：具有一階偏導(dǎo)數(shù)，設(shè)目標函數(shù)0)()(min)()()1()()1()()()1(kTkkkkkkkkkkkdxfdxxdxfdxfxxf 最速下降方向的定義：最速下降方向的定義： 牛頓方向：牛頓方向：)()()(kkxfd( )2( )1( )()()kkkdf xf x 共軛方向共軛方向定義：定義：正交。共軛，或稱它們關(guān)于則稱這兩個方向關(guān)于滿足和向中的兩個方對稱正定矩陣，若是設(shè)AAAddddE

23、nnATn0)()2()1()2()1(性質(zhì)性質(zhì)個向量線性無關(guān)。共軛的非零向量，則這個是階對稱正定矩陣，是設(shè)kAkdddnAk)()2()1(,定理定理2：。則行一維搜索，發(fā)，依次沿這組向量進出意一點共軛的非零向量，從任是是對稱正定矩陣，其中，設(shè)有二次函數(shù)kjdxfnkdxxdxfdxfExAdddAcxbAxxxfjTkkkkkkkkkknnnnTT, 1 , 0, 0)(1, 1 , 0)()(min,21)()()1()()()1()()()()(0)0()1()1()0(定理（擴張子空間定理定理（擴張子空間定理,expanding subspace theorem）(1)(2)( )(

24、1)(1)(2)( )(2)(3)(1)(1)(1)(1)(2)( )(1)( )1(1)1( )2,( );,TTknkkkkkikiiif xx Axb xcAndddAxEdddxxxxf xMxdddx xxdRx設(shè)有函數(shù)其中 為 階對稱正定矩陣，是 共軛的非零向量。以任意的為初始點，依次沿進行一維搜索，得到點，則是在線性流形(1)( )knnBknxf xE上的唯一極小點。特別的，當時，是在上的唯一極小點。) 1 (. .)(mineExbAxtsxf. 0, 0,1)(121212211EddAxdbbbAAAbxAbxAxx的充要條件是處的可行方向是則非零向量其中有點處在的可行解

25、是問題設(shè)定理：定理：可行方向法：可行方向法：。優(yōu)值的目標函數(shù)最點的充要條件是問題是則，其中，處有是可行解，在點中，設(shè)在問題0)2() 1 (21212211KKTxbbbAAAbxAbxAxxnjdEddAtsdxfjT, 2 , 1, 1|00. .)(min)2(1?？杀硎緸榈恼煌队熬仃嚨接??？杀硎緸榈恼煌队熬仃嚨接蓜t的一組基，記是子空間設(shè)MMMMIPPUEMMMMQQUEMUTTnTTnnrTrTTr112121)()2()() 1 (,定理定理:推論推論1:.QQQQQQT，是正交投影矩陣，則若推論推論2:.是半正定的是正交投影矩陣，則若QQ為下降可行方向。，則，令若為滿秩矩陣，令又設(shè)，其中處，有的可行解，在點是問題設(shè)dxfPdxfPMMMMIPEAMbbbAAAbxAbxAxxTT)(0)(,) 1 (1121112211定理：定理