《最优化方法》复习题(含答案)

《最优化方法》复习题(含答案)

附录5 《最优化方法》复习题

1、设A?Rn?n是对称矩阵，b?Rn,c?R，求f(x)?的梯度和Hesse矩阵．

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

2、设?(t)?f(x?td)，其中f:Rn?R二阶可导，x?Rn,d?Rn,t?R，试求???(t)． 解 ??(t)??f(x?td)Td,???(t)?dT?2f(x?td)d． 3、设方向d?Rn是函数f(x)在点x处的下降方向，令

ddT?f(x)?f(x)TH?I?T?， Td?f(x)?f(x)?f(x)1TxAx?bTx?c在任意点x处2其中I为单位矩阵，证明方向p??H?f(x)也是函数f(x)在点x处的下降方向． 证明 由于方向d是函数f(x)在点x处的下降方向，因此?f(x)Td?0，从而

?f(x)Tp???f(x)TH?f(x)

ddT?f(x)?f(x)T???f(x)(I?T?)?f(x)

d?f(x)?f(x)T?f(x)T???f(x)T?f(x)??f(x)Td?0，

所以，方向p是函数f(x)在点x处的下降方向．

4、S?Rn是凸集的充分必要条件是?m?2,?x1,x2,L,xm?S,x1,x2,L,xm的一切凸组合都属于S．

证明 充分性显然．下证必要性．设S是凸集，对m用归纳法证明．当m?2时，由凸集的定义知结论成立，下面考虑m?k?1时的情形．令x???ixi，

i?1k?1其中xi?S,?i?0,i?1,2,L,k?1，且??i?1．不妨设?k?1?1（不然x?xk?1?S，

i?1k?1结论成立），记y???ixi，有x?(1??k?1)y??k?1xk?1，

1??i?1k?1k

k?i?i?0,i?1,2,L,k,??1， 又

1??k?1i?11??k?1则由归纳假设知，y?S，而xk?1?S，且S是凸集，故x?S．

5、设S?Rn为非空开凸集，f:S?R在S上可微，证明：f为S上的凸函数的充要条件是f(x2)?f(x1)??f(x1)T(x2?x1),?x1,x2?S．

证明 必要性．设f是S上的凸函数，则?x1,x2?S及??(0,1)，有

f(?x2?(1??)x1)??f(x2)?(1??)f(x1)，

于是

f(x1??(x2?x1))?f(x1)??f(x2)?f(x1)，

因S为开集，f在S上可微，故令??0?，得

?f(x1)T(x2?x1)?f(x2)?f(x1)，即f(x2)?f(x1)??f(x1)T(x2?x1),?x1,x2?S．

充分性．若有f(x2)?f(x1)??f(x1)T(x2?x1),?x1,x2?S， 则???[0,1]，取x??x1?(1??)x2?S，从而

f(x1)?f(x)??f(x)T(x1?x)，f(x2)?f(x)??f(x)T(x2?x)，

将上述两式分别乘以?和1??后，相加得

?f(x1)?(1??)f(x2)?f(x)??f(x)T(?x1?(1??)x2?x)

?f(x)?f(?x1?(1??)x2)，

所以f为凸函数．

6、证明：凸规划minf(x)的任意局部最优解必是全局最优解．

x?S证明 用反证法．设x?S为凸规划问题minf(x)的局部最优解，即存在x的某

x?S个?邻域N?(x)，使f(x)?f(x),?x?N?(x)IS．若x不是全局最优解，则存在

%%)?f(x)．由于f(x)为S上的凸函数，因此 x?S，使f(x???(0,1)，有

%%f(?x?(1??)x)??f(x)?(1??)f(x)?f(x)．