文档介绍:第五节可行方向法(FDM)
可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法,也 是求解大型约束优化设计问题的主要方法之一。其收敛速度快,效果较好,适用于大中型约 束最优化问题,但程序比较复杂。
可行方向法(Fe第五节可行方向法(FDM)
可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法,也 是求解大型约束优化设计问题的主要方法之一。其收敛速度快,效果较好,适用于大中型约 束最优化问题,但程序比较复杂。
可行方向法(Feasible Direction Method)是一种直接搜索方法,其搜索方向的获取利用了 目标函数和约束函数的梯度信息。用目标函数的梯度可以得到目标函数值的下降方向,而利 用约束函数的梯度则可以得到可行的搜索方向。因此,可行方向法的搜索方向实质上是既使 目标函数值下降,同时又可行的方向,即可行下降方向。满足这一条件的方法就称为可行方 向法。
一、基本原理
当求解目标函数的极小值
min f (X) X e Rn
g (X) < 0 u = 1,2,3 L , m
u
当设计点X (k)处于起作用约束gi 上时,下降可行方向S必须同时满足条件:
StVg (X k ) < 0
i
St Vf ( Xk)<0
由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点
上,因此最优搜索如能沿着约束边界附近进行,就有可能加速最优化搜索的进程。按照这一
基本思路,在任意选定一初始点后到最后得到最优点必须解决三个问题: 一是如何尽快使最优搜索从初始点到达约束边界 二是到达边界后怎样判断所找到的边界点是否是最优点; 三是如果边界点经判断不是最优点,那么下一步应如何进行最优搜索。
二、如何从初始点尽快到达边界
序M3初怡权到达
在任意选定初始点X0之后,首先判断X0是否为 可行点,若是可行点,则选择目标函数的负梯度方向 作为下一步的搜索方向。若是非可行点,则选择目标 函数的梯度方向为搜索方向。
搜索的步长可采用试探的方法逐步缩小,直到最 后到达边界。
如图5-13表示了初始点为可行点时的搜索过程。
从初始点X0出发沿-Vf (X0)方向,取步长为t,
进行搜索,得到X1
X1 = X 0 — tVf (X 0)
若X1仍在可行区内,则把步长加大一倍继续搜索 得到
X 2 = X1 — 2tVf (X1)
若 X 1 仍在可行区内,则把步长再加大一倍继续搜索,如此方法得到新点只要仍在可行 区内,则加大步长只到得到的点进入非可行区。
一旦进入非可行区后,即可改变方向,沿得到点的梯度方向进行搜索,此时步长为原步 长的一半进行搜索。
每次判断得到的点xk是否属于可行区,若是则沿-Vf(Xk),若否,则沿Vf(Xk)方 向搜索,但是步长一直是前一个步长的一半,如此反复,只到收敛到边界上。
收敛到边界点的条件是,只要任一个约束函数为0:
g (Xk) - 0 (i=l,2,・・・..,m)
i
搜索过程中的两条原则:一是搜索方向由迭代点处于可行区还是非可行区而取负梯度方 向或是梯度方向;二是搜索步长在第—次越过约束边界前步长是逐次增加的,而此后不管迭 代点是可行点还是非可行点都是逐次减小的。
这两条原则对于初始点为非可行