搜索
2011-2012第一学期期末考试最优化理论与方法试题答案答案：1.非线性规划极值问题的特点：（1）非线性规划的极值有可能在边界上取得，也可能在可行域的任一点处取得。即极值问题可能在可行域内。（2）目标函数如果是凸函数，定义域为凸规划时，它们的任一点局部极值点极为全局极值点。（3）非线性凸规划问题的极值点存在的充要条件是库恩塔克条件（凸函数极值点处的梯度向量为零）。2.凸规划的定义：（1）目标函数为凸函数（2）约束条件图形特征表现为凹函数。凸规划的可行域为凸集，任意一极小点都为全局极小点，且极小点的合集为一凸集。证明：任意一个极小点都为全局极小点。假设X＊为凸规划问题的一个局部极小点，则对于X＊的一个充分小的邻域Ni(X＊)内任一点X（X∈Ni(X＊)）都有f(X)≥f(X＊)。设Y是凸规划可行域上的一个局部极小点，λ为任意小的正数，那么：λ*X＊+(1-λ)*Y∈Ni(X＊),则根据上面的叙述有：f(λ*X＊+(1-λ)*Y)≥f(X＊)。又f(X)为凸函数，根据凸函数的性质有：f(λ*X＊+(1-λ)*Y)≤λ*f(X)+(1-λ)*f(Y)∴f(Y)≥f(X＊),即任意一个极小值点为全局极小点。证明：凸规划极小值点的合集是一个凸集。根据凸函数的性质3，小于某一个熟知的凸函数点的合集为一个凸集，即Sβ={X|f(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（∗），即limk→∞‖X（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，ε5≥0.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))T∙D0∇f(X(0))T∙D0证明：取λ为充分小的正数，则X(0)+λ∙D∈R,且满足gi(X(0)+λ∙D)≥0,对gi（X）在X(0)处进行泰勒展开：gi(X(0)+λ∙D)=gi(X(0))+λ∇gi(X(0))T∙D+o（λ），当λ→0时，有：limλ→0o（λ）λ=0，∵λ0∴当∇gi(X(0))T∙D0时，gi(X(0)+λ∙D)gi(X(0)),D为可行方向。对于目标函数f(X)来说,只要f(X(0)+λ∙D)𝑓(X(0))成立,就能证明D为下降方向，同样对于f(X)在X(0)处泰勒展开，得到：f(X(0)+λ∙D)=f(X(0))+λ∇f(X(0))T∙D+o（λ）,∵limλ→0o（λ）λ=0∴当f(X(0))∙D0时，f(X(0)+λ∙D)𝑓(X(0)),D为可行方向。（2）若X(0)是局部极小点，则不可能找出满足以下条件的的可行方向D来满足：{∇gi(X(0))T∙D0∇f(X(0))T∙D0证明：反证法：假设在点X(0)处存在一个可行方向D同时满足上述条件，则，同（1）所述过程，D为可行下降方向，这与题目条件X(0)是局部极小点相矛盾。所以，D不能同时满足{∇gi(X(0))T∙D0∇f(X(0))T∙D0。6.对于无约束极值问题minλf(X)=12XTAX+BTX+c,式中A为n×n的对称矩阵，X，B∈En,c为常数。设向量P(i),i=0,1,2,…,n-1,为A共轭，则从任一点X(0)出发，相继以P(0),P(1),…,P(n−1)为搜索方向的下述算法：{minλf(X(k)+λP(k))=f(X(k)+λkP(k))X(k+1)=X(k)+λkP(k)经过n次一维搜索收敛于上述无约束极值问题的极小点。解：∇f(X)=AX+B经过n次搜索后，得到的解分别是X_(1)，X(2),…,X(n)∵∇f(X(k))=AX(k)+B;∇f(X(k+1))=AX(k)+B=A(X(k)+λkP(k))+B=∇f(X(k))+λk∙AP(k)∴设∇f(X(k))≠0，对于k=0,1,2,…,n-1,有：∇f(X(n))=∇f(X(n−1))+λn−1∙AP(n−1)=∇f(X(k+1))+λK+1∙AP(K+1)+λK+2∙AP(K+2)+⋯+λn−1∙AP(n−1)在经过一维搜索确定最佳步长λK时，有：df(X(k+1))dλ=df(X(k)+λkP(k))dλ=∇f(X(k+1))T∙P(k)=0因此，对于k=0,1,2,…,n-1时，有：（P(k)）T∇f(X(n))=（P(k)）T∇f(X(k+1))+λK+1（P(k)）T∙AP(K+1)+λK+2（P(k)）T∙AP(K+2)+⋯+λn−1（P(k)）T∙AP(n−1)=0即：∇f(X(n))为n个线性无关的向量P(0),P(1),P(2),…,P(n−1)正交，则只有∇f(X(n))=0，所以，X(n)为无约束相关极值问题的极小点，即经过n次以P(0),P(1),P(2),…,P(n−1)为方向的算法得到的为X(n)极小点。7.用梯度法求f(X)=(X1−1)2+(X2+1)2的极小点，已知ε=0.1解：初始估计X(0)=(0,0)T∵∇f(X)=(2(X1−1)2(X2+1))∴∇f(X)=(−22)根据检验终止准则：‖∇f(X(0))‖2=(−2)2+(2)2=8𝜀=0.1,故需要进行下一次的迭代得到X(1):X(1)=X(0)−λ0∇f(X(0))其中λ0=∇f(X(0))T∇f(X(0))∇f(X(0))TH(X(0))∇f(X(0))∵H(X)=(2002)λ0=(−22)(−22)(−22)(2002)(−22)=12∴X(1)=(00)−12(−22)=(1−1)∇f(X(1))=(00)此时，检验终止准则：‖∇f(X(1))‖2=0𝜀=0.1,迭代终止。又∵f（X）的海塞矩阵H(X)是正定时，f(X)为严格凸函数∴X(1)=是f(x)的全局极小点，且minf(X)=0.8.给出二次规划maxf(X)=6X1+3X2−2X12+4X1X2-4X22{X1+X2≤54X1+X2≤9X1,X2≥0要求：（1）库恩—塔克条件求最优解（2）写出等价的线性规划问题并化为标准形解：标准型：minF(X)=2X12+4X22−4X1X2−6X1−3X2{g1(X)=5−X1−X2≥0g2(X)=9−4X1−X2≥0g3(X)=X1≥0g4(X)=X2≥0注意本题运用库恩-塔克条件解题时应该引入4个拉格朗日乘子。当X1=43,X2=113，r3＊=0,r4＊=0时可以求得最优解，最终最优解为minf(X)=1699。（2）等价的线性规划问题：minf(X)=12(4X+8X−8XX)-6X-3X{5−X1−X2≥09−4X1−X2≥0X1,X2≥0标准型：minφ(Z)=Z1+Z2{y3+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,y4≥0,xjyj=0,j=1,2,3,49.简述把约束极值问题化为无约束极值问题的方法，并且用其中的一种方法求解非线性规划{minf(X)=X12−2X1+2X2+1g1(X)=X1−1≥0g2(X)=X2≥0解：提示，内点法和外点法。答案为Xmin=(10)T.