1、最優(yōu)化之基本概念1.2.（最優(yōu)化問題的三種表達(dá)形式,P5中）3.4.最優(yōu)化問題的表示形式下降算法：求而陶有山浦/聞最優(yōu)化問題的數(shù)學(xué)模型包含有三個要素：即變量（又稱設(shè)計變量）件。（變量、目標(biāo)函數(shù)、約束條件,P4）、目標(biāo)函數(shù)、約束條5.6.稱為集約束，通常不作考慮，可認(rèn)為目標(biāo)函數(shù)的定義域。一般有可行點（容許點）：滿足所有約束的點稱為可行點或容許點。可行域（容許集）：全體可行點構(gòu)成的集合稱為可行域，也叫容許集，記為Do（P5）最優(yōu)值：目標(biāo)函數(shù)值1第三種嘀八小-GU)=航=%(#),也/(P5底)處理最優(yōu)化問題的3種方法：解析法、圖解法、迭代法迭代算法：選取一個初始可行點，然后根據(jù)現(xiàn)有的信息確定本次迭

2、代的一個搜索方向和適當(dāng)?shù)牟介L，從而得到一個新點。搜索方向迭代步長新的迭代點/現(xiàn)有的迭代點第一種第二種最優(yōu)點A:在可行域內(nèi)找到的點，使得目標(biāo)函數(shù)值取得最優(yōu)值最優(yōu)解：;/）,但習(xí)慣上把y,本身稱為最優(yōu)解。k=0,1.2,搜索方向等式約束minF(X)El標(biāo)函數(shù)之內(nèi)r(X)-O,不等式約束上升算法：求1m佃有仙+J他）（P9）7 .收斂速度：衡量算好好壞的一個標(biāo)準(zhǔn)。（P9底）具有超線性收斂或者二階收斂的算法是較快速的算法。（P10）8 .計算終止的計算終止準(zhǔn)則：無約束優(yōu)化問題的三種計算終止準(zhǔn)則：點距準(zhǔn)則、函數(shù)下降量準(zhǔn)則、梯度準(zhǔn)則。（P11）約束優(yōu)化問題有各自的終止準(zhǔn)則。優(yōu)化算法的基本迭代過程：（P1

3、1底）9 .圖解法：（P6）運用求解二位優(yōu)化問題可行域：即約束集合（P6）等高線：在三維空間中，不同的c值得到不同的投影曲線。沒一條投影曲線對應(yīng)一個c值，稱投影曲線為目標(biāo)函數(shù)的等值線或者等高線。（P7）10 .組合優(yōu)化問題舉例：背包問題即0-1問題:P13例1.9需要設(shè)射為二進(jìn)制變量,表示裝第i個物組合爆炸P15組合爆炸P15算法的空間復(fù)雜性：算法執(zhí)行期間占用的存儲單位(P15)品。旅行商問題（TSP）:（P14）聚類問題：（P14）11 .算法復(fù)雜性：算法對時間的復(fù)雜性T（n）和對空間的復(fù)雜性S（n）o算法的時間復(fù)雜性：算法執(zhí)行基本操作的次數(shù)12 .組合優(yōu)化問題分類：根據(jù)算法的復(fù)雜性，可分為

4、P類、NP類、NP完全類。P類問題：具有多項式實踐求解算法NP類問題：未找到球最優(yōu)解的多項式實踐算法NP完全類問題：任何一個問題至今未發(fā)現(xiàn)有多項式算法；只要其中一個問題找到了多項式算法，那么其他所有問題均有多項式算法。（P15）第二章1 .例題2.1如何判定矩陣是否正定（P19）充要條件：矩陣的行列式的順序主子式全部大于零線彳弋P1642 .方向?qū)?shù)（P19）（1）方向?qū)?shù)的定義：（P19底）定義2改了：KfH花點鳴可微.產(chǎn)是固定不變的廣向量一是方向P上的單位向圾,則稱極限"5。）-he工+曲一/區(qū)）二=iini初產(chǎn)ff。*g為函數(shù)Z（A）位點$處沿P方向的方向?qū)?shù).記為(2)下降方

5、向：(P20)f(Xo+tP)<f(i)定義2.2下降方向)設(shè)&*f*是連續(xù)函數(shù)，尸wJT1-L產(chǎn)H0.若在在<5>0當(dāng)w(o,力時有八8十田)v八項)貝”稱p為F在鳴處的卜降方向力(3)上升方向：1.13f(x0)日若<0,則稱P為f在X0處的下降方向。dP3 .梯度(1)定義及常用梯度公式：(P20)(2)梯度與方向?qū)?shù)之間的關(guān)系：(P21)定理2若/:次內(nèi)f尺】在點招可微，則2=3,心則p方向是函數(shù)處的下降方向。若叩他沖>0,則p方向是函數(shù)處的上升方向。?<1方向?qū)?shù)的正負(fù)決定了函數(shù)值的上升或者下降，那么上升或者下降的幅度則由絕對值的大小決定。

6、(3)關(guān)系(P21)七)“=YT(A0>re=三|YT(A7o>|當(dāng)。的方向與W7)的相同時，等號成立梯度方向是函數(shù)值的最速上升方向；函數(shù)在與其梯度正交的方向上變化率為零；函數(shù)在與其梯度成銳角是上升的，而在與其梯度成鈍角的方向上是下降的；梯度反方向是函數(shù)值的最速下降方向。例題2.2對目標(biāo)函數(shù)求某一點的最速下降方向。4 .Hesse矩陣(1) Hesse矩陣的定義：(P22)定義2.4階偏導(dǎo)數(shù)ci8xi(/,y-1,2,-,«)都存在，則稱函數(shù)/在點處二階可導(dǎo)，并且稱矩陣cbcf新八工）鏟人工）山(項)Qx10k23/占)才八M）chr1cUt（i血外甘/工）ar；是Z在點

7、，件處的He號SS矩陣=處的所有二階偏導(dǎo)數(shù)連續(xù)時有Hesse矩陣對稱。例題2.3、2.4、2.5計算求解了已知函數(shù)的梯度和Hesse矩陣。線性函數(shù)的一階導(dǎo)數(shù)為常向量，二階導(dǎo)數(shù)為零矩陣；二次函數(shù)的一階導(dǎo)數(shù)為線性向量函數(shù)，二階導(dǎo)數(shù)為常矩陣。（P24）（2）Jacobi矩陣定義2.5設(shè)日：尺"叱，記A）-（A）,GV）,如果&PO在點范處各分量的偏導(dǎo)數(shù)%都存在.則稱向量函數(shù)&（X）在點X。處是一階可導(dǎo)的，并且稱矩陣M.K)斗血叫回、削詡，（X）肛是Hg在點X。處的一階導(dǎo)數(shù)或Jaabi矩陣.乜簡記為打（X。）=梯度的Jacobi矩陣即為函數(shù)的Hesse矩陣。（P2425）性質(zhì)

8、見書本P25。（3）泰勒展開式：（P25）證明同見P25是,N.N設(shè),>J?1旦有=既廷續(xù)f扁導(dǎo)致,貝U八v尸）一八X3+<*尸尸+母尸丁工八寶3不中JV-=+Ov1.5.二次型與正定矩陣（1）二次型：（P18第一部分）設(shè),：kT卻，如果/在點A處對于自變量上的各分量的二二次型的方程為，"工+flJ2X2+LL+a2tlx1xK+*+口E1*K為+"心籃K"=+口=”：B.嚇£"產(chǎn)產(chǎn)j.I/-j-Jt用矩陣表示為“修，三，勺）=X2巧=Xt.4X£】/«!矩陣A的元素%=%是二次型系數(shù)巧巧的一半，二次型和矩陣A相

9、互唯一訣定;A=At（2）正定矩陣（P19文字部分）定義2£若對任意一組不全為零的數(shù)天，巧，,都有/（天,三,=-¥tAY>0則稱巧，天正定，且二次型矩陣A也稱為正定口/（多,七,7l=Xt4XN0A為半正定矩陣.不巧，通）=X"X40A為半負(fù)定矩陣.既不是半正定也不是半負(fù)定，就稱為矩陣A為不定的.矩陣A為正定的充要條件是它的行列式M的順序主子式全部大于零。（P19）判定6.極小點的判定條件（1）局部極小點和嚴(yán)格局部極小點定義（P26）定義2.7若XwQ,存在X*的某一領(lǐng)域JV0T芯）使得對VAf都有八"”）生產(chǎn)（X）,則稱王.為八星）的局部極小點

10、二定義N.8若*，wR存在AT的某一領(lǐng)域可（工，爐使得對VA7EZJnJVGYM冉旦工X#'都有,則稱*'為/（*）的嚴(yán)格局部極小點,苴中2£*二<5,=1*|JTvaO全局極小點和嚴(yán)格全局極小點定義（P26）定義2超若X*憶VeZ7都有/（X*）/0T則稱為的全局極小點二定義7。若理三萬，"三心，但X*X*都有/（*）式八*），則稱*'為/（X的嚴(yán)格全南極小點&顯然，整體的最優(yōu)解一定是局部的最優(yōu)解，而局部的最優(yōu)解不一定是整體的最優(yōu)解。（2）無約束問題的最有性條件,幾個概念最優(yōu)性條件：優(yōu)化問題最優(yōu)解所滿足的必要條件和充分條件；必要條件：

11、最優(yōu)點滿足那些條件；充分條件：滿足那些條件的點是最優(yōu)點。（3）無約束問題的最優(yōu)性條件,幾大定理（P27）定理2.32.5重點定理2.3設(shè)/：叱-我具仃連續(xù)一階偏導(dǎo)數(shù)，若*是的局部極小點并且是D的內(nèi)點.則Yf（X*）=O一階必要性條件（若x為極值點，則/%)二0導(dǎo)數(shù)為0。）定理2.4設(shè)/：肥f必在點X*二階可微,若X*是局部極小點，則梯度YT（X"）=O,并且Hesme矩陣力八.亡）半正定的駐點.定義2.11設(shè)k是。的內(nèi)點.若Vf（k）=o，則稱k是八X）二階充分性條件定理2.5設(shè)/：肥具有二階連續(xù)偏導(dǎo)數(shù)，k是方的內(nèi)點,若uf（k）=o并且。是正定的.則x是/（£）的嚴(yán)格局部

12、極小點,（若x為極小值點，則體）二。,一階導(dǎo)數(shù)為0,二階導(dǎo)數(shù)大于0。）6.約束問題的最優(yōu)性條件（1） 約束最優(yōu)點除了可能落在可行域內(nèi)的情況外，更是常常在約束邊界上或約束曲面上。（2） 約束優(yōu)化問題的類型：（P37）不等式約束優(yōu)化問題（IP型）、等式約束優(yōu)化問題（EP型）、一般約束優(yōu)化問題（GP型）（3） 約束優(yōu)化問題局部解的一階必要條件：（P38）在研究某一點出的可行方向時，只需要考慮在這一點的起作用的約束（P38中）。（4） IP型約束問題的一階必要條件：（P39一般性條件在P40）拓展一般IP型約束問題的一階必要條件討論如下*若城優(yōu)點X*位丁個約束邊界的交升：處，則這1個約束條件組成一個起

13、作用的約京集，則成立Ml，石oP38-39)看書上具有三個不等式約束的二維最優(yōu)化問題可供理解（但是在實際求解過程中，并不能預(yù)先知遒最優(yōu)點A"位于哪一個或哪幾個約束邊界的匯交處.為此，需要把約束全部考慮進(jìn)去，并取不足作"J約束的相應(yīng)乘步為軍，則最優(yōu)解的一階必要條件應(yīng)把：公式改為：V/XCZ匕（X*）=0f=i4,二o/（一）之。否M（X，）=Sf=L2（5） EP型約束問題的一階必要條件（P41）門維等式約束優(yōu)化甬min八X）.冢t.h（X）=O.J=1,2A772.X,為最優(yōu)點的一階必要性條件為；月勺（X）=°y=i（6） GP型約束問題的一階必要條件（P41）設(shè)

14、n維一般約束優(yōu)化問題的頗學(xué)模型為min八gOV）NO*/=1勺（X）=O,j=階必要性條不牛為3文昌”馬（工T）一支打；勺=o2；之O助（X"）三。可5=L2/*（7） Kuhn-Tucker條件（K-T條件）用于判斷某可行迭代點是否可以作為約束優(yōu)化點輸出步驟K-T條件檢驗?zāi)车c是否為約束最有點的步驟（P42）K-T條件檢驗?zāi)车cX,是否為約束最優(yōu)點的步驟二<r/ii（1）檢驗天工是有為可行點.為此相要計自（。）.t助（XQ之CM=L2,./C2）選出可"點X*處的起作用約！k.面面已求得個什L其中零成相”儲妾近零的約束就是起作JIJ約束.把這些起作用約束一直新編

15、排成序列用（*，=L2.，/<3>計算X一點;處的II標(biāo)函數(shù)的梯度"（X*）和，個起（1用約束函數(shù)的梯度第（X"）C4）按照K-T條件，上點應(yīng)該滿足W（工7）工義,/乂*#）=02|=。a=L2.，/）”成分量的形式，則TT回區(qū)）物（*）鼻陽n陽（MJ冬X2二AI七CXjClxCXjSxx9（）.6J了（）Va工士c2祗匕Sxj夕（XQx9（X力W*Q,甌/彥*）石況-名冬乙、一。由于矢岸赤品（XQ”F=1.工I線性無關(guān)，所以方程存在唯解,求翩1二面的方科:纖*求得妤乘4.2.乙昔所仃的乘戶均為11仇，久之。,/=L2,-,，則A為約束錄優(yōu)附3否則就不忍.例題2

16、.9利用K-T條件判別某點是否為最優(yōu)點（P43）7.凸集（1）凸集的定義與性質(zhì)：（P28）空集也是凸集定義2.12集介LU后也»它和,匕丘。以及任意的數(shù)AW61xxl+（I-a）x2eC則稱。為凸集.AXi+（1-A）X2eC稱為XfX-2的凸組合。性質(zhì)1:任意一組凸集的交仍然是凸集。（2）在凸集中，比較重要的特殊情形有凸錐和多面集。（P29）定義2/L4設(shè)集合匚”，若VXE。及任意的數(shù)3之0,均仃axec,則稱。為錐，乂若是凸集，則稱為凸錐.定義2J.5有限個半空間的交Ax<b稱為多面集，其中且為mX門維矩陣，b為小維向廿口若&=。則多向一集©工<0也

17、是凸錐，稱為多面錐,定理27集合口為凸集的充分必要條件是VA及仃點數(shù)%>。=1.2AA>2）,12：=iA=I,Tf£LAXeU定理2.8集合O為凸錐的充分必要條件是VAEU及任意數(shù)%>n（t=i,2k.k>a）,均仃52之1入、:eC（3）極點（P29底P30例子）定義2/16設(shè)C為北空凸集XcC*X不能表示成C中兩個不同點的凸組合；換言之，若設(shè)X=AM+（1-入）人以Aw位，1XnX；WC必推得X=.Vl=X上則稱X是凸集C的極點.（極點一般為圖形的端點和圓的圓周（個人見解）（4）極方向（P30）定義2.17段C為/心中的閉凸集.尸為小等向虱如果對C中的每

18、一個X,都仃射線(X+A/J|A>()<zC7.則稱向俄P為C的方向.乂設(shè)鼻和口足的兩個力向，若對任何比數(shù)人有八#八修.則稱日和縣是兩個不同的力向.若C的方向P不能表示咸該集合的兩個不同方向的正的線性組合,則稱P為C的極方向.(5)表示定理(P31)定理2.9(RepresentationTheorem)設(shè)C=X|工X=九X二。為非空箓面集.則有<1)極點集非空,且存在行限個極點Xi.X*X江(2)極方向集合為空柒的無孌條件是C仃界.若C無界*則存在有限個極方向修，危(3XeC的充要條件是x=二3'X*+"工其中£乙%=1,%20(»=1

19、,2廄)*"才>0(J=1,2I)(6)凸集分離定理(P32)凸集分離定理是凸分析中最重要的定理之一。定義2.18設(shè)G和。N是心中的兩個非空集合，丹=的是超平面，若對于每一個4tG都有產(chǎn)X2次,對于每一個jfwc，都有X<a(或情況恰好相反).則稱超平面H分離集合g和G.'定理量。若Q為閉凸集，Xq星U貝”存在口石0*0以及數(shù)creRiXtfVJTe<7,育。丁一MN"A并且存在工W匕,使得"丁工=".定理211設(shè)O為凸集.工0£C，卯存在門E衣”.門KO,使得PXeU書，X三門二定理2-1望設(shè)Q為閉口集a貝UQ可哀為

20、所育包含C的半空間的文，即U=|£X|三a茸中國“工.廣WJ5"*1|<JT|aTJCacr=Ua*O-8 .凸函數(shù)(1)凸函數(shù)定義(P32)定義2/ig設(shè)函數(shù)4%)定又在凸集上，若對任意的.。，工3wc及任意的VNe(O，D都有/(工/+Q-工)MA/(A；)+a-A)/(X2)貝u稱函卻on為凸集c上的凸函數(shù).如果對任意互不相同的.,*之EC及任意PNw(O,l)和有+0-占)</(豆)+Q-口圣)則稱函數(shù)八太)為凸集c上的嚴(yán)格凸函數(shù).（2）其他相關(guān)凸函數(shù)的定義（P3233）（3）凸函數(shù)的性質(zhì)定理：（P33-34）定理2.13設(shè)以是定又在C上的凸函數(shù)，其中C

21、是2T中的一個非空凸集，則對于任意實數(shù)水平集口片=彳|/（犬）與/?,萬£（7是凸集.凸函數(shù)的判定（P34）定理，14設(shè)廠匚=期f#是可微函數(shù).其中乙集.黑）C1>/為凸函數(shù)的充彩條4半是=X工wu,都有八必）之人為）+DCA71A<與一項）<251><2）f為產(chǎn)格凸密效的充要條件是,A"2e<7且都有/CAS>>>+PJXX、產(chǎn)工工-M凸函數(shù)判定的二階條件：（P35）定理2.15設(shè)力c=*是二次可微函數(shù)，。為非空開凸集，則/為C上凸函數(shù)的充要條件是，HKse矩陣在。上到處半正定.證明參見（陳寶林最優(yōu)化理論與算法清華大學(xué)

22、出版社）.定理216設(shè)齊c二內(nèi)小是二次可微函數(shù)，C為非空凸集，若Hesse矩陣鏟與在C上處處正定，則/在C上為嚴(yán)格凸函數(shù).9 .凸規(guī)劃（不會）（1）定義：（P35）主要看書定義224設(shè)fCuR”其中C是非空凸集，/是凸函數(shù)，則形式為的問題稱為凸規(guī)劃問題.（2）極小點的性質(zhì)：定理2.17設(shè)X"是凸規(guī)劃問題的局部極小點，（1）則1是凸規(guī)劃問題全局極小點；（2）若f是丹格凸函數(shù)，則X*是凸規(guī)劃問題的唯一全局極小點.定義225形式為的函數(shù)稱為n元二次函數(shù)，其中站Mqnn4口Q12Q是對稱矩陣Q=心_4相4鵬工fd、=十小丁木十U二工255)若Q為正定，則稱C255）為正定二次國數(shù)，注意至UW

23、/（M=Q由定理216知，正定二次遹數(shù)是嚴(yán)格凸函數(shù)，在最優(yōu)化算法構(gòu)i£中它起專心殊的作用.第三章1 .線性規(guī)劃數(shù)學(xué)模型和基本概念（1）線性規(guī)劃的數(shù)學(xué)模型所滿足的三個條件（P46）每一個問題都用一組決策變量瓦訪）贏F表示某一方案；每組值就代表一個具體方案。有一個目標(biāo)函數(shù)，可用決心額變量的線性函數(shù)來表示，按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化或最小化。有一組約束條件，可用一組線性等式或不等式來表示。（2）線性規(guī)劃的一般形式（P46）Cii*+力iw*士+*.三<=-三石產(chǎn)1+C8Kq+G工4mV£='A%£占+=e2三-11-M<=-X1*Xn*.r

24、NO-口一.-Ur1”i依目卻由線奉致口壇價值率致%4、E”11故鑿海孝牧%*=1.N-加J=1.2.”,1間做約束舞致心技術(shù)奉察t（3）線性規(guī)劃的標(biāo)準(zhǔn)型（P47）矩陣-向量形式的標(biāo)準(zhǔn)型略（P47）minx?,，x)=。內(nèi)+cm+-*“11*1+門1工*2十1"ad+22X2十.十%產(chǎn)J+"切2工2+一十門四Xpx2,*一，k"=0,目標(biāo)函數(shù)要求最小，所有約束條件都是等式約束.且所有決策變量都是非負(fù)的（4） 一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)型（P47-48）W加x'減若H標(biāo)函數(shù)足求髭入他的問題,這時只；帚將所仃口標(biāo)由數(shù)系數(shù)乘以一1*求山1人f直的I-d跑就變成r求m小f

25、直的m幽，upmaxZ(AR)=miii7'(A")心約束張Pi為不等式日寸.種是不等式，則可在“三”不笠式的左端加入一個仆貨的新變討松馳變量）.把不等式變?yōu)轶沂剑毫硪环N地"三”不笄式.則可在：“之”不等式的左端僦去一個“仇松弛變垃（剩余變量）t把不等式變?yōu)榉绞?松馳變量在目標(biāo)函數(shù)中對應(yīng)的系數(shù)為零0若存在取值無約束的變量4,可令4=匕一匕其中花之?？诶}3.1如何將一般形式的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式（5）線性規(guī)劃的基本概念（P48）線性規(guī)劃標(biāo)準(zhǔn)形式的約束條件AX=b.X"其中，A>jwxn矩陣，n>mtbm維向收。設(shè)矩陣A的秩為，（行滿秩），

26、則/中必存在，階非奇異F矩陣B。把矩陣A的列進(jìn)行可能的更新排列,使得=艮NJq1%工%A=勺勺3=4，為小犀=】1 *即8=片,鳥,R上士顯然.矩陣B可逆b=弓鳥，q1,、=心與、咐r'VWB+1其中入占的分城與云中的列對成，X、的分中:與W中的列對成稱分為線性規(guī)劃問題的一個軾矩PU或稱為基力基矩陣中的列向量與月，己稱為基向量，其余變量%+廣稱為非物變?nèi)绻庥譂M足非負(fù)條件，則稱之為基可行解，此時的基B稱為可行基基可行解中非零分量的個數(shù)不會超過m,若基可行解中非零的個數(shù)恰為m,稱此基可行解為非退化的基可行解，否則稱為退化的基可行解。若一個線性規(guī)劃的所偶基可行解都是非退化的，稱此線性規(guī)劃

27、是非退化的。2 .線性規(guī)劃的基本定理(1)引理3.1:設(shè)*是標(biāo)準(zhǔn)型線性規(guī)劃的可行解，'為基可行解的充要條件是，彳的正分量對應(yīng)系數(shù)列向量線性無關(guān)。(2)定理3.1:線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。(3)定理3.2:若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點上達(dá)到最優(yōu)。3 .單純形法(P50-54好好看吧)(1)單純形法的思路：從可行域中某一個基可行解(一個頂點)開始，轉(zhuǎn)換到另一個基可行解(頂點)，直到目標(biāo)函數(shù)到達(dá)最優(yōu)時，基可行解即為最優(yōu)解。(如書本P51圖3.1所示)(2)單純形法計算步驟：(P51-52)單純形法表P51(首先要化成標(biāo)準(zhǔn)型)單純形法流程圖

28、：P52(3)初始可行基的確定(P53)(表示看不懂)http:書中的檢驗數(shù)應(yīng)由書本P51(2)中公式所得，Ci的值會影響檢驗數(shù)的值。看完視頻以后可看例題3.2單純形表法求解線性規(guī)劃問題。4 .大M法(限制條件中含有等式)(1)使用條件：當(dāng)系數(shù)矩陣中不含單位矩陣，沒有明顯的基可行解時，單純形法難以使用。(2)大M法的思想：在約束條件中加入人工變量，構(gòu)造基矩陣為單位陣的線性規(guī)劃問題的標(biāo)準(zhǔn)型。同時將人工變量在目標(biāo)函數(shù)中的價值參數(shù)為M,M是一個很大的正數(shù)。在迭代過程中，將人工變量從基變量中逐個換出，如果最終所有的檢驗數(shù)均大于零時，基變量中不再含有非零的人工變量，這表明原問題有解，否則無解。(3)解題

29、步驟：參考P55例題3.3對于線也規(guī)劃向鏗minf(X)=2cixis.Jj;=lai；x=b<h,N。)，i=L2,m<jMJ1引入人工變量F+構(gòu)造輔助的線性規(guī)劃問題_n.minf(X)=>：匚產(chǎn)十):Mx】,j=<j=Tl*n口“；x.+h<b.NO),!I-2,，m5.t*,=iK-2O.i=1.2.n.n+1.-.n+Elkj寫成矩陣的形式minf(X)=CX+McTXJAX+=b3.X>O,X口NOIE中e-LULjf,X,=、*».45尸M是相當(dāng)大的正數(shù)（可以理解為正無窮），對人工變量起到懲罰的作用，逼迫輔助線性規(guī)劃的最優(yōu)解中人工變景均

30、為0.5 .兩階段法（限制條件中含有等式）（1）解題步驟：（P56-57）第一階段：給原問題加入人工變量，構(gòu)造只含價值系數(shù)為1的人工變量的目標(biāo)函數(shù)且要求實現(xiàn)最小化，其約束條件與原問題相同，利用單純行法求解問題。若得到g（x）=0,這說明原問題存在基可行解，可進(jìn)入第二階段，否則原問題無可行解，停止計算。第二階段：將第一階段計算得到的最終表，除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計算的初始單純形表進(jìn)行計算。例題3.4兩階段法求解線性規(guī)劃問題。（P57）6 .對偶問題的基本原理（1）原問題與對偶問題的表達(dá)形式和關(guān)系原問題的標(biāo)準(zhǔn)形式minf(X=亡,羽+c-x-Hnch

31、bx,»>££u%內(nèi)+%+即”，N、Hr.X,+建強Xb>XI1上W""VI上Sjj喂'+“X'+”由42bMX、*，xt>().1V對偶問題的標(biāo)準(zhǔn)形式mux瑟(丫)=電¥|+b2y2+叫1Y力+amlyni<%。工、+%工力+TaymM%，號,J限切+a8y工+，TaQm<cn,.y.y.n=。兩者對應(yīng)關(guān)系：見書本P61表3.7所示(2)對偶原理：(P61-62)弱對偶原理：對偶問題(max)的任何可行解y°,其目標(biāo)函數(shù)值總是不大于原問題(min)任何可行解20的目標(biāo)函數(shù)值。對

32、偶定理：假如原問題貨對偶問題之一具有有限的最優(yōu)解，則另一問題也具有有限的最優(yōu)解，且兩者對應(yīng)的目標(biāo)函數(shù)值相等。加入一個問題的目標(biāo)函數(shù)值是無界的，則另一問題沒有可行解?；パa松弛定理：假如即和分別是原問題和對偶問題的可行解，是原問題剩余變量的值，即是對偶問題松弛變量的值，則丫口、口分別是原問題和對偶問題最優(yōu)解的充要條件是嚴(yán)加+V呼=0(3)對偶問題的迭代算法步驟(P63)(11找出原問題的一個拈,構(gòu)成初始的對偶可行的基本解，使所有的檢驗數(shù)巴之。,構(gòu)成初始的對偶單純形表<2>若所右的3之0，則當(dāng)時的解是最優(yōu)解.停止計算.杏則計算J=mingIbs<O.貝”I為行上行，該行對應(yīng)的猿變量

33、為出基變埴口(3)若所有上之0,則對偶問題無界.原問即無解，停止計算，否則計算8k=min§|ar<0>=巴1一瞋J-a山則、為進(jìn)基變量保持判別數(shù)大于非負(fù)，即對偶問題的可行性(4)以%為主元素進(jìn)行遼代,然后轉(zhuǎn)P1到步驟(2)o例題P64-65使用對偶單純形法解線性規(guī)劃問題7.線性規(guī)劃問題的靈敏度（會分析當(dāng)系數(shù)變化是，最優(yōu)解和最優(yōu)值的變化情況）例題3.9(P66)例題3.10(P68)（1）價值系數(shù)G的變化（P66主要是那個不等式）（2）資源系數(shù)%的變化（P67主要是那個不等式）第四章1.一維搜索法基本概念（P71）（1）迭代算法：選取一個初始可行點，然后根據(jù)現(xiàn)有的信息確定

34、本次迭代的一個搜索方向和適當(dāng)?shù)牟介L。»拽素方向（2）一維搜索法：從已知點兒出發(fā),沿著某一下降的探索方向來確定步長k的問題.實質(zhì)是單變量函數(shù)？（t）關(guān)于變量的一維搜索選取問題。直線搜索有精確直線搜索和非精確直線搜索。（3）精確直線搜索：求”使得目標(biāo)函數(shù)/沿著方向尸法到極小，即=m小<p（n=min/（工上若碎連續(xù)可微的，那么由精確直線搜索得到的步長因子滿足丫/（牙2尸七=YA（X-卜我了克=0一維函數(shù)的奴，）=+/已）在極小點處滿足“=0因為kF步長稱為最優(yōu)用&精準(zhǔn)一維搜索法可分為兩類：試探法：需要按某種方法找試探點，通過一系列試探點來確定極小點。函數(shù)逼近法（插值法）：用

35、某種較簡單的曲線逼近本來的函數(shù)曲線，通過求逼近函數(shù)的極小點來估計目標(biāo)函數(shù)的極小點（4）非精準(zhǔn)直線搜索求（便用目標(biāo)的數(shù)沿著方向尸.褥到可接會的下隙st.是可接受的,2 .搜索區(qū)間及其確定方法（1）求解以為最優(yōu)化問題的步驟：（P72“簡言之”）A先確定它的一個有限授索區(qū)間0Q把問題化為求解問題也WF)>通過不斷縮短區(qū)間S2的長度,最后求得最優(yōu)解.(2)搜索區(qū)間的定義：(P72)設(shè)中：滅fR1.廠EO+8乂，右OaxD.若存在閉區(qū)間S中（/*）=min.（，）切U5+8KmbuO.rmM）一切，則千爾門一占牌MJ股(4三)g攜素區(qū)同(3)加步探索法：(P72底-73)加步探索法的思想：P72底

36、-73加步探索法的步驟：(P73)(1)選取初始數(shù)據(jù).選取初始點小，計算外=加)出初始步長/i()t加步系5tct,令內(nèi)=方0，？1=，加(2)令心=，1+加置人上+1;(3)若儀Q)三火G，轉(zhuǎn)(4),否則轉(zhuǎn)(5);(4)令*=r"=口,佇=>1，<px=h=G£h,轉(zhuǎn)(2)；(5)若Q1,轉(zhuǎn)(6)，否則轉(zhuǎn)(7)；(6)令=-/1,轉(zhuǎn)(2)：(7)令3=52=3"1=如停止計算，極小點包含區(qū)間由心或回用在加步探索法中，一般建議a=2;初始點要盡量取接近于問題的最優(yōu)解；(4)單谷區(qū)間和單谷函數(shù)：定義：(P74)定義4N設(shè)中：足一交閉區(qū)間小句u&L

37、若存在點.使得中在S"卜一嚴(yán)格速感，尹在【，二切上嚴(yán)格遞峭,則稱5句是函數(shù)以，)的單谷區(qū)間，*")是口句上的單谷函數(shù)一性質(zhì)：(P74)若一個區(qū)間是某函數(shù)的單谷區(qū)間，意味著，在該區(qū)間中函數(shù)只有一個凹谷(極小值)。某區(qū)間上的單谷函數(shù)在該區(qū)間上不一定是連續(xù)函數(shù)。凸函數(shù)在所在區(qū)間上必然是單谷函數(shù)。定理4設(shè)產(chǎn)：川f川.«方雇尹Q)單份區(qū)間.任取并且G<G-W*J11)若有尹氏)與WG則已.切是w(號向少區(qū)|1U則H/J是小。)的單谷X回經(jīng)過函數(shù)值的比較可以把單谷區(qū)間縮短為一個較小的單谷區(qū)間。把搜索區(qū)間無限縮小，從而求出極小值。(黃金分割法的主要想法來源)3 .對分法(

38、1)二分法原理：(P75)為=o.假雙中m/是單減刖微：在，*.切是單增函數(shù).所以育>feS"*),門覽立中'(，)vO,所以/<")v。>FW*r小)，成立/(/)>。/以R3),O(2) 對分法迭彳t步驟(P75)1,確定初始搜索區(qū)間S&L要求”(n)V0./3)aO2 .i十第凡6的中點亡=。.5(0+6).3 .若中'(c)v0,貝11口=白.轉(zhuǎn)(4)：若中'(白)>0,貝IJZ>=G轉(zhuǎn)(4)：若中'(c)=0,貝卜*=c轉(zhuǎn)(5)；4 .若一切<£"!肘*=0-5(

39、仃+力).轉(zhuǎn)C4)FF則J轉(zhuǎn)<2)5 .打印產(chǎn),結(jié)束4.Newton切線法(1)原理：(P77)Newton切線迭代公式設(shè)區(qū)間s切|中經(jīng)過欠迭代已求得方程40)=o的一個近似根過(公#G)作曲線的切線.其方程地y-©S=-)(樂4)用這條舊紋匕橫袖支點的橫飛標(biāo)作為及優(yōu)點的新的近似.皿、人=022Newton切線法<i>確定初始搜索區(qū)間s.2一要求中'S)>oO選取初始迭代點(3,H算/<Q)°(4)若|1。上凡停止誥代，鐲出f,否則今2F,轉(zhuǎn)步褰<3)(3)優(yōu)點：(P78)收斂速度很高。如果初始點選得適當(dāng)，通常經(jīng)過幾次迭代就可以得

40、到滿足一般精度要求的結(jié)果。可證明至少是二階收斂的。(4)缺點：(P78)需要求二階導(dǎo)數(shù)。如果在多維最優(yōu)化問題的一維搜索中使用這種方法，就要涉及Hesse矩陣，一般是難于求出的。當(dāng)曲線y=0(t)在a,b上有較復(fù)雜的彎曲時，這種方法也往往失效。即使曲線比較正常，在a,b中或者凹或者凸，初始點的選取必須適當(dāng)。5 .黃金分割法(1)原理：(P78)在單谷區(qū)間a,b適當(dāng)?shù)牟迦雰牲ct1,t2,通過比較這兩點函數(shù)值的大小來縮短區(qū)間的長度，依次迭代。(2)黃金分割法算法步驟：(P79),絨)=0一382*維|印層三<1>確定WO的和J女臺土素(2)t+我G=C+門),中上=守On)(3>i

41、|71=c+中'=)：(口)右k1川打E|j二=二巴,千手機二百山隊4專(5).2(5)關(guān)U另II是不愛商LL三巴：若：兩足，貝IJ置燃后轉(zhuǎn)3,百貝U*S方=產(chǎn)"6=t工中、=中二聲士=c十a(chǎn)),卬2=燃啟車專9.6 .拋物線插值法(1)原理：(P81)拋物線法就是一個用二次函數(shù)來逼近？的方法，這也是我們常說的二次插值法。(2)拋物線插值法迭代步驟：見書本P82-83(3) Matlap求解第五章常用無約束最優(yōu)化方法1 .分類：直接搜索法(直接法)：在計算過程中只用到目標(biāo)函數(shù)值，不必計算導(dǎo)數(shù)。(坐標(biāo)輪換法、單純形法)間接法：在計算過程中要用到目標(biāo)函數(shù)的導(dǎo)數(shù)。(最速下降法、Ne

42、wton法、共軻梯度法、變尺度法)2 .最速下降法：（1）基本原理：見精準(zhǔn)直線搜索法（P87）若每次迭代的搜索方向比取目標(biāo)函數(shù)的負(fù)梯度方向，即%=T/戢），步長打取最優(yōu)步長，由此確定的算法稱為最速下降法。（2）最速下降法迭代步驟：（P87）迭代公式X2=項一，k=31.2,共中人按如尸確定/區(qū)T"區(qū)）=nunf'X*-而單記為JT-=由-Y/X鞏）為并寫方便記?（x）=Y/X%）則g（Ah）=yf（A;）最速下降法的迭代步驟士（1）選定初始點甩計算加/%*=o（2）作門線搜索工覆*1=應(yīng)覆.-3）計算人="工"）"=以（3）用終止準(zhǔn)則愴驗是否泄足

43、：若滿足，則打印最優(yōu)解否則，wik=k+i轉(zhuǎn)（2）.最速下降法運用于正定二次函數(shù)（P87-88）例題5.1（P89）（3）特點：線性收斂，當(dāng)距最優(yōu)點較遠(yuǎn)時，速度快，而接近最優(yōu)點時，速度下降。該算法簡單，每次迭代計算量小，即使從一個不好的初始點出發(fā)，往往也能收斂到局部極小點3 .Newton法：（1）適用范圍：如果目標(biāo)函數(shù)具有連續(xù)的二階偏導(dǎo)數(shù)，其Hesse矩陣正定，可用Newton法。此方法收斂速度很快。（2）原理：（P90-91）從初始點開始，每一輪從當(dāng)前迭代點出發(fā)，沿著Newton方向并取步長&=1的算法稱為Newton法。（具體看書本）（3） Newton法迭代步驟：（P91）&l

44、t;1>選定初飴點*：計舞兀MXb）,£。一應(yīng)事）,置*=o（2計算.3由方程G女戶去=gk解出產(chǎn)*-<4>計算丫7=*無+/hA+j="*7上宮2=江*2）<&>判別空止隹則是否遹足：若活足，則打印/優(yōu)（*計14»1）停機：否貝h翼A配+1.轉(zhuǎn)例題5.2Newton法迭代的運用（P91-92）從Newton方向的構(gòu)造知道，對于正定二次函數(shù)，Newton方向就是指向其極小點的方向.因此，用Newton法解目標(biāo)函數(shù)為正定二次函數(shù)的無約束最優(yōu)化問題，只需一次迭代就可得最優(yōu)解.(4) Newton法缺點對初始點要求嚴(yán)格。一般要求比較

45、接近或有利于接近極值點，而這在實際計算中是比較難辦的，當(dāng)初始點遠(yuǎn)離極小點時，牛頓法不一定收斂。當(dāng)Hesse矩陣非正定時，Newton方向不一定是下降方向，經(jīng)迭代，目標(biāo)函數(shù)值可能上升，Newton法的搜索將會失敗.在進(jìn)行某次迭代時可能求不出搜索方向。若目標(biāo)函數(shù)在Xk處Hesse矩陣為奇異，則求不出，因而無法構(gòu)成牛頓方向，從而迭代無法進(jìn)行。牛頓方向構(gòu)造困難，計算相當(dāng)復(fù)雜，占用機器內(nèi)存相當(dāng)大。4 .修正Newton法(1)原理：(P93)為了克服Newton法的缺點，人們保留選取Newton方向作為搜索方向，摒棄其步長恒取1,而用一維搜索確定最優(yōu)步長，由此產(chǎn)生的算法稱為修正Newton法.(2)修正

46、Newton法的迭代步驟：(P93)<1>選定初始點置KO(2)求梯度向?qū)m產(chǎn)近必上若|vycvc昨后，停止迭代，輸出否則轉(zhuǎn)(3)(33本勾造Zawton方向，計算仃一弋取與=工7'(工XTW(兌)<4>迸行一維搜索*求心使得八"+"鼻、=ffzxJ(3)算法說明：修正Newton法克服了Newton法的缺點。由于含有一維搜索，每次迭代目標(biāo)函數(shù)值一般有所下降(絕對不會上升)當(dāng)?shù)c接近于最優(yōu)解時，收斂速度快，對初始點的選擇要求不嚴(yán)。求解的計算量和存儲量均很大。5 .共軻方向法(1)計算量小，收斂速度沒有Newton法快，但比最速下降法快得多。(

47、2)概念：(P97)從任意點X0出發(fā)，依次沿某組共軻方向進(jìn)行一維搜索的求解最優(yōu)解問題的方法，叫共軻方向法。(3)原理：書本(P94-97)(4)共軻方向法迭代步驟：(P98)已知具有正定用建/的二次函數(shù)和紹止限總八*)=+<7(1)選定初始點合和Y降方向廣Q謾音=。(2)作立線拽素3g尸Q<3>判別|石星否滿足士若滿足停止，打印國一否則轉(zhuǎn)C4>:(4)提供共舶方向尸I使得P：APp=0,7=O.L.曲(S)k+I,轉(zhuǎn)2)6 .共輾梯度法：(1)每一個共軻向量都是依賴于迭代點處的負(fù)梯度而構(gòu)造出來的，稱為共軻梯度法。(2)基本原理：(P99-100)(3)迭代步驟：(P10

48、0-101)日親口目標(biāo)函數(shù)/匚V)手口繞止限后CDHfJ®求初始梯度.計容V/XTQ,者-停止.播出4否蛔轄杓造的始拽素方向弓vrc-vo>»*=o<4>®進(jìn)行一維搜索，求以使得，(x1r+)=3mx1c十e)一？-%-=三三±三飛寶(5)*一號止.輸田+1.否則轉(zhuǎn)g>©檢驗送代數(shù)口若上+1=不令-乂=4Z轉(zhuǎn)(3),否則轉(zhuǎn)(7)構(gòu)造共甑方向.取X=11V(土+1)|尸J尸當(dāng)IIYAX/LE”)*令人二1,車訝(4)例題5.3共軻梯度法的運用(P102)(4)算法說明：(P103)可將共軻梯度法看作是最速下降法的一種改進(jìn)。

49、當(dāng)令入k=0時，就變?yōu)樽钏傧陆捣?共軻梯度法由于不涉及矩陣，僅僅存向量，因而存儲量小，適合于維數(shù)較高的優(yōu)化問題。共輾梯度法不要求精確的直線搜索.但是，不精確的直線搜索可能導(dǎo)致迭代出來的向量不再共軻，從而降低方法的效能.7 .變尺度法(擬牛頓法)(1)基本思想：用不包含二階導(dǎo)數(shù)的矩陣近似Newton法中的Hesse矩陣的逆矩陣(2)基本原理：(P103-104)(3)Hk需滿足的三個基本條件：<i)日列中的矩陣要求是對陣正定的12)要求為之間的迭代具有簡單的形式(3)"*必須滿足扭牛頓條件(4)變尺度法迭代步驟：(P105)重點：DFP算法(1)基本原理：(P106-107)DF

50、P算法校正公式:(2)迭代步驟：(P107)<1）會定初F始點方，終止眼上<2）?7.JJo=Z,戶o=F520<3）作豈會受投素X*i皿蒼.馬）八卜維We=暮3<4）檢救足否7的是登二Hl：刈*心IlYTQVQlHs爪子I上，輪（5）77Xr=>j,?i.A=AVhip圣>=瘀7轉(zhuǎn)。）二否則依（6（G>t十堂K"*=&*7Sjt-S范=£*+JfeH*十*=/T由*s*s；_£：八y*A*.I=一衣.£/+例題5.4DFP算法的應(yīng)用（107-108）BFG鯽法：基本原理：（P109）者慮如下校正公共_S

51、*SfH*>*a；H*H=H*+安七+43：工）3E乜尸Q以"當(dāng)戶=O時就是。尸P校正公式一令一1口針力到著名的m尸GS校正公式譚晨、62：一b#2：-工4能3*J（2） BFGS迭代步驟：（P109-110）第一步冷定戾矢號初始點國j.初始衙陞=/,i卜算自s令e。桂陽.第二步令尸土二乜之一第三步由柿砒一鰥E秧素砒j定弗氏以，*+4廣*>吧蟲>，*+%產(chǎn)*:第四步令*A1=*產(chǎn)無第五步君以illlW則*=*-l=5tOp.否則令以=Mjt一1-K公第六步衣*7=H*+/7。之父一HqT_£.*-令m,轉(zhuǎn)第迦（3） DFP算法和BFGS算法比較：（P111

52、）兩者迭代過程相同，區(qū)別在于校正矩陣選取不同，兩者在精確一維搜索下，得到的點列是一致的。在不精準(zhǔn)一維搜索下：DFP法：由于一維搜索的不精確和計算誤差的積累可能導(dǎo)致某一輪的Hk奇異。BFGS法：對一維搜索的精度要求不高，并且由它產(chǎn)生的Hk不易變?yōu)槠娈惥仃?。BFGS法比DFP法更具有好的數(shù)值穩(wěn)定性，它比DFP法更具有實用性。8.坐標(biāo)輪換法：（屬于直接法）（1）基本思想：將含有n個變量的優(yōu)化問題輪換地轉(zhuǎn)化為單變量（其它變量視為常量）的優(yōu)化問題。所謂單變量優(yōu)化問題就是沿某個坐標(biāo)軸方向進(jìn)行一維搜索的問題。（2）基本原理：（P111）（3）坐標(biāo)輪換法的迭代步驟：（P112-113）打個坐標(biāo)車由方向依次為6

53、=L5O.,o1r%=O,LO.丁q=口。0T（】）給定的J站級tlJ-Ue用孑叟素/向汨<3>核卜，弋求取彳無之匕氏3/迸彳/造彳?1卜弊八，ff+%）=minXf-”+，弓）了a=Xf+限但工弋中后=1.2.內(nèi)需i以；次數(shù)，了為所壞中一經(jīng)電技素的呼與F4辦力成優(yōu)步長<4>如果牧（5M否貝口裝。上<5>為泗足|國T工上前與總叫修M消命山（工尸）“丁,在手W»J令Kzq<3>例題5.5坐標(biāo)輪換法的運用（P113）9.單純形法（1）基本原理：（P115）（2）單純形法迭代步驟：（P116）（1>構(gòu)造初始單純形在打維空間中選初始點與，

54、從與出發(fā):，沿著各坐標(biāo)方向以步長f挈動得至，個頂點也1P-上8”工-一1,町-Xq這悻取可以保證線性無關(guān)否則會便搜素拒圍尋眼在較低維的空間，有可能找不到班小點.在各坐標(biāo)方向可以移動不同的距離.步長r的范圍可取651£5開始取f=16-2.0.接近最優(yōu)點時;魔封、,倒女口取1=0.51O<2>計算各項點69的數(shù)值乂=八%，ri=。1口比較各函續(xù)值六<b+6定限好點/差層j科次：差點X-BP>£-工>-min工-O,L2.-生«y=_At-Vw>=maxyiri=0,1,Zr-'Tn=，（年方）=max>T/?i=0.1,-*-