《最優(yōu)化方法》復習題(含答案)

1、 / 712345678910111213141516天津大學最優(yōu)化方法復習題(含答案)第一章 概述(包括凸規(guī)劃)判斷與填空題arg max f(x)= arg min _f (x).，max If (x): x D 二 Rn 二-min If (x): x D 二 Rn設(shè) f : D J Rn t R.若 x*w Rn,對于一切 xw Rn 恒有 f (x*) f(x)，則稱 x* 為最優(yōu)化問題mmf (x)的全局最優(yōu)解設(shè)f : D三Rn T R.若x D ,存在x*的某鄰域Nc(x*),使得對一切x w n jx)恒有f(x) f (x),則稱x”為最優(yōu)化問題 min f (x)的嚴格局部

2、最 x. D優(yōu)解. TOC o 1-5 h z 給定一個最優(yōu)化問題，那么它的最優(yōu)值是一個定值.V非空集合D Rn為凸集當且僅當 D中任意兩點連線段上任一點屬于D . V非空集合D Rn為凸集當且僅當 D中任意有限個點的凸組合仍屬于D . V任意兩個凸集的并集為凸集.函數(shù)f : D三Rn t R為凸集D上的凸函數(shù)當且僅當-f為D上的凹函數(shù).設(shè)f : D三Rn t R為凸集D上的可微凸函數(shù)，x*w D .則對Vx= D ,有f (x) - f(x ) t f (x )T(x -x ).若c(x)是凹函數(shù)，則D=xWRnc(x)20是凸集。f(x)的算法A產(chǎn)生的迭代序列，假設(shè)算法A為下降算法,則對

3、Vkw&,1,2，恒有 f(xk書)n, b e Rm 為給定的數(shù)據(jù)，且 rank A = m, m bTy . V6設(shè)Xo是線性規(guī)劃(LP)對應的基B = (P1,，Pm)的基可行解，與基變量Xi,，xm對應的規(guī)范式中，若存在Ok M0,則線性規(guī)劃(LP)沒有最優(yōu)解。X7求解線性規(guī)劃（LP）的初始基可行解的方法：.8對于線性規(guī)劃（LP）,每次迭代都會使目標函數(shù)值下降.X二、簡述題1將以下線性規(guī)劃問題化為標準型：max f（x） = x1 -2x2 3x3s.t. xi x2 x3 三 6,x1 2x2 4x3 , 12,xi - x2 , x3 一2,x2 _ 0, x3 - 0.2寫出以下

4、線性規(guī)劃的對偶線性規(guī)劃：max f （x） = 3x1 2x2 x3 4x4s.t. 2x1 4x2 3x3 x4 =6,-2xi 4x2 3x3 x4 - 3,x1，x2, x3, x4 -0.三、計算題熟練掌握利用單純形表求解線性規(guī)劃問題的方法（包括大M法及二階段法）.見書本：例2.5.1 （利用單純形表求解）;例2.6.1（利用大M法求解）；例2.6.2 （利用二階段法求解）.四、證明題熟練掌握對偶理論（弱對偶理論、強對偶理論以及互補松弛條件）及利用 對偶理論證明相關(guān)結(jié)論。第三章無約束最優(yōu)化方法一、判斷與選擇題1設(shè)G WRnn為正定矩陣，則關(guān)于G共腕的任意n + 1向量必線性相關(guān).V2在

5、牛頓法中，每次的迭彳t方向都是下降方向.X3經(jīng)典Newton法在相繼兩次迭代中的迭代方向是正交的.乂4 PRP共腕梯度法與BFGS算法都屬于Broyden族擬Newton算法.乂5用DFP算法求解正定二次函數(shù)的無約束極小化問題，則算法中產(chǎn)生的迭 代方向一定線性無關(guān).V6 FR共腕梯度法、PRP共腕梯度法、DFP算法、及BFGS算法均具有二次收斂性.X7共腕梯度法、共腕方向法、DFP算法以及BFGS算法都具有二次終止性.V8 函數(shù)f : Rn t R在xk處的最速下降方向為 .9求解min f(x)的經(jīng)典Newton法在xk處的迭代方向為pk =.X R”10若f(x)在x*的鄰域內(nèi)具有一階連續(xù)

6、的偏導數(shù)且 Vf(x*) = 0,則x*為的局 部極小點.X11若f (x)在x*的某鄰域內(nèi)具有二階連續(xù)的偏導數(shù)且x*為f(x)的嚴格局部極小點，則G =V2f (x )正定.X12求解min f(x)的最速下降法在xk處的迭代方向為pk=.xRU13求解min f (x)的阻尼Newton法在xk處的迭代方向為pk =. x zR14用牛頓法求解 mjn (xTGx + bTx (bWRn, GRn時，至多迭代一次可達其極小點.X15牛頓法具有二階收斂性.V16二次函數(shù)的共腕方向法具有二次終止性.X17共腕梯度法的迭代方向為： .證明題1設(shè)f : Rn t R為一階連續(xù)可微的凸函數(shù)，x*w

7、Rn且*(x沖)=0 ,則x”為mRnf (x)的全局極小點.2給定b亡Rn和正定矩陣G w Rn41 .如果xk亡Rn為求解min f(x) = ；xTGx+bTx的迭代點，dkWRn始為其迭代方向，且%0, +8)為由精確一維搜索所的步長，則“k- 2(xk)Tdk(dk)TGdk3試證：Newton法求解正定二次函數(shù)時至多一次迭代可達其極小點四、簡述題1簡述牛頓法或者阻尼牛頓法的優(yōu)缺點2簡述共腕梯度法的基本思想.五、計算題1利用最優(yōu)性條件求解無約束最優(yōu)化問題.3 21 2例如：求斛 min f(x)=萬-x2 -x1x2 -2x12用FR共腕梯度法無約束最優(yōu)化問題.見書本：例3.4.1.

8、3用PRP共腕梯度法無約束最優(yōu)化問題.見書本：例3.4.1.3 919例如：min f (x) =- x1 +-x2 -x1x2 -2x1 其中x0 = (0,0),名=0.01第四章 約束最優(yōu)化方法考慮約束最優(yōu)化問題：(NLP)min f (x)st. G(x)=0, i E1,2, ,l；q (x) _ 0, i I -l 1, l 2, , m；其中，f,Ci(i =1,2, ,m): Rn R.-、判斷與選擇題1外罰函數(shù)法、內(nèi)罰函數(shù)法、及乘子法均屬于SUMT. X2使用外罰函數(shù)法和內(nèi)罰函數(shù)法求解(NLP)時，得到的近似最優(yōu)解往往 不是(NLP)的可行解.X3在求解(NLP)的外罰函數(shù)法

9、中，所解無約束問題的目標函數(shù) 為.4在(NLP)中l(wèi) =0,則在求解該問題的內(nèi)罰函數(shù)法中，常使用的罰函數(shù) 為.5在(NLP)中l(wèi) = 0,則在求解該問題的乘子法中，乘子的迭代公式為(九k由)i =,對i亡%,，m).6 在(NLP)中m=l,則在求解該問題的乘子法中，增廣的 Lagrange函數(shù) 為:7對于(NLP)的KT條件為：二、計算題利用最優(yōu)性條件(KT條件)求解約束最優(yōu)化問題.用外罰函數(shù)法求解約束最優(yōu)化問題.見書本：例4.2.1;例 4.2.2.用內(nèi)罰函數(shù)法求解約束最優(yōu)化問題.見書本：例4.2.3.用乘子法求解約束最優(yōu)化問題.見書本：例4.2.7;例 4.2.8.三、簡述題簡述SUMT

10、外點法的優(yōu)缺點.簡述SUMT內(nèi)點法的優(yōu)缺點.四、證明題利用最優(yōu)性條件證明相關(guān)問題.例如：Q設(shè)為正定矩陣，A為列滿秩矩陣.試求規(guī)劃(P)min f (x) = 1 x Qx c x a2st.A x = b的最優(yōu)解，并證明解是唯一的.第五章多目標最優(yōu)化方法一、判斷與選擇題1求解多目標最優(yōu)化問題的評價函數(shù)法包 括.2通過使用評價函數(shù)，多目標最優(yōu)化問題能夠轉(zhuǎn)化為單目標最優(yōu)化問題.，設(shè)F:D JRnT Rm,則F在D上的一般多目標最優(yōu)化問題的數(shù)學形式為.對于規(guī)劃 V -mjn F (x) =(f1(x)，fm(x)T ,設(shè) xl* W D ,若不存在 xW D使得F(x)WF(x*)且F(x)#F(x,則x沖為該最優(yōu)化問題的有效解.V一股多目標最優(yōu)化問題的絕對最優(yōu)解必是有效解. V對于規(guī)劃V -mjn F(x) =(f1 (x)，fm(x)T ,設(shè)Wi為相應于fi (i =1, 2，m)的權(quán)系數(shù)，則求解以上問題的線性加權(quán)和法中所求解優(yōu)化的目標函數(shù)為.7利用求解V -min F(x) =(fi(x)，fm(x)T的線性加權(quán)和法所得到的 x-D Rn解，或者為原問題的有效解，或者為