最優(yōu)化知識點(diǎn)+名詞解釋

1.等值線定義L6在高維空間（n>3）中，使目標(biāo)函數(shù)值取同一常數(shù)的點(diǎn)集｛X\f（X）=烏匚為一常數(shù)｝稱為了（X）的等值線（或等高線、等值面）O可微|險(xiǎn)f(X°+P)7W)e以=°IIPII項(xiàng)(1-2-4)定義1.7設(shè)/:ZJcRt（tR,且X|險(xiǎn)f(X°+P)7W)e以=°IIPII項(xiàng)(1-2-4)11^11則禰六X）在X"可微。梯度定義1.9（梯度）以/（X）的"個(gè)偏導(dǎo)數(shù)為分量的向量7j（x）稱為H.X）的梯度，星然vf（x）=M”(X。)”(X。)M(X。)dx[3x2方向?qū)?shù)定義Lit)(方向?qū)?shù))設(shè)尸€R\||P||=L可微函數(shù)/(X)在X點(diǎn)沿方向F的方向?qū)?shù)定義為：酎(X)=lhii.f(X+〃P)—f(X)TOC\o"1-5"\h\zdPoto+ n=Um"X)馳p)+miwi)□tU+ Q=limV/(Xf(P)+邛蒂|(zhì)|F|| (126)a—>0~ ||Qjr|-Vf(X)7P=||V/(X)||COS(W(X)?P)向量值函數(shù)定義1.12(向量值函數(shù))g(X)是一個(gè)向量值函數(shù)，若qDcRRrt\即g(X)=3(X)0(X),…：加(X)廣列火X")(1-2-7)如W)為i(x。)

fJ：］j 列火X")(1-2-7)打化(X。)打如X。)▽g(X”)="月 如"為新X。)膈ex。)為新X。)為向量值函數(shù)￡/(X)在X。處的導(dǎo)數(shù)或"松矩陣。莎y(Xi\決(如也］"X、a工e.定義1.14▽)(屋)稱為/"(X)關(guān)于X的二階導(dǎo)數(shù)，莎y(Xi\決(如也］"X、a工e.▽”'(X)=*(X)=為(X)打標(biāo)兄/(1-2-8)7.Taylor展開式定理L1S設(shè)了：Ou/TtR,若/(X)在X"的某個(gè)領(lǐng)域N(X\S)內(nèi)二階連續(xù)可微，則對任意的XGN(X\8)在X°處有1街乂口廠展式/(X)=/(X。)+W(x如X—X。)1 (1-2-12)+-(X一X。)]▽勺(X)(X—X。)+D(||X一乂畛定義1.16(內(nèi)點(diǎn)、邊界點(diǎn)與極限點(diǎn))設(shè)。GR\X(}GRu.若存在X°的頓域N(XH)Cd,則稱X°為Q的內(nèi)點(diǎn)；如果在X。的任意領(lǐng)域中，既有X[€D,又<X2D,則稱X。為D的邊界點(diǎn)；既不是內(nèi)點(diǎn)，又不是邊界點(diǎn)的|點(diǎn)，稱為外點(diǎn)；如果存在點(diǎn)列{X”， (X*互異)，且liii以t+oc||X*—X°||=05則稱X。為O的極限點(diǎn)(聚點(diǎn))口開集閉集定義1.17(開集與閉集)設(shè)I)CR\如果。的每一個(gè)點(diǎn)都是D的內(nèi)點(diǎn)，則稱。為開集；如果Q的每一個(gè)極限點(diǎn)都屬于則稱D為閉集。|極小點(diǎn)與最優(yōu)解定義1.18(極小點(diǎn)與最優(yōu)解)設(shè)f:DU矽T/?,若存在X*€D及實(shí)數(shù)&>0,使得MXCNq(X\6)C\D都有/(X*)<f(X),則稱X*為/(X)的局部極小點(diǎn)；若/(X*)</(X),則稱X*為六X)的嚴(yán)格局部極小點(diǎn);若對vxeD,都有/(X*)《/(X、則稱稱x?為/(X)的全局極小點(diǎn)；若六X”)vf(X),則稱X*為/(X)的全局嚴(yán)格極小點(diǎn)。駐點(diǎn)定義1.19(駐疳)設(shè)/:DUITTR,X*走D的內(nèi)點(diǎn),若W(X*)=。,則稱X*為f(X)的駐點(diǎn)。一階必要條件定理L20(—階必要條件)設(shè)f:DcRvR,f具有連續(xù)的一階偏導(dǎo)數(shù)，若X*是門X)的局部極小點(diǎn)且是D的內(nèi)點(diǎn)，則V/(X*)=Oo二階必要條件定理L21(二階必要條件)設(shè)廠DCRnTR,/具有連續(xù)的二階偏導(dǎo)數(shù)，若X*是f(X)的局部極小點(diǎn)且是〃的內(nèi)點(diǎn)，則▽十(X*)半正定。二階充分條件定理1.22(二階充分條件)</PCJTtR、具有連續(xù)的二階偏導(dǎo)數(shù),X*為隊(duì)X)的駐點(diǎn)，且V7(X,)是正定矩陣，則X*是六X)的嚴(yán)格局部極小點(diǎn)。15.凸集定義1.23(凸集)設(shè)DcR\若對所有的X]X2eD.以及□G0,1],都有ciX'+(1—q)X‘色D,則稱_D為凸集口凸函數(shù)定義L29(凸函數(shù))設(shè)/:DUR'JR,D是凸集，若對所有的X',X"D,以及口￡(。：1),都有了(母+(1-ok)<W(X】)+(1-o)f(X氣則稱為D上的四函數(shù)口凸函數(shù)的必要條件定理1.35設(shè)/.DCRlR.D是非空凸集，六X)在刀上可微，則/(.X)在。上是凸函數(shù)的充要條件是對■任意的X]x2eD,都有K)>/(X1)+w(xy02—X1).定理L3G設(shè)f:DCR11tR,D是非空凸集，/(X)在Q上具有連續(xù)的二階偏導(dǎo)數(shù)，則.f(X)在D上是凸函數(shù)的充要條件是V2f(X)是半正定矩陣』定義2.5（可行集，可行域）S={X\AX-b.X>0）.基記頂2一…為1：2】.…m中m個(gè)數(shù)的一個(gè)組合，若B—琮）可逆.則召稱為線性規(guī)劃的基，服j=稱為基向量。稱為基變量，其余的變量稱為非基變量。基本解設(shè)B=（已］.P遂…,Pj”）是線性規(guī)劃（2L3）的基「其相應(yīng)的基變量XB-3刃,1論…項(xiàng)?。┢邉t方程組BXn-b有唯一解令非基變量全部為零，則得到AX=b的一組解%=V?=1.2…tm.其余叼=0.這個(gè)解稱為基本解?？尚薪鈞es基本可行解既是基本集，又是可行解。即所有分量非負(fù)的基本解。最優(yōu)基可行解，最優(yōu)基若X。是一個(gè)基可行解.且對任意的基可行解X,都有/(X0)< 則稱X。為最優(yōu)基可行解。而X。所對應(yīng)的基為最優(yōu)基心頂點(diǎn)設(shè)X°GDCR\。是凸集。如果X"不能表示為。中其它任意兩個(gè)不同點(diǎn)的凸組合，則稱X"為。的頂點(diǎn)。換基運(yùn)算(2)換基運(yùn)算：從一個(gè)基可行解〔頂點(diǎn))迭代出(轉(zhuǎn)到)另—個(gè)基可行解(頂點(diǎn))。26.單純形算法算法2.1單純形算法驟1構(gòu)造初始單純形表/PiP2■-P.b\頃]fj2…刃其中，<7j= Pj—cj,j=i.-~-.n.fo=c]b.步驟2求-nic)xi<j<n｛巧｝□步驟3若療WO,則X是讖優(yōu)解，停機(jī)；否則轉(zhuǎn)步驟L步藻4若Pi京,則無最優(yōu)解，停機(jī)；否則轉(zhuǎn)步驟氏步驟5求加=】心突"方記〉牛步驟6以四1為主元對單純形表作換基運(yùn)算得到新單統(tǒng)形表，轉(zhuǎn)步驟九在所有判別數(shù)為正的那些列中，以最左邊的那一列為進(jìn)基列，即I=niin｛j|tTy>0｝.在進(jìn)基列中有多個(gè)分量符合主元條件，則選擇基變量下標(biāo)最小的那一個(gè)“用作為主元.即0=min㈤]>0.k=min｛抒=—.%> -修正單純形法的優(yōu)點(diǎn)存儲少，每次迭代只存儲一個(gè)基矩陣的逆；運(yùn)算量減少，去掉了不參與迭代的列向量的運(yùn)算。修正單純形方法算法 孑驟1 ,-=C^B~\步馨2計(jì)算氣=勺,若所有巧非正，則當(dāng)前豪可行解為最優(yōu)解。否則轉(zhuǎn)步驟丸步算3/=iiiinOI^>0｝,計(jì)算歸1已=(制,…皿制『，若所有的財(cái)非正，則原規(guī)劃無酰優(yōu)解，否則轉(zhuǎn)步驟L步驟4求H=miii￡傍如>。｝】k=mi山｛，目=會3>。｝。步驟5形成矩陣E眼步驟6計(jì)算B!~[=EklB~\X〃，= B~]：=B!~\轉(zhuǎn)步驟L表3.2原（對偶）線性規(guī)劃變換規(guī)則表原規(guī)劃（對偶規(guī)劃）對偶規(guī)劃〔原規(guī)劃）minmax目標(biāo)中系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)中系數(shù)約束條件2變量＞約束條件＜變量至約束條件=變量無約束變量之約束條件＜變量＜約束條件＞變量無約束約束條件-31.對偶單純形算法算法3」對偶單她形算法步踝］（Pi冉…巳b\E＜T_lJ2''rfo/步驟2若b＞l）,則當(dāng)前正則解就為敢優(yōu)解，否則，取k=缶D}-步驟3若％＞0/=1?u,則原規(guī)劃（尸）無可行解，否則轉(zhuǎn)步驟翕步驟4求斜=mini勺女{潔|%＜°}?步驟5以卻為主元按照、式（3-W）對對偶單純形表作換基運(yùn)算得到新對偶單純形表，轉(zhuǎn)步驟A下降迭代算法算法4」下降迭代算法"驟1選擇初始點(diǎn)X”,步驟2按某種規(guī)則確定P七使得Vf（Xk）TPk＜（U步驟3按某種規(guī)則確定匕使得f{Xk^tfi.Pk）＜f（Xk^步驟4計(jì)算X*=X*'fh：P七步驟5判定是否滿足終止準(zhǔn)則，若滿足則輸出Xk~\f{Xk+1）.停機(jī)；否則置帝=*+1,轉(zhuǎn)步驟L黃金分割算法算注4.2黃金分割算法下驟1確定聲⑴的初始搜索區(qū)間叵瓦黃驟2計(jì)算冬=“十削b-"），S=0（."黃算3計(jì)算打一（1十Q■（石一隊(duì)）？皆1—*L）?O步驟4若h-M冬E,停機(jī)；否則，轉(zhuǎn)步驟5。步驟5若，（圮叫（坯）,則b=M如一h：斧（0）=以0）. =a-\-a（b-a）,代=郴）;否則，"=h-h=板,伉）=以切）：/2=a+0{b-a）.構(gòu)=#（圮然后轉(zhuǎn)步驟4。最速下降算法算法4.5敢速下降算法 一"驟1步驟2一維搜索以=ay^m\nf（Xk-仰行耙）），Xk+l=X&hWf（X"計(jì)算產(chǎn)+1, 竺礦f（x*+氣步驟3若||時(shí)中||＜E,則停機(jī)，并輸出X—i"1;否則*:K+L轉(zhuǎn)沙驟2。算法4.6牛頓算法7驟—給定目標(biāo)函數(shù)氏X）以及梯度o（X）, 爪陣成（X）,精度％步驟2選定初始點(diǎn)X，計(jì)算gU—glX。），置A--O0步驟3計(jì)算Hk-H（Xk）Q步驟4由方程/p代-—9上解出P*（沒有求逆，考慮到計(jì)算量），步驟5計(jì)算X廿'=Xk+P\fk~l= qk+i=g（xk+i）.步驟6判斷終止條件是否滿足？若是，則停機(jī)并輸出X*+1及產(chǎn)+1;否岷="L轉(zhuǎn)步驟3。36.共軛定義115（共貌）設(shè)Q是口X月對稱正定矩陣，如果X和QV正交，即XtQ￥=0. （4-6-69）則稱X和Y關(guān)于Q共板臼定理4.17如果非零向量組F",FL…，Pm~［（是）關(guān)于Q共輒的，則這m個(gè)向量必然線性無關(guān)心步驟2步驟步驟2步驟3步驟4妒=W\\9h\\FR共軛梯度算法算逐空血 一^?一1給定目標(biāo)函數(shù)j(X),初始點(diǎn)X°,梯度。氣捋度三，置人=若滿足停機(jī)條件，輸出X七計(jì)算PJ{—g札 k=計(jì)算PJ{一"+牌計(jì)算=xE"、砂+qm,轉(zhuǎn)步驟a推論4,23(^Flecher&.7?既"邑1964)可行域定義5.1(可行域)S壘{X|佛(X)>S頃X)=OH=1~"j=1~可行方向定義5.2(可行方向)設(shè)X￡5?若對某一個(gè)非零向量PERL存在一個(gè)d>0,使得對所有A6(0』)時(shí)，有X+XPGS,則稱P為點(diǎn)X處的一個(gè)可行方向口下降方向定義5.3(下降方向)設(shè)XGS,存在§>0,當(dāng)AE(00)時(shí)，若存在非零向量P使得f(X+XP)<f(X)成立，則稱P為f(X)在點(diǎn)X處的一個(gè)下降方向。定義5.4(可行下降方向)設(shè)XES,非零向量F既是點(diǎn)X處的可行方向，又是/(X)在點(diǎn)X處的一個(gè)下降方向。42.正則點(diǎn)/正則解定義5.7(正則點(diǎn)，正則解)設(shè)X GS,若購⑶，iGT(X),jeJ線性無關(guān)，則稱無為S的一個(gè)正則點(diǎn)。43.一階必要條件定理5.8(-階必要條件)設(shè)六X),q(X),/“(X)可微,若X*是(NEP)的一個(gè)局部極小點(diǎn)且為正則點(diǎn)，則存在人；(,GZ(f))以及芯偵6J),使得V/(X*)=￡g,(X*)+寸"MX)(5-1-5)ieT[X^ j=lA：＞0,蕾gJX，)=O,令= (5-1-6)成立巾44.K-T點(diǎn)定義5.9(KKT點(diǎn))稱(5-1-5)和(5-1-6)為KKT條件；稱滿足KKT條件的點(diǎn)為KKT點(diǎn)，或K-T點(diǎn)。定理542(二階充分條件)設(shè)了(X),o"X),，"X)二次連續(xù)可微，若X*eS,存在商，心i=Izm,j=I5,使得KKT條件成立且對滿足條件ZF(X*)=Ri A*>0;(5-1-7)Zp}">0,zeI(X*),A*=0;(5-1-8)Z「▽如(X*)=0.(5-1-9)的非零向量Z有TOC\o"1-5"\h\zm I—Ek奶(X〃))Z>0i=\ J=1(5-1-10)成立，則XWNLP)的嚴(yán)格局部最小點(diǎn)。46.外點(diǎn)罰函數(shù)法算法5.1外點(diǎn)(罰函數(shù))法 一步驟1選定X",mi>0(mi=1),C>1(C=10),k=lo步驟2以為初始點(diǎn)，求解懲罰函數(shù)(5-3-23)的最優(yōu)解X氣步驟3若mka(Xk)<E,則X*為約束優(yōu)化問題(NLP)的箕優(yōu)解，否則轉(zhuǎn)步驟N"步驟4令gp=Cmk,A：=A--F1?轉(zhuǎn)專驟⑵心內(nèi)點(diǎn)罰函數(shù)法算法5.2內(nèi)點(diǎn)(罰函數(shù))法"驟1選定WS'七>05=10)?C<1(C=(U),k=77~步驟2以為初始點(diǎn)，求解障礙函數(shù)修―?)的波優(yōu)解X，步驟3若1飛倒X"uj則X”為約束優(yōu)化問題(5-1-44)的最優(yōu)解，否則轉(zhuǎn)步驟UL步驟.4令任—I=。7幻k=k-\-I,轉(zhuǎn)步驟(2)心懲罰函數(shù)法基本思想及優(yōu)缺點(diǎn)懲罰函數(shù)法基本