1、則對k 01, 2,匚恒有f(xk1)豈f(xk)最優(yōu)化方法復(fù)習(xí)題第一章 概述(包括凸規(guī)劃)判斷與填空題argmaxf(x)二觀minmax(x): x D二Rnf = -min (x): x D二Rn；設(shè)f : D - Rnr R.若x Rn,對于一切x Rn恒有f (x ) _ f (x),則稱x為設(shè)f : D Rn R.若x ” D,存在x ”的某鄰域N；(x”)，使得對一切xN .(x )恒有f(x”)：f (x)，則稱x”為最優(yōu)化問題優(yōu)解給定一個最優(yōu)化問題，那么它的最優(yōu)值是一個定值V非空集合DRn為凸集當(dāng)且僅當(dāng)D中任意兩點(diǎn)連線段上任一點(diǎn)屬于D. .V非空集合DRn為凸集當(dāng)且僅當(dāng)D中任

2、意有限個點(diǎn)的凸組合仍屬于D. .V任意兩個凸集的并集為凸集函數(shù)f:D Rn R為凸集D上的凸函數(shù)當(dāng)且僅當(dāng)-f為D上的凹函數(shù)V設(shè)f : D乂Rn R為凸集D上的可微凸函數(shù)，X：D則對一D,有f (x) - f(X ) -、f (x )T(X - X ).若c(x)是凹函數(shù)，則D=xRnc(x)KQ是凸集。V1 12 23 34 45 56 67 78 89 9101011111212最優(yōu)化問題mWf (x)的全局最優(yōu)解x：minf (x)的嚴(yán)格局部最設(shè)x*為由求解minX出f(x)的算法 A A 產(chǎn)生的迭代序列，假設(shè)算法A A 為下降算法,1313 算法迭代時的終止準(zhǔn)則（寫出三種）1414 凸規(guī)

3、劃的全體極小點(diǎn)組成的集合是凸集。V1515 函數(shù)f : D二Rn R在點(diǎn)xk沿著迭代方向d Rn0進(jìn)行精確一維線搜索的步長:k，則其搜索公式為_. .1616 函數(shù)f:DRn R在點(diǎn)xk沿著迭代方向dkRn0進(jìn)行精確一維線搜索的步長.：k，則i f （xks_：kdk）Tdk=_. .1717 設(shè)dk Rn0為點(diǎn)xk DRn處關(guān)于區(qū)域D的一個下降方向，則對于-：0，-乜三（0,）使得xk：dkD.簡述題1 1 寫出 Wolfe-PowellWolfe-Powell 非精確一維線性搜索的公式。2 2怎樣判斷一個函數(shù)是否為凸函數(shù).（例如：判斷函數(shù)f（x） 2x1x22x|-10 x15x2是否為凸

4、函數(shù)）三、證明題1 證明一個優(yōu)化問題是否為凸規(guī)劃.（例如1TTmin f （x） x Gx c x b2判斷s.t. Ax二b（其中 G 是正定矩陣）是凸規(guī)劃x _02 熟練掌握凸規(guī)劃的性質(zhì)及其證明第二章線性規(guī)劃考慮線性規(guī)劃問題：(LP)min cTxs.t. Ax = b, x _ 0,其中，Rn,Rm n, b Rm為給定的數(shù)據(jù)，且 rankA =m, m豈n.、判斷與選擇題1(LP)的基解個數(shù)是有限的.V2若(LP)有最優(yōu)解，則匕一疋有基可仃解為最優(yōu)解.V3(LP)的解集是凸的.V4對于標(biāo)準(zhǔn)型的(LP)，設(shè)”xk由單純形算法產(chǎn)生，則對01,2，有CTXk CTXk 1. X5若x為(LP

5、)的最優(yōu)解，y為(DP)的可行解，則c x -by. V6設(shè)X。是線性規(guī)劃(LP)對應(yīng)的基B = (R,，Pm)的基可行解，與基變量Xi,，Xm對應(yīng)的規(guī)范式中，若存在-k R為一階連續(xù)可微的凸函數(shù)，X：Rn且f(x“)=O，則x為minf (x)的全局極小點(diǎn).1X1R12給定b Rn和正定矩陣G Rn n.如果x Rn為求解minf(x)=xTGx bTx的迭代點(diǎn)，d RnO為其迭代方向，且x R23 3試證：Newton 法求解正定二次函數(shù)時至多一次迭代可達(dá)其極小點(diǎn)四、簡述題1 簡述牛頓法或者阻尼牛頓法的優(yōu)缺點(diǎn).2 簡述共軛梯度法的基本思想.五、計(jì)算題1 利用最優(yōu)性條件求解無約束最優(yōu)化問題例

6、如：求解 min f (x)二器：卡；一XM- 2x2 用 FR 共軛梯度法無約束最優(yōu)化問題.見書本：例 341.3 用 PRP 共軛梯度法無約束最優(yōu)化問題.見書本：例 3.4.1.31例如：minf(x)x；x| - x1x2- 2x1其中 x0= (0,0)T,；= 0.01第四章 約束最優(yōu)化方法考慮約束最優(yōu)化問題：(NLP)min f (x)s.t.G(X) =0,iE1,2, I ;:k 0,二)為由精確一維搜索所的步長，則f (xk)Tdk(dk)TGdkG(x) _0,iI Ji 1,12, ml,其中，f,c(i =1,2, m) : Rn R.-、判斷與選擇題1 外罰函數(shù)法、內(nèi)

7、罰函數(shù)法、及乘子法均屬于SUMT.X2 使用外罰函數(shù)法和內(nèi)罰函數(shù)法求解（NLP ）時，得到的近似最優(yōu)解往往 不是（NLP ）的可行解.X3 在求解（NLP ）的外罰函數(shù)法中，所解無約束問題的目標(biāo)函數(shù) 為 .4 在（NLP ）中 I =0,則在求解該問題的內(nèi)罰函數(shù)法中，常使用的罰函數(shù) 為5 在（NLP ）中 l = 0，貝 U 在求解該問題的乘子法中，乘子的迭代公式為（k Ji =_，對 i 比，ml6 在（NLP）中 m =1，則在求解該問題的乘子法中，增廣的 Lagrange 函數(shù) 為：_7 對于（NLP）的 KT 條件為：_二、計(jì)算題1利用最優(yōu)性條件(KT 條件)求解約束最優(yōu)化問題.2用外

8、罰函數(shù)法求解約束最優(yōu)化問題.見書本：例 421;例 422.3用內(nèi)罰函數(shù)法求解約束最優(yōu)化問題.見書本：例 423.4用乘子法求解約束最優(yōu)化問題.見書本：例 4.2.7;例 4.2.8.三、簡述題1 簡述 SUMT 外點(diǎn)法的優(yōu)缺點(diǎn).2 簡述 SUMT 內(nèi)點(diǎn)法的優(yōu)缺點(diǎn).四、證明題利用最優(yōu)性條件證明相關(guān)問題.例如：Q設(shè)為正定矩陣，A 為列滿秩矩陣.試求規(guī)劃(P) min f (x) =1x Qx c x a2st.A x二b的最優(yōu)解，并證明解是唯一的.第五章多目標(biāo)最優(yōu)化方法一、判斷與選擇題1 求解多目標(biāo)最優(yōu)化問題的評價函數(shù)法包 括_ .2 通過使用評價函數(shù)，多目標(biāo)最優(yōu)化問題能夠轉(zhuǎn)化為單目標(biāo)最優(yōu)化問題 .V3 設(shè)F:D Rn Rm，則 F 在 D 上的一般多目標(biāo)最優(yōu)化問題的數(shù)學(xué)形式為_.使得F(x)EF(x )且F(x) = F(x )，則x”為該最優(yōu)化問題的有效解.V5一般多目標(biāo)最優(yōu)化問題的絕對最優(yōu)解必是有效解.Vfi(i =1, 2，m)的權(quán)系數(shù)，則求解以上問題的線性加權(quán)和法中所求解優(yōu)化的目標(biāo)函數(shù)為_ .解，或者為原問題的有效解，或者為原問題的弱有效解V對于規(guī)劃V -minF(x) (x).fm(x)T，設(shè)x D,若不存在 X D對于規(guī)劃V- minF(X)=(刈, fm(x)T設(shè)Wi為相應(yīng)于利用求解V -minF(X)=、簡述題1 簡單證明題 絕對最優(yōu)解、有效解、及弱有效解之間