2011-2012 第一学期期末考试
最优化理论与方法试题答案
答案：
1.非线性规划极值问题的特点：（1）非线性规划的极值有可能在边界上取得，也可能在可行域的任一点处取得。即极值问题可能在可行域内。（2）目标函数如果是凸函数，定义域为凸规划时，它们的任一点局部极值点极为全局极值点。（3）非线性凸规划问题的极值点存在的充要条件是库恩塔克条件（凸函数极值点处的梯度向量为零）。 2.凸规划的定义：（1）目标函数为凸函数（2）约束条件图形特征表现为凹函数。凸规划的可行域为凸集，任意一极小点都为全局极小点，且极小点的合集为一凸集。 证明：任意一个极小点都为全局极小点。
＊
假设X为凸规划问题的一个局部极小点，
则对于X的一个充分小的邻域Ni(X)内任一点X（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β= ，Sβ为凸集，故凸规划极小点的合集是一个凸集。
3.迭代算法：为了求f(X)的最优解，首先给出一个初试估计 （ ），如果按照某一算法得到 （ ），并使 （ ）比 （ ）更优（例如：对于最小值问题而言，有f（ （ ）） f（ （ ））），再按照该算法得到比 （ ）更优的点 （ ）,…。以此类推，可得到一个解的数列 （ ） ，若数列 （ ） 末尾有极限 （ ），即 （ ） （ ） ,那么一般认为数列 （ ） 收敛于解 （ ）。 常用的迭代终止准则：
（1）相继两次迭代的绝对误差： （ ） （ ） ε ； （ ） （ ） ε . （2）相继两次迭代的相对误差： （ ） （ ）
（ ）
＊
＊
＊
ε ;
（ ） （ ）
（ ）
ε
.
（3）目标函数梯度模的足够小： （ ） ε . 其中ε ，ε ，ε ，ε
，ε
0.
4.斐波那契算法：一种对称地把区间缩短的方法，它以最少的次数把区间缩短为所要求的长度（斐波那契长度满足 ），但每次的缩短率不同。
黄金分割法又称0.618法，它是一种等速对称分割法，采用固定的缩短率0.618 和0.382处，同时便于缩短次数进行计算。例如，把区间（ ）经过n次缩短为单位区间，可
由 来确定。
区别：黄金分割法是等速分割算法，而斐波那契算法是不等速分割算法。+
5. 是函数f(X)定义域的R中的一个可行点，D是函数在点 处的任一可行方向， 是该点起作用的的约束，回答下列问题并证明：
（1）当D是 处可行的下降方向时，D与 和 之间有甚关系？ （2）若 是局部极小点，D与 和 之间有甚关系？ 解：（1）D为
处可行的下降方向，有
证明：取 为充分小的正数，则 +λ R,且满足 ( λ ) ,对 （X）在 处进行泰勒展开： ( λ )= ( )+ λ D+ （ ）， 当λ 0时，有：
（ ）
=0， λ 当 D 时， ( λ )
( ),D 为可行方向。
对于目标函数f(X)来说,只要f( λ ) 成立,就能证明D为下降方向，同样对于f(X)在 处泰勒展开，得到：
( λ )= ( )+ λ D+ （ ）,
（ ）
=0 当 ( ) D 0时， ( λ ) ( ),D为可行方向。
（2）若 是局部极小点，则不可能找出满足以下条件的的可行方向D来满足：
证明：反证法：假设在点 处存在一个可行方向D同时满足上述条件，则，同（1）所述过程，D为可行下降方向，这与题目条件 是局部极小点相矛盾。所以，D不能同时满足 。
6.对于无约束极值问题 = X+c,式中A为n 的对称矩阵，X，B ,c 为
常数。设向量 ,i=0,1,2,…,n-1,为A共轭，则从任一点 出发，相继以 λ λ
为搜索方向的下述算法：
λ 经过n次一维搜索收敛于上述无约束极值问题的极小点。 解： f(X)=AX+B
经过n次搜索后，得到的解分别是 ，
,…,
f( )= A +B ; f( )= A +B=A( λ )+B= f( )+ λ 设 f( ) ，对于k=0,1,2,…,n-1,有： f( )= f( )+ λλ
= f( )+ λ
λ
在经过一维搜索确定最佳步长λ
λ
时，有：
=
= =0
因此，对于k=0,1,2,…,n-1时，有：
（ ） f( )= （ ） f( )+ λ λ
（ ） =0
（ ） λ
（ ）
即： f( )为n个线性无关的向量 正交，则只有 f( )=0，所以，
为无约束相关极值问题的极小点，即经过n次以 为方向的算法得到的为 极小点。
7.用梯度法求f(X)= 的极小点，已知 =0.1 解：初始估计 =
∵
∴ =
根据检验终止准则： = + 故需要进行下一次的迭代得到
λ
其中λ
∵H(X)= λ==
∴ = =
此时，检验终止准则： =0 迭代终止。 又∵f（X）的海塞矩阵H(X)是正定时，f(X)为严格凸函数 ∴ =是 的全局极小点，且
8.给出二次规划 -4
要求：（1）库恩—塔克条件求最优解（2）写出等价的线性规划问题并化为标准形
解：标准型：
注意本题运用库恩-塔克条件解题时应该引入4个拉格朗日乘子。 当 = , = ， =0, =0时可以求得最优解， 最终最优解为 =
＊
＊
。
（2）等价的线性规划问题： ( )-6X-3X
标准型：
9.简述把约束极值问题化为无约束极值问题的方法，并且用其中的一种方法求解非线性规划
解：提示，内点法和外点法。 答案为Xmin= .
相关推荐：
loading