最优化方法知识题一

* *

习题一

一、考虑二次函数f(x)=xxxxxx2122212132

1) 写出它的矩阵—向量形式: f(x)=xQxbxTT21

2) 矩阵Q是不是奇异的?

3) 证明: f(x)是正定的

4) f(x)是凸的吗?

5) 写出f(x)在点x=)1,2(T处的支撑超平面(即切平面)方程

解:1) f(x)= xxxxxx2122212132

=xx21216222xx21+11Txx21

其中 x=xx21 ,Q=6222 , b=11

2) 因为Q=6222 ,所以 |Q|=6222=8>0 即可知Q是非奇异的

3) 因为|2|>0, 6222=8>0 ,所以Q是正定的,故f(x)是正定的

4) 因为)(2xf=6222,所以|)(2xf|=8>0,故推出)(2xf是正定的,即

)(2xf是凸的

5) 因为)(xf =1)x6x1,2-x2x(22121T,所以)(xf=(5,11)

所以 f(x)在点x处的切线方程为5(21x)+11(12x)=0

二、 求下列函数的梯度问题和Hesse矩阵

1) f(x)=2x12+xxxxx23923121+xxx2322

2) f(x)=ln(x12+xxx2221) * *

解: 1) )(xf= (,94321xxx 26321xxx, xx219)

)(2xf=019161914

2) )(xf=(xxxxxx112221221 , xxxxxx112221221)

)(2xf=)()()()(2221212222212142221214222121222222121222212122221212212122xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

三、设f(x)=xxxxxxx323223322122,取点)1,1,1()1(Tx.验证d)1(=(1,0,-1)是f(x)在点x)1(处的一个下降方向,并计算0mintf(x)1(+td)1()

证明: )(xf=)124,123,x 2(233221xxxxT

)5,4,2()(1Txf

d)(1xf=(1,0,-1)542= -3<0

所以d)1(是f(x)在x)1(处的一个下降方向

f(x)1(+td)1()=f((1+t,1,1-t))

=433)1(1)1(221(222)1()1tttttt

f(x)1(+td)1()=6t-3=0 所以t=0.5>0

所以0mintf(x)1(+td)1()=3*0.25-3*0.5+4=3.25

四、设aj ，b ，cj（j=1,2,….,n）考虑问题 * *

Min f(x)=njjjxc1

s.t. bnjjjxa1

0xj (j=1,2,….,n)

1) 写出其Kuhn Tuker 条件

2) 证明问题最优值是])([12112njjjbca

解：1）因),....,1(njxj 为目标函数的分母故0xj

所以j（j=1,…,n）都为0

所以Kuhn Tuker 条件为 0)()(xhxf

即

xcxcxcnn2222211+aaan21=0

2）将acxjjj代入 h(x)=0 只有一点

得 njjjnjjjbncabca122)(1

故有accaxjjnjjjjb1

所以最优解是])([12112njjjbca

五、使用Kuhn Tuker 条件，求问题 * *

min f(x)=)2()1(2122xx

s.t.

0,021212112xxxxxx

的Kuhn Tuker 点，并验证此点为问题的最优解

解：x=(1/2,3/2) 0 故1，2=0

则 0)()()(2211xxxfhh

即0111142222121xx

1,021

而 2002)(2xf 故08)(2xxfxT

即其为最优解

六、在习题五的条件下证明

L(,,x)),,(),,(xLLx

其中 L（x,,）=f(x)+)2()1(2112xxxx

证明：L(,,x)=f(x)+)2()1(2112xxxx

= f(x)

= f(x)+)1(12xx+xx21(2)= ),,(xL

= f(x)

)2()1()()(2112xxxxxfxf= ,,(xL)

* *

习题二

一、设f(x)为定义在区间[a,b]上的实值函数，x是问题min{f(x)|abx}的最优解。证明：f(x)是[a,b]上的单谷函数的充要条件是对任意xxxxba2121],,[,

满足f(xx21)1()

证明：不妨设x1

“必要性” 若xxx21)1(

则由单谷函数定义知)())1((121xxxff

故有)}(),(max{))1((2121xxxxfff

“充分性” 由x1，x2的任意性取x1=x时，f(x2)>f(x1)

则x2>xx21)1(>x1=x 且f(xx21)1()

若取 x2=x时, f(x1)>f(x2)

x=x1

满足单谷函数的定义

二、设x1

1)证明:满足条件

)()(),()(),()(221111xxxxxxfff的二次函数)(x是（严格）凸函数

2）证明：由二次插值所得f(x)的近似极小值点（即)(x的驻点）是

)()()()(122122xxxxxxfffx

或者

)()()()(121121xxxxxxfffx

证明：1）设)(x=cbxax2 （0a）

则 baxx2)(

由)(2)()(2)(222111xxxxxxfbafba

得)())()(()(,0)(2)()(1212111212xxxxxxxxxxfffbffa

或 )())()(()(121222xxxxxxfffb

故1）得证

2）)(x的驻点为)()()()(2121121xxxxxxfffabx

或xx2)()()()(12212xxxxxfff

三、设f(x)=0,21QcxQxQbxTTT试证：共轭梯度法的线性搜索中)()()()()()(0mindtxdxkkkkktftf，有dddgtkTkTkkQk)()()()(，其中* *

)()(xgkkf

证明：由已知 ，得bQxxf)(

令)(t)()()(dxkktf为t的凸二次函数。要使tk是)(t的极小点即为驻点，故满足0)(tk

而)(tk)()()(dxkktfdk)(

= dbdtxQkTkk)(])([)()(

=ddtQbxQkTkk)(][)()(

=dddgkTkTkQkt)())((）（

故有 0)(()()ddtdgkTkkTkQk）（

得

dddgtkTkTkkQk)()()()(

四、用共轭梯度法求解：

min f(x)=xxxxx121222122123 , xR2

取初始点)4,2()1(Tx

解：易知

1113A 02b

第一次迭代：

),23(1221)(xxxxTxf )6,12()(11Txgf

)6,12()()1()1(Txdf

线性搜索得步长 * *

1756121113)6,12(612)6,12()1()1()1(11)(dddgATT

从而 dxx)1(1)1()2(=3826171

第二次迭代：

)1712,176()()2(Txf g2)1712,176(T

12981)1()1()1(2)(dddgAATT

28921028990)1(12)2(dgd

线性搜索得步长： 7.12

11)2(2)2()3(dxx

)0,0()()3(3Txgf

所以 最优解为)1,1(*Tx

五、用拟Newton法求解：

min Rxxxxxxxf21212221,422)(

取初始点 )1,1()1(Tx

解：1）DFC法

取初始对称矩阵

10011H