2011-2012最优化理论与方法试题答案-李宗平教授出题

2011-2012 第一学期期末考试最优化理论与方法试题答案答案：1.非线性规划极值问题的特点：（1）非线性规划的极值有可能在边界上取得，也可能在可行域的任一点处取得。即极值问题可能在可行域内。（2）目标函数如果是凸函数，定义域为凸规划时，它们的任一点局部极值点极为全局极值点。（3）非线性凸规划问题的极值点存在的充要条件是库恩塔克条件（凸函数极值点处的梯度向量为零）。 2.凸规划的定义：（1）目标函数为凸函数（2）约束条件图形特征表现为凹函数。凸规划的可行域为凸集，任意一极小点都为全局极小点，且极小点的合集为一凸集。证明：任意一个极小点都为全局极小点。假设X为凸规划问题的一个局部极小点，则对于X的一个充分小的邻域Ni(X)内任一点X（XNi(X)）都有f(X)f(X)。设Y是凸规划可行域上的一个局部极小点，为任意小的正数，那么：* X+(1-)*YNi(X),则根据上面的叙述有：f(* X+(1-)*Y) f(X)。又f(X)为凸函数，根据凸函数的性质有：f(* X+(1-)*Y)* f(X)+ (1-) * f(Y) f(Y)f(X),即任意一个极小值点为全局极小点。证明：凸规划极小值点的合集是一个凸集。根据凸函数的性质3，小于某一个熟知的凸函数点的合集为一个凸集，即S=Xf(X)，S为凸集，故凸规划极小点的合集是一个凸集。3.迭代算法：为了求f(X)的最优解，首先给出一个初试估计X（0），如果按照某一算法得到X（1），并使X（1）比X（0）更优（例如：对于最小值问题而言，有f（X（1）f（X（0），再按照该算法得到比X（2）更优的点X（1）,。以此类推，可得到一个解的数列X（k），若数列X（k）末尾有极限X（*），即limkX（k）-X（*）=0,那么一般认为数列X（k）收敛于解X（*）。常用的迭代终止准则：（1）相继两次迭代的绝对误差：X（k+1）-X（k）1；(X（k+1）)-f(X（k）)2.（2）相继两次迭代的相对误差：X(（k+1）)-X(（k）) X（k）3;f(X（k+1）)-f(X（k）)f(X（k）)4.（3）目标函数梯度模的足够小：f(X（k）)5.其中1，2，3，4，50.4.斐波那契算法：一种对称地把区间缩短的方法，它以最少的次数把区间缩短为所要求的长度（斐波那契长度满足Fn=Fn-1+Fn），但每次的缩短率不同。黄金分割法又称0.618法，它是一种等速对称分割法，采用固定的缩短率0.618 和0.382处，同时便于缩短次数进行计算。例如，把区间（b0-a0）经过n次缩短为单位区间，可由(b0-a0)0.618n来确定。区别：黄金分割法是等速分割算法，而斐波那契算法是不等速分割算法。+5.X (0)是函数f(X)定义域的R中的一个可行点，D是函数在点X (0)处的任一可行方向，gi(X)0是该点起作用的的约束，回答下列问题并证明：（1）当D是X (0)处可行的下降方向时，D与f(X (0)和gi(X (0)之间有甚关系？（2）若X (0)是局部极小点，D与f(X (0)和gi(X (0)之间有甚关系？解：（1）D为X (0)处可行的下降方向，有gi(X (0)TD0f(X (0)TD0 当gi(X (0)TD0时， gi(X (0)+D) gi(X (0),D 为可行方向。对于目标函数f(X)来说,只要f(X (0)+D) f(X (0)成立,就能证明D为下降方向，同样对于f(X)在X (0)处泰勒展开，得到：f(X (0)+D)= f(X (0)+ f(X (0)TD+o（）,lim0o（）=0当f(X (0) D0时，f(X (0)+D) 0f(X (0)TD0f(X (0)TD=0.1,故需要进行下一次的迭代得到X(1): X(1)=X(0)-0fX0其中0=fX0TfX0fX0TH(X0)fX0H(X)=2002 0=-22-22-22=12X(1)=00-12-22=1-1 fX1=00此时，检验终止准则：fX12=0=0.1,迭代终止。又f（X）的海塞矩阵H(X)是正定时，f(X)为严格凸函数X(1)=是fx的全局极小点，且min f(X)=0.8.给出二次规划maxf(X)=6X1+3X2-2X12+4X1X2-4X22X1+X254X1+X29X1,X20要求：（1）库恩塔克条件求最优解（2）写出等价的线性规划问题并化为标准形解：标准型：min FX=2X12+4X22-4X1X2-6X1-3X2g1X=5-X1-X20g2X=9-4X1-X20g3X=X10g4X=X20注意本题运用库恩-塔克条件解题时应该引入4个拉格朗日乘子。当X1=43 ,X2=113 ，r3=0,r4=0时可以求得最优解，最终最优解为min f(X)=1699。（2）等价的线性规划问题：min fX=12(4X+8X-8XX)-6X-3X5-X1-X209-4X1-X20X1,X20标准型：min Z=Z1+Z2y3+4y4-y1+4x1-4x2+z1-6=0y3+y4-y2-4x1+8x2+z2-3=05-x1-x2-x3=09-4x1-x2-x4=0x1,x2,x3,x4,y1,y2,y3,y40,xjyj=