南京邮电大学2011-12研究生最优化试题标准答案

1一、（3％×8）（1）线性规划0,015322..3min21212121xxxxxxtsxx的对偶规划为自由变量21212121,015332..2-axyyyyyytsyym。（2）在三维空间3R中，集合},1|),,{(222zxyzyxzyx的极点构成的集合为},1|),,{(222zxyzyxzyx。（3）用黄金分割法求解某个函数在区间[-1,3]上的极小点，若要求缩短后的区间的长度不大于原始区间的0.08，则需要迭代的次数为6（4）函数65722),,(32121232221321xxxxaxxxxxxxf为严格凸函数，则常数a的取值范围是22||a（5）在最速下降法，Newton法，FR方法，PRP方法，DFP方法，BFGS方法中不具备二次终止性的算法为最速下降法（6）求函数2221212),(xxxxf的极小点，取Tx)1,0()0(，用最速下降法一步得到的下一迭代点(1)xT)0,0(（7）对于无约束优化问题min212122216432xxxxxx，(1,)Tpa为目标函数在点(0,1)T的下降方向，则a的取值范围是27a（8）用内罚函数法（对数罚函数）求解0x01..min212221xtsxx，其增广目标函数为212221ln)1ln(xrxrxx二、（10％）()fx为凸集nDR上的函数，令(){(,)|,,()}epifxyxDyRyfx，证明()fx为凸函数的充要条件是()epif为凸集。证明：任意取两点)(),(),,(2211fepiyxyx，其中,,21Dxx,,21Ryy,)(11xfy)(22xfy。RD,为凸集，RyyDxx2121)1(,)1(。)(xf为凸函数，212121)1()()1()())1((yyxfxfxxf，,)1((21xx),())1(21fepiyy)(fepi为凸集。（5分）任取,,21Dxx令),(),(2211xfyxfy)(),(),,(2211fepiyxyx。)(fepi为凸集，),)(1(),(2211yxyx,)1((21xx)())1(21fepiyy，)()1()()1())1((212121xfxfyyxxf为凸函数。由凸函数定义知，)(xf（5分）三、（10％）设G为n阶正定对称矩阵，12,,,nnuuuR线性无关。kp按如下方式生成：11pu，1111121(,,,)TkkikkiTiiiuGppupknpGp，证明12,,,nppp关于G共轭。证明：（1）2112121122111()0TTTTTTuGppGppGuppGuuGppGp，因此12,pp关于G共轭。2（4分）（2）设,(1)ijppijk关于G共轭，即0()TjipGpji（2分）下证(1)jpjk与1kp共轭。1111TkTTTkijkjkjiTiiiuGppGppGupGppGp，由于0()TjipGpji，上式等于110TkjTTjkjjTjjuGppGupGppGp。（4分）由归纳法原理，命题成立。四、（20％）（1）用单纯形方法求解下面的线性规划0,024261553..2-min21212121xxxxxxtsxx。（2）若在上面的线性规划中要求变量为整数，在相应的整数规划中，请对变量1x写出对应割平面方程。（3）根据最后得到的单纯形表，求出该线性规划的对偶问题的最优解。解：（1）标准型线性规划为0,,24261553..2-min432142132121xxxxxxxxxxtsxx（2分）单纯型表为Cj-2-100icBBbp1p2p3p40p315351050p412(3)1014-2-1000p330(4)1-13/4-2p1411/301/3120-1/302/3-1p23/4011/4-1/4-2p115/410-1/125/12001/127/12判别数非负，最优解为T)4/3,4/15(，最优值为4/33（8分）（2）根据单纯型表，有415125121431xxx43311251211433xxxx割平面方程为012512114343xx即951143xx（6分）(3)根据最后得到的单纯形表，得到该线性规划的对偶问题的最优解TTTBBCy127,1211353)1,2()(11*注：（1）原理正确，计算错误，若不影响最优基，扣2分，若影响最优基，扣4分（2）割平面方程基本原理4分，（即计算错误扣2分）（3）对偶问题的最优解公式2分，结果2分（没有TBBC)(1可以不扣分但直接写出结果没有过程要酌情扣分）五、（10％）用PRP共轭梯度法求解122212122123minxxxxx，初始点Tx)0,0(0。3解：.0)0,2(.),23()(01221TTgxxxxxg，取T)0,2(-gp00（1）从0x出发，沿0p进行一维搜索，即求46)pf(x)(min2000的极小点，得步长.310于是得到,)0,32(0001TpxxTg)32,0(1.（4分）由PRP公式得,91/)(000110gggggTT故Tpgp)32,92(0011.（3分）(2)从1x出发，沿1p进行一维搜索，即求3294274)pf(x)(min2111的极小点，得.231于是得到,)1,1(1112Tpxx此时Tg)0,0(2.故,)1,1(2*Txx.1*f.（3分）注：方法思路+公式正确，仅计算错误，可给分。六、（10％）用乘子法求解问题03x..22min212221xtsxx解：增广Lagrange函数为,)3(2)3(22221212221xxxxxxM令,0)3(4,0)3(421222111xxxxMxxxxM解得.42321xx（4分）根据乘子迭代公式,2622)3(211kkkxx当0时，迭代收敛，且6*k。（4分）在.42321xx中令6得123/2xx。（2分）七、（10％）讨论Tx)3,0(*是否下面问题的KT点0109xx..min212221221xxtsxx。解：有效集为}1{*I，（2分）TTTxcgxxg)6,0()(,)1,0(,)1,2()(*1*1.易见)(6*1*xcg，（4分）0,06121，所以*x是KT点。（4分）4八、（6％））设**,sz分别是两个线性规划问题（I）0xbx..max1AtsxczT与（II）0xkbx..max2AtsxczT的最优值，*1y是（I）的对偶问题的最优解。求证：kyzsT*1**。证明：（I）与（II）的对偶规划分别为(DI)0ycy..minTTAtsyb与(DII)0ycy..)(minTTAtsykb（2分）（I）的最优值与（DI）的最优值相同，得*1*ybzT，（2分）*1y是（DI）对偶规划的最优解，且（DI）与（DII）约束条件相同，从而*1y是（DII）的可行解。*1y在（DII）的目标函数值不小于最优值，即**1)(sykbT.因此kyzsT*1**。（2分）注：此题别的方法可类似给分。