最优化历年考点总结

计算题部分：

最速下降法、Newton法、DFP变尺度法、Rosen投影梯度法（2003） 最速下降法、Newton法、两步法（2004） 最速下降法、Newton法（2005） 最速下降法、Newton法（2007）

给出函数要求选用合适方法求解（2003、2004、2005、2007）

名词解释部分：

最速下降方向、变尺度法、无约束最优化的梯度算法、内部罚函数法（内点罚函数法）、收敛准则、松弛变量、外点罚函数法、 1、最速下降方向：在某一点x,负梯度方向p= –g(x)是使目标函数 f(x)下降最快的方向,称为最速下降方向.

2、收敛准则：由于精确的最优解是永远也不可能达到的。但从工程角度考虑，一个精确度过高的最优解在计量和实施过程中是无法实现和没有必要的。因此最优化计算只要求得到满足一定精度的近似最优解，而非精确最优解。判断迭代点是否达到给定精度要求的判别式称之为最优化算法的收敛准则或终止准则。 点距准则：一般来说，迭代点向极小点的逼近速度是逐渐变慢的，越接近极小点相邻迭代点的距离越小。当相邻迭代点间的距离充分小，并且小于给定的收敛精度??0，即有

Xk?1?Xk??时，便可认为点Xk?1是满足给定收敛精度的最优解。于是可令

X*?Xk?1?6，输出

?4X*和

f(X)*后终止迭代。一般取收敛精度

??10~10.

值差准则:在迭代点向极小点逼近的过程中，不仅相邻迭代点间的距离逐渐缩短，而且它们的函数值也越来越近。因此。可将相邻迭代点的函数值之差作为判断近似最优解的另一个准则，也就是值差准则。即对于充分小的正数?，如果

f(Xk?1)?f(Xk)f(Xk?1)?f(Xk)??令

X*或者

f(Xk)??成立，

?Xk?1，输出X*和

f(X)*后终止迭代。

梯度准则：由极值理论可知，多元函数在某点取得极值的必要条件是函数在改点的梯度等于零。一般情况下，梯度等于零点就是函数的极值点。但在迭代计算中，梯度值不可能绝对等于零，故可以认为，梯度的模小于给定精度的点就是函数的近似最优点。即当

?f(Xk)?gk??时令

X*

?Xk?1，输出X*和

f(X)*后终止迭代。

3、松弛变量：若所研究的线性规划模型的约束条件全是小于类型，那么可以通过标准化过程引入M个非负的松弛变量。松弛变量的引入常常是为了便于在更大的可行域内求解。若为0，则收敛到原有状态，若大于零，则约束松弛。

4、内点罚函数法：它对企图从内部穿越容许集边界的店在目标

函数中加入相应的“障碍”，距边界越近，障碍越大。在边界上给以无穷大的障碍，从而保障迭代点一直在容许集内部移动。 5、外点罚函数法：它对违反约束的点在目标函数中加入相应的“惩罚”，而对容许集内的店不予惩罚。但此法的迭代点一般在容许集外部移动。

6、无约束最优化的梯度方法：利用函数的导数也就是根据目标函数的梯度，有时还要计算Hesse矩阵所提供的信息构造出的算法。包括：最速下降法、Newton法、共轭梯度法和变尺度法。 7、变尺度法：在Newton法的基础上改进而来，避免每次迭代计算目标函数的Hesse矩阵和它的逆矩阵。常用的方法有：DFP算法和BFGS算法。

问答部分：

1、 何？

答：无约束非线性问题的解法可以分为两大类，一类是梯度方法分为：最速下降法、Newton法、共轭方向法、共轭梯度法、变尺度法。另一类是不使用导数的方法称之为直接方法。前者收敛速度快，但需要计算梯度，甚至需要计算Hesse矩阵；后者不涉及导数，适应性强，但收敛速度较慢。 解法快慢大致次序：

最速下降法越接近极小值，步长越小，前进越慢。

Newton法要求计算二阶导数，计算量很大。但是收敛速度很快。

无约束非线性问题解法有哪些？解法快慢的大致次序如

共轭梯度法是介于最速下降和Newton法之间的算法，克服了最速下降法的收敛速度慢的缺点，有避免了Newton法大计算量。 变尺度法计算机量少。

2、 铁路新线纵断面优化设计通常是约束非线性问题，根据其

目标函数、约束条件应如何选定优化方法？

答：铁路部门在进行铁路纵断面设计时，通常采用投影梯度法、简约梯度法和约束变尺度法。 （1） 投影梯度法

根据投影梯度法可知，它对问题的求解是依靠目标函数的负梯度来寻找下降方向，用一维搜索寻找使函数下降最多的最优步长，并保证所有的迭代点在可行域以内，以求得最值。该方法适用于目标函数非线性，约束条件为线性的问题。其优点：计算简单，在优化初始阶段收敛速度快，占用的计算机内存少。它采用数值微分方法计算目标函数的梯度，考虑了目标函数的分段性。不足之处是迭代接近最优解时收敛速度慢，出现“锯齿”现象。 （2） 简约梯度法

该方法的基本思想与线性规划的单纯形法相类似，它将所有变量分为自变量和基本变量两个部分，同时对约束进行处理，将原有