当前位置:文档之家› 无约束优化方法(最速下降法-牛顿法)

无约束优化方法(最速下降法-牛顿法)

解(1)计算初始点 处目标函数的梯度和梯度的模
(2)由于 ,不满足精度指标,转下一步计算。
(3)确定搜索方向
(4)计算新的迭代点
由公式(4.2)可得
代入目标函数
沿 方向进行一维搜索(或对 求导,并令其为零)
令 ,,求得最优步长 。
(5)计算新迭代点
(6)计算新迭代点的梯度及梯度的模
因已满足精度要求,停止迭代,得最优解为
4.1最速下降法
最速下降法是一个求解极值问题的古老算法,1847年由柯西(Cauchy)提出。
4.1.1最速下降法的基本原理
由第二章优化设计的数学基础可知,梯度方向是函数增加最快的方向,负梯度方向是函数下降最快的方向,所以最速下降法以负梯度方向为搜索方向,每次迭代都沿着负梯度方向进行一维搜索,直到满足精度要求为止。因此,最速下降法又称为梯度法。由公式(4.2)
一:间接法——要使用导数的无约束优化方法,如直接法——只利用目标函数值的无约束优化问题,如坐标轮换法、鲍威尔法单纯形法等。
无约束优化问题的一般形式可描述为:
求n维设计变量
使目标函数
目前已研究出很多种无约束优化方法,它们的主要不同点在于构造搜索方向上的差别。
图4.1最速下降法的搜索路径
此外,最速下降法的迭代公式也可以写成下面的形式
(4.4)
将其与式4.3相比较,可知,此处 等于4.3式中步长除以函数在 点导数的模 ,而此时的搜索方向 也不再是个单位向量。
4.1.2最速下降法的迭代过程
1)给定初始点 ,收敛精度ε,并令计算次数 ;
2)计算 点的梯度 及梯度的模 ,并令

可见,对于目标函数的等值线为圆的情况,只要一次迭代就能达到极小值点 。这是因为圆周上任意一点的负梯度方向总是指向圆心的,如图4.3所示。
图4.3例题4.1目标函数极小值的搜索过程
通过上面的分析可知最速下降法具有以下特点:
(1)理论明确,程序简单,对初始点要求不严格,每次迭代所需的计算量和存储量也较小,适用于计算机计算。
第四章无约束优化方法
——最速下降法,牛顿型方法
概述
在求解目标函数的极小值的过程中,若对设计变量的取值围不加限制,则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题,多数是有约束的,无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理,转化为无约束最优化问题来求解。
最常用的数值方法是搜索方法,其基本思想如下图所示:
无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确定搜索方向的方法,称为间接法,如最速下降法、牛顿法、变尺度法和共轭梯度法。另一类是直接利用目标函数值确定搜索方向的方法,称为直接法,如坐标轮换法、鲍威尔法和单形替换法。各种无约束优化方法的区别在于确定其搜索方向0d的方法不同。
2、数值方法
数值迭代法的基本思想是从一个初始点 出发,按照一个可行的搜索方向 搜索,确定最佳的步长 使函数值沿 方向下降最大,得到 点。依此一步一步地重复数值计算,最终达到最优点。优化计算所采用的基本迭代公式为
(4.2)
在上式中, 是第是k+1次搜索或迭代方向,称为搜索方向(迭代方向)。
由上面的迭代公式可以看出,采用数值法进行迭代求优时,需要确定初始点 、搜索方向 和迭代步长 ,称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向 上确定最优步长 的方法,本章我们将讨论如何确定搜索方向 。
无约束优化问题的求解:
1、解析法
可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程
的解。也就是求X*使其满足
解上述方程组,求得驻点后,再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有n个未知量,n个方程的方程组,在实际问题中一般是非线性的,很难用解析法求解,要用数值计算的方法。由第二章的讲述我们知道,优化问题的一般解法是数值迭代的方法。因此,与其用数值方法求解非线性方程组,还不如用数值迭代的方法直接求解无约束极值问题。
可知,若某次选代中己取得点 ,从该点出发,取负梯度方向
为搜索方向。则最速下降法的迭代公式为
(4.3)
当第k次的迭代初始点 和搜索方向 已经确定的情况下,原目标函数成为关于步长 的一维函数。即
最优步长 可以利用一维搜索的方法求得
根据一元函数极值的必要条件和多元复合函数的求导公式,得
或写成
由此可知,在最速下降法中相邻两个搜索方向互相正交。也就是说在用最速下降法迭代求优的过程中,走的是一条曲折的路线,该次搜索方向与前一次搜索方向垂直,形成“之”字形的锯齿现象,如图4.1所示。最速下降法刚开始搜索步长比较大,愈靠近极值点其步长愈小,收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线是较扁的椭圆时,这种缺陷更加明显。因此所谓最速下降是指目标函数在迭代点附近出现的局部性质,从迭代过程的全局来看,负梯度方向并非是目标函数的最快搜索方向。
(2)对一般函数而言,最速下降法的收敛速度并不快,因为最速下降方向仅仅是指某点的一个局部性质。
(3)最速下降法相邻两次搜索方向的正交性,决定了迭代全过程的搜索路线呈锯齿状,在远离极小点时逼近速度较快,而在接近极小点时逼近速度较慢。
(4)最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于等值线(面)为同心圆(球)的目标函数,一次搜索即可达到极小点。若目标函数为二次函数,等值线为椭圆,当初始点选在长轴或短轴上时,一次搜索也可达到极小值点。
3)判断是否满足精度指标 ;若满足, 为最优点,迭代停止,输出最优解 和 ,否则进行下一步计算;
4)以 为出发点,沿 进行一维搜索,求能使函数值下降最多的步长 ,即
5)令 ,k=k+1,转到步骤2)。
最速下降法的程序框图如图4.2所示。
4.2最速下降法的程序框图
例题4.1用最速下降法求目标函数 的极小值,设初始点 ,计算精度 。
为什么要研究无约束优化问题?
(1)有些实际问题,其数学模型本身就是一个无约束优化问题。
(2)通过熟悉它的解法可以为研究约束优化问题打下良好的基础。
(3)约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分,也是优化方法的基础。
根据构成搜索方向所使用的信息性质的不同,无约束优化方法可以分为两类。
相关主题