1、附录 5 最优化方法复习题1、设 是对称矩阵， ，求 在任意点nAR,nbRc1()2TfxAbxc处的梯度和 Hesse 矩阵x解 2(),()fxfA2、设 ，其中 二阶可导， ，试求ttd:nR,nxRdt()解 2(),()()TTtfxttdfxt 3、设方向 是函数 在点 处的下降方向，令ndRfx，()TTfxHIdf其中 为单位矩阵，证明方向 也是函数 在点 处的下降方I ()p()fx向证明 由于方向 是函数 在点 处的下降方向，因此 ，从而d()fx()0Tfd()()TTfxpHf()()TTdxffI fxf()()Tfxf，0Td所以，方向 是函数 在点 处的下降方向
2、p()fx4、 是凸集的充分必要条件是 的一切nSR1212,mmxSx 凸组合都属于 证明 充分性显然下证必要性设 是凸集，对 用归纳法证明当 时，S由凸集的定义知结论成立，下面考虑 时的情形令 ，1mk1kix其中 ，且 不妨设 （不然,0,12,iixSk 1ki1k，结论成立） ，记 ，有 ，1k1kiiiyx11()kkyx又 ，110,2,ki iiki 则由归纳假设知， ，而 ，且 是凸集，故 ySkxSxS5、设 为非空开凸集， 在 上可微，证明： 为 上的凸函数nRSRf: f的充要条件是 211212()(),Tfxfxx证明 必要性设 是 上的凸函数，则 及 ，有SS(0
3、,1)，212()()fxfxfx于是 ，12121()fxf因 为开集， 在 上可微，故令 ，得SfS0，即 12121()()Tfxxf211212()(),TfxffxxS充分性若有 ，2,Tf S则 ，取 ，从而0,12()xxS， ，11()Tfff22()()Tffxfx将上述两式分别乘以 和 后，相加得1212()()()()Tfxfxffx，1所以 为凸函数f6、证明：凸规划 的任意局部最优解必是全局最优解min()xSf证明 用反证法设 为凸规划问题 的局部最优解，即存在 的某min()xSf x个 邻域 ，使 若 不是全局最优解，则存在()Nx(),ffxN，使 由于 为
4、上的凸函数，因此xS()fx()fxS，有0,1(1)()1()fxfxfx当 充分接近 1 时，可使 ，于是 ，(NS(1)fx矛盾从而 是全局最优解x7、设 为非空凸集， 是具有一阶连续偏导数的凸函数，证明：nRSRSf:是问题 的最优解的充要条件是： xmi()xf ()0,TfxxS证明 必要性若 为问题 的最优解反设存在 ，使得in()xSf，则 是函数 在点 处的下降方向，这与 为问题()0Tfxdxx的最优解矛盾故 inxS()0,TfS充分性若 反设存在 ，使得 (),TfxxSx()fx()(1)()fff，()10,1f fx因 为凸集， 在 上可微，故令 ，得SfS0，这
5、与已知条件矛盾，故 是问题 的最()()Tfxxf xmin()xSf优解8、设函数 具有二阶连续偏导数， 是 的极小点的第 次近似，利用()fxkx()fk在点 处的二阶 Taylor 展开式推导 Newton 法的迭代公式为()fk211()()k kxfxf证明 由于 具有二阶连续偏导数，故21()()()()()TTkkkkkkfxfxfxxfx且 是对称矩阵，因此 是二次函数为求 的极小点，可令2k，即 ，若 正定，则上式解出的()0x2()()0kkkfxfx2()kfx的平稳点就是 的极小点，以它作为 的极小点的第 次近似，()x()x()fx1k记为 ，即 ，这就得到了 New
6、ton 法的迭代公式.1k211)()kkkff9、叙述常用优化算法的迭代公式（1）0.618 法的迭代公式： (),.kkaba（2）Fibonacci 法的迭代公式： 11(),(12,)nkkkkkknFnaba（3）Newton 一维搜索法的迭代公式： ()kktt（4）最速下降法用于问题 的迭代公式：1min()2TfxQbxc1()()kkk kTfff（5）Newton 法的迭代公式： 211()kkkxfxf（6）共轭方向法用于问题 的迭代公式：min()TfQbc1)kk kTfxdx10、已知线性规划： 123123123in();60,.fxxxs.t（1）用单纯形法求解
7、该线性规划问题的最优解和最优值；（2）写出线性规划的对偶问题；（3）求解对偶问题的最优解和最优值解 （1）引进变量 ，将给定的线性规划问题化为标准形式：456,x12312345612min();. 0,.fxxstx 12x34x56x4x3 1 1 1 0 0 6051 -2 2 0 1 0 1061 1* -1 0 0 1 20f-2 1 -1 0 0 0 04x2 0 2 1 0 -1 4053 0 0 0 1 2 5021 1 -1 0 0 1 20f-3 0 0 0 0 -1 -20所给问题的最优解为 ，最优值为 (,)Tx2f（2）所给问题的对偶问题为：123123123ma()
8、600;.,0.gyysty（1）（3）将上述问题化成如下等价问题： 12323123min()600;.,0.hyysty引进变量 ，将上述问题化为标准形式：456,1232341562min()00;. ,0.hyysty（2） 1y23y45y64-3 -1 -1 1 0 0 25-1 2 -1* 0 1 0 -16y-1 -2 1 0 0 1 1h-60 -10 -20 0 0 0 04-2 -3 0 1 -1 0 33y1 -2 1 0 1 0 16-2 0 0 0 1 1 0h-40 -50 0 0 -20 0 20问题（2）的最优解为 ，最优值为 （最小值） (,1)Ty2h问题
9、（1）的最优解为 ，最优值为 （最大值） g11、用 0.618 法求解 ，要求缩短后的区间长度不超过 0.2，2min()3t初始区间取 0,1解 第一次迭代：取 1,.2ab确定最初试探点 分别为1,， 10.38()3.8a110.68()6.8aba求目标函数值： ， 21(.).72.310.比较目标函数值： 11()比较 16.80.2a第二次迭代：21212121,.,3.8,()0.67b20.38()0(6.6,(3).4aa222(),.第三次迭代：323232320,.8,.6,()0.4ab23.()0(14(163).7a33(),.第四次迭代：434343431.6
10、,.82,.6,()0.4ab0()160.821.98,().67a 444(),.第五次迭代：545454542.36,.82,.918,()0.67ab01()36()06a555(),.第六次迭代：656565652.3,3.2,2.918,()0.67ab08()704()07a666(),.第七次迭代：767676762.045,3.2,2.918,()0.7ab7770.618()3.049,()0.2aba(),第八次迭代：878787872.91,3.26,3.049,()0.2ab06()1()1a888(),第九次迭代：98989982.1,3.1,3.04,()0.2a
11、b03()2()1a999(),.04.8故 .2x12、用最速下降法求解 ，取 ，22112min()43fxxx(0)1,T迭代两次解 ，1212()4,3)Tfxx将 写成 的形式，则 fTfQb24,3Qb第一次迭代： (0)(0)(1)(0) (0)Tfxfxfx(,3)1201/4,4第二次迭代： (1)(1)(2)(1) (1)TfxfxfxQ3/2(/,0)1/7/4/40132,413、用 FR 共轭梯度法求解 ，取 ，迭222131313min()()()fxxxx(0),1)2Tx代两次若给定 判定是否还需进行迭代计算0.,解 ，22131232()()fxxx再写成 ，
12、 ， ()TfG6()fxG第一次迭代：，令 ，(0),4)Tfx(0)0,4)Tdfx从 出发，沿 进行一维搜索，即求 的最优()0 (0 2min21648fxd解，得(1)(0)0/6,(1/2,3/)Txd第一次迭代： ，(1)4/3,0)Tfx2(1)009fx(1)10(4/3,8/)Tdfd从 出发，沿 进行一维搜索，即求()x1(1)0 1423648148min(,)2239391423fxd 的最优解，得(2)(1)1/24/33, 89(0,)8/Txd此时(2) (2)0,)0.1Tfxfx得问题的最优解为 ，无需再进行迭代计算,14、用坐标轮换法求解 ，取 ，迭代21
13、12min()4fxx(0)1,Tx一步解 从点 出发，沿 进行一维搜索，(0)1,Tx1(,0)Te即求 的最优解，得()20min43fe(1)(0)01,(,)Txe再从点 出发，沿 进行一维搜索，(1)x2,Te即求 的最优解，得()0in7f(2)(1)12/,(3,/)Txe15、用 Powell 法求解 ，取 ，初始搜索112minfx(0),Tx方向组 ，给定允许误差 （迭代两次） 01(,)(,0)TTd.解 第一次迭代：令 ，从点 出发沿 进行一维搜索，易得(0)(),Tyx(0)y0d；(1)()0,(,)T接着从点 出发沿 进行一维搜索，得(1)y1d(2)()133,(,)2T由此有加速方向 ()(0)2y因为 ，所以要确定调整方向23/d由于 ，按（8.4.17）式有(0)(1)(2)9,0,4fyffy
