最優(yōu)化方法(試題+答案)

1、精品文檔填空題21X11.若 f (x)x1X213，則 f (x)12 x2X2f (x).2.設(shè)f連續(xù)可微且f (x)0 ,若向量d滿足，則它是f在x處的一個下降方向。3. 向量(1,2,3)T關(guān)于3階單位方陣的所有線性無關(guān)的共軛向量有 .4. 設(shè)f : RnR二次可微，則f在x處的牛頓方向為 .5. 舉出一個具有二次終止性的無約束二次規(guī)劃算法： .6. 以下約束優(yōu)化問題：min f(x) x-i2s.t. h(x) x2 捲 10g (x)x- X2 0的K-K-T條件為：7. 以下約束優(yōu)化問題:的外點罰函數(shù)為(取罰參數(shù)為、證明題(7分+8分)min f (x)x； x；s.t. xx2

2、1).1. 設(shè) gi : RnR,i 1,2,m1 和 h : RnR,i m11, m都是線性函數(shù)，證明下面的約束問題:nmin f (x)2Xkk 1s.t.gi(x)0,i I 1, mhj(x)0,j E m11,m是凸規(guī)劃問題。2.設(shè) f : R2R連續(xù)可微，ai Rn， hiR，i 1,2, m，考察如下的約束條件問題:min f (x)T ds.t. aiTd 0,i I aiTd 0,i El|d|1的解，求證：d是f在x處的一個可行方向。三、計算題(每小題 12分)設(shè)d是冋題min f(x)st. ax00,iI1,2axbi0,iE m!1, m1.取初始點x(0)(1,1

3、)T.采用精確線性搜索的最速下降法求解下面的無約束優(yōu)化問題(迭代2步)：2 2min f (x)x12x22.采用精確搜索的BFGS算法求解下面的無約束問題:min f (x)x1x23.用有效集法求解下面的二次規(guī)劃冋題：min f (x)x：2x2 2x14X2St.X1X21 0冷0,X20.4.用可行方向算法(Zoutendijk算法或Frank Wolfe算法)求解下面的問題(初值設(shè)為x(0)(0,0),計算到x即可)：1 2min f (x)%22X1X2X22x1s.t. 3x1 x23x10, x20.一、填空題4x1 2x212x1 4x23參考答案2. f(x)Td 0 3.

4、 (2, 1,0)T , (3,0, 1)T (答案不唯一)。4.2f(x) 1 f(X)5. 牛頓法、修正牛頓法等(寫出一個即可)6.12 x10xL(x,)0X2 X；100,X1X20,(X1X2)027. F (x)X12X21(X1 X21)2二、證明題1.證明：要證凸規(guī)劃，即要證明目標(biāo)函數(shù)是凸函數(shù)且可行域是凸集。一方面，由于f二次連續(xù)可微，2 f (x) 2I正定，根據(jù)凸函數(shù)等價條件可知目標(biāo)函數(shù)是凸函數(shù)。另一方面，約束條件均為線性函數(shù)，若任意x, y D可行域，則gi( x (1)y) gi(x) (1 )gi(y)0 i Ihj( x (1)y)hj(x) (1)hj(y)0 i

5、 E2.證明：要證d是f在X處的一個可行方向，即證當(dāng)x D , d Rn 時，0,使得x d D ,(0,當(dāng)i 1時，ax bi0 , ad0,故 a(xd) biaiTx biad 0 ；當(dāng)i E時,aiTx bi0 , aiTd 0，故 aiT(xd) biaiTx baiTd 0.故x (1)y D，從而可行域是凸集。因此，d是f在x處的一個可行方向。二、計算題1.解：()f(xd) (X1dj2 2(X2d2)2令()0得dr X1 2d 2 X22 2d12d2f(x)2x14X2第一次迭代：f(x(0)24，d(0)f(x(0)2，()4(0)f (x() d ):令()0,求得0

6、5/18 ；488第二次迭代：x(1) x(0)(0)d9，f(x )9,d(1)f (x )9122999(1). (1) ()f(xd )，令()0，求得11/2，故x(2) x(1)1d00，由于f(x)0，故x(2)為最優(yōu)解。kx(k)(k) f (x )d(k)k0(1,1)T(2,4)T(2, 4)T5/181(4/9, 1/9)T(8/9, 2/9)T(8/9,2/9)T1/22(0,0)TX1f(x)2x2X2Xi2.解：取 x(0)(1,1)TB0I第一步迭代:f(x(0)0d(0)B01(0) f (x )()f(x(0)d(0)(1)2(求得01/2;第二步迭代:x(1)

7、x(0)0d(0)(1)、 f (x )s(0)x(1)x(0)(0)y()f(x(1)f(x(0)Bi1 0001/213/210 101121 21d(1)Bi1f(x)21，()f(xd)，令()0,求得12。故4x(2)x(1)1d0，由于f(x)0，故x 為最優(yōu)解。00kx(k)r ,(k)、f (x )d(k)k0(1,1)T(0,1)T(0, 1)T1/21(1,1/2)T(1/2,0)T(1/2, 1/4)T22(0,0)T3.解：取初始可行點x(0)(0,0), AoA(x(0) 2,3.求解等式約束子問題2 2min d1 d2 2d1 4d2s.t d10,d20得解和相

8、應(yīng)的Lagrange乘子d(0)(0,0)T,( 2, 4)T故得xx(0)(0,0) T,A A32轉(zhuǎn)入第二次迭代。求解等式約束子問題min di2 d；st di 02di 4d2得解d(1)(0,2)T 0計算min1 bi ai x.T (1)i 1 3 aTd(1) 0 3a1 xi1,3,ai d0T -a d1EE1,T .(1)ai d12x x(1)1d(1)(0,1)T,A2AU1 1,2轉(zhuǎn)入第三次迭代。求解等式約束子問題min d； d； 2d1 2d2s.t d1 d2 0,d1 0得解和相應(yīng)的Lagrange乘子d (0,0) T,(2,0)T由于0，故得所求二次規(guī)劃問題的最優(yōu)解為x(2)(0,1)T，相應(yīng)的Lagrange乘子為(2,0,0)4.解：計算梯度得f(x)(2xi X2 2,2x2 Xi)T當(dāng)k 0時，x(0)(0,0)， f (x) ( 2,0)T.y(0)是下面線性規(guī)劃問題的解：min f (x(0) )y2y1s.t. 3y1y2 3y10, y2 0.解此線性規(guī)劃(作圖法)得y(0)(2/3,0)T，于是d(0) y(0) x(0)(2/3,0)T.由線性搜索(0)(0)2以 4.min f (x td ) t t01 1 、93得t01.因此，x(1)x