最优化理论、方法及应用试题

一、 （30分）

1、 针对二次函数，其中Q是正定矩阵，试写出最速下降算法的详细步骤，并简要说明其优缺点？

答：求解目标函数的梯度为，，搜索方向：从出发，沿作直线搜索以确定。

Step1: 选定,计算

Step2: 做一维搜索, ,.

Step3：判别，若满足精度要求，则停止；否则，置k=k+1,转步2。

优缺点：最速下降法在初始点收敛快，算法简单，在最优点附近有锯齿现象，收敛速度慢。

2、 有约束优化问题

最优解的必要条件是什么？

答：假设是极小值点。必要条件是f，g，h函数连续可微，而且极小值点的所有起作用约束的梯度和线性无关，则存在使得

3、 什么是起作用约束？什么是可行方向？什么是下降方向？什么是可行下降方向？针对上述有约束优化问题，如果应用可行方向法，其可行的下降方向怎样确定？

答：起作用约束：若，这时点处于该约束条件形成的可行域边界上，它对的摄动起到某种限制作用。

可行方向：是可行点，某方向p，若存在实数，使得它对任意，均有，则称方向p是点的可行方向。

下降方向：某一可行点，对该点的任一方向p来说，若存在实数，使对任意均有，就称方向p为点的一个下降方向。

可行下降方向：既是可行方向，又是下降方向。

可行方向的确定：可行方向法就是沿下降容许方向搜索并保持迭代点为可行点的一种迭代方法。

二、 （25分）

1、 回答出n维空间中非零向量系相互共轭的定义。

答：设Q是n×n对称正定矩阵。若n维空间中非零向量系满足

则称是Q共轭的，或称的方向是Q共轭方向。

2、 应用共轭梯度方法求解无约束优化问题，初始点为。

答： 假设误差范围是。，初始搜索方向

步长：，

第二步迭代：，,

，，

步长：

3、 对于无约束优化问题，写出其下降的牛顿方向，并应用牛顿算法迭代两步，初始点仍取为。

答：，求解方程，，

。

于是。

三、 （20分）

1、 针对有约束优化问题

试构造出两种外部惩罚函数。

答：，其中，。

其它选择

2、 最小二乘问题

用台劳公式进行一阶线性化得，将问题转化为如下的问题

，

其中是函数在处的Jacobi矩阵。证明算法

（1） 当非奇异时，方向P是下降的

（2） 当接近奇异时，方向也是下降的。其中是一个适当的常数。

证明：（1）即证明，，A（x）是f(x)的Jacobi矩阵，，故，。

（2）当接近奇异时，若s是一个适当的常数，则存在，从而，因此方向也是下降的。

四、 （15分）

求解如下的约束优化问题

答：先求满足K-T条件的点，，

，解得：

五、 （10分）

将Zoutendijk可行方向法应用于优化问题，其中中，其中A，b,C,d是响应的矩阵。试给出可行下降方向和最优步长的确定方法。

答：假设x是题中的某个容许点。适当调换A的行向量和b的响应分量，然后分解，相应的分解，使得。则非零向量P为从点x出发的容许方向向量的充要条件是。

由此可得到的有限的最优解，设为P*，P*为点x处的一个下降容许方向向量。

为了确定一个新的迭代点，可以从点x出发沿下降容许方向P*直线搜索，即

最优步长t*的确定

分解成，简化成。

求可行区间：，u，v的维数与相同，，当时，对，总成立。从而成立，此时，当时，为使成立，即成立，只需考虑的不等式

若取，则对，都有成立，从而

。

最优化试题及答案