第四章 无约束优化方法
——最速下降法，牛顿型方法
概述
在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。
为什么要研究无约束优化问题?
（1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。
二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。
无约束优化问题的一般形式可描述为：
求n维设计变量 X??x1x2?xn??Rn
T使目标函数 f(X)?min
目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 无约束优化问题的求解： 1、解析法
可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程
minf(X*)?0
的解。也就是求Ｘ＊使其满足
?f(X*)?0?x1?f(X*)?0?x2??f(X*)?0?xn解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。
2、数值方法
数值迭代法的基本思想是从一个初始点X(0)?(0)搜索，确定最佳的步长?0使函数值沿d方向下降最大，得到X(1)点。依此一步一步
地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为
?(0)出发，按照一个可行的搜索方向dX(K?1)?X(K)?(K)??Kd(k?0,1,2,?) （4.2）
?(K)在上式中， d是第是 k+1 次搜索或迭代方向，称为搜索方向（迭代方向）。
由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点X(k)、搜
?(k)索方向d和迭代步长?K，称为优化方法迭代算法的三要素。第三章我们已经讨论了
?(k)如何在搜索方向d上确定最优步长?K的方法，本章我们将讨论如何确定搜索方向?(k)d。
最常用的数值方法是搜索方法，其基本思想如下图所示：
无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确定搜索方向的方法，称为间接法，如最速下降法、牛顿法、变尺度法和共轭梯度法。另一类是直接利用目标函数值确定搜索方向的方法，称为直接法，如坐标轮换法、鲍威尔法和单形替换法。各种无约束优化方法的区别在于确定其搜索方向0d的方法不同。
4．1最速下降法
最速下降法是一个求解极值问题的古老算法，1847年由柯西（Cauchy）提出。 4.1.1最速下降法的基本原理
由第二章优化设计的数学基础可知，梯度方向是函数增加最快的方向，负梯度方向是函数下降最快的方向，所以最速下降法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向进行一维搜索，直到满足精度要求为止。因此，最速下降法又称为梯度法。由公式（4.2）
X(K?1)?X(K)?(K)??Kd(k?0,1,2,?)
可知，若某次选代中己取得点X(k)，从该点出发，取负梯度方向
?(k)?f(X(k))d?? (k)?f(X)为搜索方向。则最速下降法的迭代公式为
X(K?1)?X(K)??K?f(X(k))?f(X(k))(k?0,1,2,?) （4.3）
当第ｋ次的迭代初始点X步长?的一维函数。即
(k)?(k)和搜索方向d已经确定的情况下，原目标函数成为关于
?(?)?f(X(K)??S(K))
最优步长?K可以利用一维搜索的方法求得
min?(?)?f(X?(k?1))?f(X(K)?(k)?(k)(K)??kd)?minf(X??d)
?根据一元函数极值的必要条件和多元复合函数的求导公式，得
?(k)T(K)(K)???(?)????f(X??d)??f(X)?0
?(K?1)(K)?)???f(X??f(X)?0
T?(K?1)T?(k)或写成 [d]d?0
由此可知，在最速下降法中相邻两个搜索方向互相正交。也就是说在用最速下降法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前一次搜索方向垂直，形成“之”字形的锯齿现象，如图4.1所示。最速下降法刚开始搜索步长比较大，愈靠近极值点其步长愈小，收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线是较扁的椭圆时，这种缺陷更加明显。因此所谓最速下降是指目标函数在迭代点附近出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目标函数的最快搜索方向。
图4.1最速下降法的搜索路径
此外，最速下降法的迭代公式也可以写成下面的形式
X(K?1)?X(K)??K?f(X(k))(k?0,1,2,?) （4.4）
将其与式4.3相比较，可知，此处?K等于4.3式中步长除以函数在X(K)点导数的模
??f(X(k))，而此时的搜索方向d(k)??f(X(k))也不再是个单位向量。
4.1.2最速下降法的迭代过程
１） 给定初始点X(0)，收敛精度ε，并令计算次数k?0； ２） 计算X(k)点的梯度?f(X(K))及梯度的模?f(X(k))，并令
?(k)?f(X(k))d?? (k)?f(X)３） 判断是否满足精度指标?f(X(k))??；若满足，X(k)为最优点，迭代停止，
输出最优解X*?X(k)和f(X*)?f(X(k))，否则进行下一步计算； ４） 以X即
(k)?(k)为出发点，沿d进行一维搜索，求能使函数值下降最多的步长?K，
minf(X?(k)?(k)?(k)(k)??d)?f(X??Kd)
５） 令X(k?1)?X(k)?(k)??Kd，ｋ＝ｋ＋１，转到步骤2)。
最速下降法的程序框图如图4.2所示。