附录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?1kk?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)．
%%?N?(x)IS，于是f(x)?f(?x?(1??)x当?充分接近1时，可使?x?(1??)x)，
矛盾．从而x是全局最优解．
7、设S?Rn为非空凸集，f:S?R是具有一阶连续偏导数的凸函数，证明：x是问题minf(x)的最优解的充要条件是：?f(x)T(x?x)?0,?x?S．
x?S%证明 必要性．若x为问题minf(x)的最优解．反设存在x?S，使得
x?S%%?f(x)T(x?x)?0，则d?x?x是函数f(x)在点x处的下降方向，这与x为问题
minf(x)的最优解矛盾．故?f(x)T(x?x)?0,?x?S．
x?S%%充分性．若?f(x)T(x?x)?0,?x?S．反设存在x)?f(x)． ?S，使得f(x%f(x??(x?x))?f(x)???%f(?x?(1??)x)?f(x)?
%?f(x)?(1??)f(x)?f(x)%?f(x)?f(x)?0(??(0,1)，
?因S为凸集，f在S上可微，故令??0?，得
%%?f(x)T(x?x)?f(x)?f(x)?0，这与已知条件矛盾，故x是问题minf(x)的最优
x?S解．
8、设函数f(x)具有二阶连续偏导数，xk是f(x)的极小点的第k次近似，利用
f(x)在点xk处的二阶Taylor展开式推导Newton法的迭代公式为 xk?1?xk?[?2f(xk)]?1?f(xk)．
证明 由于f(x)具有二阶连续偏导数，故
1f(x)??(x)?f(xk)??f(xk)T(x?xk)?(x?xk)T?2f(xk)(x?xk)．
2且?2f(xk)是对称矩阵，因此?(x)是二次函数．为求?(x)的极小点，可令
??(x)?0，即?f(xk)??2f(xk)(x?xk)?0，若?2f(xk)正定，则上式解出的?(x)的平稳点就是?(x)的极小点，以它作为f(x)的极小点的第k?1次近似，记为
xk?1，即xk?1?xk?[?2f(xk)]?1?f(xk)，这就得到了Newton法的迭代公式.
9、叙述常用优化算法的迭代公式．
??k?ak?(1??)(bk?ak),（1）0.618法的迭代公式：?
??k?ak??(bk?ak).Fn?k?1???a?(bk?ak),k?kF?n?k?1(k?1,2,L,n?1)． （2）Fibonacci法的迭代公式：?F???a?n?k(b?a)kkkk?Fn?k?1?（3）Newton一维搜索法的迭代公式： tk?1?tk?（4）最速下降法用于问题minf(x)???(tk)． ???(tk)1TxQx?bTx?c的迭代公式： 2?f(xk)T?f(xk)xk?1?xk??f(xk) T?f(xk)Q?f(xk)（5）Newton法的迭代公式：xk?1?xk?[?2f(xk)]?1?f(xk)． （6）共轭方向法用于问题minf(x)?1TxQx?bTx?c的迭代公式： 2?f(xk)Tdkxk?1?xk?dk． TdkQdk10、已知线性规划：
?minf(x)?2x1?x2?x3;?s..t3x1?x2?x3?60,??x1?2x2?2x3?10, ??x1?x2?x3?20,??x1,x2,x3?0.?（1）用单纯形法求解该线性规划问题的最优解和最优值； （2）写出线性规划的对偶问题； （3）求解对偶问题的最优解和最优值．
解 （1）引进变量x4,x5,x6，将给定的线性规划问题化为标准形式：
?minf(x)?2x1?x2?x3;?s..t3x1?x2?x3?x4?60,??x1?2x2?2x3?x5?10, ??x1?x2?x3?x6?20,??x1,x2,L,x6?0.?
x1 x2 x3 x4 x5 x6 x4 3 1 1 1 0 0 60 x5 1 -2 2 0 1 0 10 x6 1 1* -1 0 0 1 20 f -2 1 -1 0 0 0 0 x4 2 0 2 1 0 -1 40 x5 3 0 0 0 1 2 50 x2 1 1 -1 0 0 1 20 f -3 0 0 0 0 -1 -20 所给问题的最优解为x?(0,20,0)T，最优值为f??20． （2）所给问题的对偶问题为：
??maxg(y)??60y1?10y2?20y3;??s..t?3y1?y2?y3?2,??y1?2y2?y3??1, ???y1?2y2?y3?1,??y1,y2,y3?0.（3）将上述问题化成如下等价问题：
??minh(y)?60y1?10y2?20y3;??s..t?3y1?y2?y3?2,??y1?2y2?y3??1, ???y1?2y2?y3?1,??y1,y2,y3?0.引进变量y4,y5,y6，将上述问题化为标准形式：
??minh(y)?60y1?10y2?20y3;??s..t?3y1?y2?y3?y4?2,??y?1?2y2?y3?y5??1, ??y1?2y2?y3?y6?1,??y1,y2,L,y6?0.
1）2）（ （