《最优化方法》复习题

《最优化方法》复习题

一、 简述题

1、怎样判断一个函数是否为凸函数. （例如: 判断函数2122

212151022)(x x x x x x x f +-++=是否为凸函数） 2、写出几种迭代的收敛条件.

3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M 法及二阶段法）.

见书本61页(利用单纯形表求解);

69页例题 (利用大M 法求解、二阶段法求解);

4、简述牛顿法和拟牛顿法的优缺点.

简述共轭梯度法的基本思想.

;

写出Goldstein 、Wolfe 非精确一维线性搜索的公式。

5、叙述常用优化算法的迭代公式．

（1）法的迭代公式：(1)(),().

k k k k k k k k a b a a b a λτμτ=+--??=+-?

（2）Fibonacci 法的迭代公式：111(),(1,2,,1)()n k k k k k n k n k k k k k n k F a b a F k n F a b a F λμ---+--+?=+-??=-??=+-??

．

（3）Newton 一维搜索法的迭代公式： 11k k k k x x G g -+=-． （4）推导最速下降法用于问题1min ()2

T T f x x Gx b x c =++的迭代公式： 1()T k k k k k T k k k

g g x x f x g G gx +=-? （5）Newton 法的迭代公式：211[()]()k k k k x x f x f x -+=-??．

（6）共轭方向法用于问题1min ()2

T T f x x Qx b x c =++的迭代公式： 1()T k k k k k T k k

f x d x x d d Qd +?=-． 、

二、计算题

双折线法练习题 课本135页 例3.9.1

FR 共轭梯度法例题：课本150页 例4.3.5

二次规划有效集：课本213页例6.3.2,

所有留过的课后习题.

三、练习题：

1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2T T f x x Ax b x c =

++在任意点x 处的梯度和Hesse 矩阵．

解 2(),()f x Ax b f x A ?=+?=．

2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+．

（

3、证明：凸规划min ()x S f x ∈的任意局部最优解必是全局最优解．

证明 用反证法．设x S ∈为凸规划问题min ()x S

f x ∈的局部最优解，即存在x 的某个δ邻域()N x δ，使()(),()f x f x x N x S δ≤?∈．若x 不是全局最优解，则存在x S ∈，使()()f x f x <．由于()f x 为S 上的凸函数，因此 (0,1)λ?∈，有

((1))()(1)()()f x x f x f x f x λλλλ+-≤+-<． 当λ充分接近1时，可使(1)()x x N x S δλλ+-∈，于是()((1))f x f x x λλ≤+-，矛盾．从而x 是全局最优解．

4、已知线性规划：123123123123123min ()2;..360,2210,20,,,0.f x x x x s t x x x x x x x x x x x x =-+??++≤??-+≤??+-≤??≥?

（1）用单纯形法求解该线性规划问题；

（2）写出线性规划的对偶问题；

解 （1）引进变量456,,x x x ，将给定的线性规划问题化为标准形式：

123123412351236126min ()2;..360,2210,20,,,,0.f x x x x s t x x x x x x x x x x x x x x x =-+??+++=??-++=??+-+=??≥?

—

所给问题的最优解为(0,20,0)T x =，最优值为20f =-．

（2）所给问题的对偶问题为：

123123123123123max ()601020;..32,21,21,,,0.g y y y y s t y y y y y y y y y y y y =---??---≤??-+-≤-??--+≤??≥?

5、用法求解 2min ()(3)t t ?=-，要求缩短后的区间长度不超过，初始区间取

[0,10]．

解 第一次迭代：

取11[,][0,10],0.2a b ε==．

确定最初试探点11,λμ分别为

11110.382() 3.82a b a λ=+-=，11110.618() 6.18a b a μ=+-=．

求目标函数值：21()(3.823)0.67?λ=-=，21()(6.183)10.11?μ=-=． %

比较目标函数值：11()()?λ?μ<．

比较11 6.1800.2a με-=->=．

第二次迭代：

212121210, 6.18, 3.82,()()0.67a a b μμλ?μ?λ========．

2222220.382()0.382(6.180) 2.36,()(2.363)0.4a b a λ?λ=+-=-==-=． 2222()(), 3.82a ?λ?μμε<-=>．

第三次迭代：

323232320, 3.82, 2.36,()()0.4a a b μμλ?μ?λ========． 2333330.382()0.382(3.820) 1.46,()(1.463) 2.37a b a λ?λ=+-=-==-=． 3333()(), 3.82 1.46b ?λ?μλε>-=->．

、

第四次迭代：

434343431.46, 3.82, 2.36,()()0.4a b b λλμ?λ?μ========． 444440.618() 1.460.0.618(3.82 1.46) 2.918,()0.0067a b a μ?μ=+-=+-==． 4444()(), 3.82 2.36b ?λ?μλε>-=->．

第五次迭代：

545454542.36, 3.82, 2.918,()()0.0067a b b λλμ?λ?μ========． 555550.618() 3.262,()0.0686a b a μ?μ=+-==．

5555()(), 3.262 2.36a ?λ?μμε<-=->．

第六次迭代：

656565652.36, 3.262, 2.918,()()0.0067a a b μμλ?μ?λ========． {

666660.382() 2.7045,()0.087a b a λ?λ=+-==．

6666()(), 3.262 2.7045b ?λ?μλε>-=->．

第七次迭代：

767676762.7045, 3.262, 2.918,()()0.0067a b b λλμ?λ?μ========． 777770.618() 3.049,()0.002a b a μ?μ=+-==．

7777()(),b ?λ?μλε>->．

第八次迭代：

878787872.918, 3.262, 3.049,()()0.002a b b λλμ?λ?μ========．

888880.618() 3.131,()0.017a b a μ?μ=+-==． 8888()(),a ?λ?μμε<->．

{

第九次迭代：

989899982.918, 3.131, 3.049,()()0.002a a b μμλ?μ?λ========． 999990.382() 2.999,()0.000001a b a λ?λ=+-==． 9999()(), 3.049 2.918a ?λ?μμε<-=-<． 故99

3.0242x λμ+==．

6、用最速下降法求解 221122

12min ()2243f x x x x x x x =++--,取(0)(1,1)T x =,迭代两次．

解 1212()(224,243)T f x x x x x ?=+-+-，

将()f x 写成1()2T T f x x Gx b x =

+的形式，则224,243Q b -????== ? ?-????． 第一次迭代：

(0)(0)(1)(0)(0)(0)(0)()()()()()T T f x f x x

x f x f x G f x ??=-??? )

0(0,3)1013220131/4(0,3)243?? ?????????=-= ? ? ??????????? ???????

． 第二次迭代：

(1)(1)(2)(1)

(1)(1)(1)()()()()()T T f x f x x x f x f x G f x ??=-??? 3/2(3/2,0)13/27/40223/21/401/4(3/2,0)240-??- ?-????????=-= ? ? ?-??????????- ???????．

7、用FR 共轭梯度法求解

222123123123min ()()()()f x x x x x x x x x x =-++-++++-，取(0)11(,1,)22

T x =，迭代两次．若给定0.01,ε=判定是否还需进行迭代计算． 解 222123121323()3()2()f x x x x x x x x x x =++-++， 再写成1()2T f x x Gx =，622262226G --?? ?=-- ? ?--??

，()f x Gx ?=． 第一次迭代：

(0)()(0,4,0)T f x ?=，令(0)0()(0,4,0)T d f x =-?=-， 从(0)x 出发，沿0d 进行一维搜索，即求(0)200min ()21648f x d λλλλ≥+=-+的最优解，得

《

(1)(0)0001/6,(1/2,1/3,1/2)T x x d λλ==+=．

第一次迭代：

(1)()(4/3,0,4/3)T f x ?=．2(1)02(0)()

29

()f x f x α?==?， (1)100()(4/3,8/9,4/3)T d f x d α=-?+=---． 从(1)x 出发，沿1d 进行一维搜索，即求

(1)10142362214181418min ()(,,)262233923392261423f x d λλλλλλλλ≥??- ?--?? ? ? ?+=------ ? ? ?-- ??? ?- ???

的最优解，得

(2)(1)1111/24/333,1/38/9(0,0,0)881/24/3T x x d λλ-???? ? ?==+=+-= ? ? ? ?-????．

此时

(2)(2)()(0,0,0),()00.01T f x f x ε?=?=<=．

》 得问题的最优解为(0,0,0)T x =，无需再进行迭代计算．

8、求解问题 （方法不限定）

()22121212121211min 51022

..2330420

,0

f x x x x x s t x x x x x x =+---≤+≤≥取初始点()0,5T .

9、采用精确搜索的BFGS 算法求解下面的无约束问题：

21222121)(min x x x x x f -+=

解：取T x )1,1()0(= I B =0 ???? ??--=?12

212)(x x x x x f

第一步迭代：

???

? ??=?10)()0(x f ???? ??-=?-=-10)()0(10)0(x f B d ，ααααφ+-+=+=2)0()0()1(21

)()(d x f ，令0)('=αφ，求得2/10=α；

第二步迭代：

????? ??=+=211)

0(0)0()1(d x x α，????? ??=?021)()1(x f ，????? ??-=-=210)0()1()0(x x s 、

????

? ??-=?-?=121)()()0()1()0(x f x f y

??

????--=??????--+??????-??????=2112/32112/1100010011B -=)1(d ?????? ??--=?-4121)()1(11x f B ，)()()1()1(d x f ααφ+=，令0)('=αφ，求得21=α。故

???? ??=+=00)1(1)1()2(d x x α，由于???

? ??=?00)()2(x f ，故)2(x 为最优解。 10、用有效集法求解下面的二次规划问题：

.

0,00

1..42)(min 21212

12221≥≥≥+----+=x x x x t s x x x x x f

解：取初始可行点(0)(0)0(0,0),(){2,3}.x A A x ===求解等式约束子问题

221212

12min 24..0,0

d d d d s t d d +--== 得解和相应的Lagrang

e 乘子

(0)(1)(0)10(0,0),(2,4)(0,0),\{3}{2}

T T

T d x x A A λ==--====故得

—

转入第二次迭代。求解等式约束子问题

2212121min 24..0

d d d d s t d +--= 得解 (1)(1)(1)(1)111(1)(1)(0,2)0

1min{1,1,3,0}2

T T T T i i i T T i i d b a x b a x i a d a d a d α=≠--==<==计算

令

(2)(1)(1)121(0,1),{1}{1,2}T x x d A A α=+=== 转入第三次迭代。求解等式约束子问题

221212

121min 22..0,0d d d d s t d d d +--+==

得解和相应的Lagrange 乘子

!

(2)(0,0),(2,0)T T

d λ==

由于(2)0λ≥，故得所求二次规划问题的最优解为

(2)(0,1)T

*==，

x x

相应的Lagrange乘子为

λ*=

(2,0,0)T

最速下降法的优缺点：

优点：方法简单，计算量较小；最速下降法为全局收敛，对初始点的要求很少。

缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最

，

速下降法的最速下降仅是一种局部性质，即从局部来看目标函数的值下降得最快，但从总体来看它可能走了许多弯路。

牛顿法的优缺点：

优点：牛顿法的收敛速度快，为二阶收敛；公式简单，

计算方便。

缺点：牛顿法要求f(x)二阶可微，迭代中需多次计算

；牛顿法具有局部收敛性，对初始点的要求比较苛刻。

共轭梯度法的优缺点：

优点：计算公式简单，存储量较小，对初始点要求很少，对二次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之间，对高维（n 较大）的非线性函数具有较高的效率。对于二次函数具有二次终止性，一般情况下优于共轭梯度法。

缺点：共轭梯度法的收敛性依赖于精确的一维搜索，计算量较大；共轭梯度法的一些理论背景至今尚不清楚，如周期性的重新开始，初始搜索放心的选取，一维搜索的精确性等，对共轭梯度法执行的影响仍有待进一步研究。

拟牛顿法的优缺点：

优点：拟牛顿法具有较快的收敛速度（是超线性的）；

对于二次函数具有二次终止性，一般情况下优于共轭梯度法。

缺点：拟牛顿法需要的存储量较大，对大型计算不便；DFP法远不如BFGS法数值稳定性好，BFGS法具有较强的数值计算稳定性。

本文来源：https://www.bwwdw.com/article/zc7l.html