可行方向法基本算法
- 格式:doc
- 大小:133.50 KB
- 文档页数:3
(一) 、基本思想是:给定一个可行点)(k x 之后,用某种方法确定一个改进的可行方向k d ,然后沿方向k d ,求解一个有约束的线搜索问题,得极小点k λ,令k k k k d x x λ+=+)()1(,如果)1(+k x 不是最优解,则重复上述步骤。
可行方向法就是利用线性规划方法来确定k d 的。
1) 、线性约束问题:设x 是问题⎪⎩⎪⎨⎧∈=≤nR f x e Ex b,Ax x s.t.)( min 的一个可行解,假定11b x A =,22b x A <,其中⎥⎦⎤⎢⎣⎡=21A A A ,⎥⎦⎤⎢⎣⎡=21b b b则一个非零向量d 是在点x 点的一个可行方向,当且仅当0d A 1≤,0=Ed ;如果0(T <∇x)d f ,则d 是一改进方向。
2) 、非线性约束问题设x 是问题⎪⎩⎪⎨⎧∈=≤n i R m i f x x x,,2,1 0,)(g s.t.)( min 的一个可行解,令{}0)(,|≤∈=x x x i n g R S ,{}0)(|==x x i g I ,即I 是S ∈x 点紧约束的指标集,设f 和)(I i g i ∈在x 点可微,)(I i g i ∉在x 点连续,如果0(T <∇x)d f ,)(0)(T I i g i ∈≤∇d x ,则d 是一改进的可行方向。
(二) 、算法1) 、线性不等式约束的Zoutendijk 方法的计算步骤:1。
求一初始可行解0x 。
,令k =1,转2。
2.对于可行点k x ,设11k A x b =,22k A x b <,12(,)T T T A A A =, 12(,)T T T b b b =求解问题()11min . 0 011,1,,T j z f x d s t A d P Ed d j n⎧=∇⎪≤⎪⎨=⎪⎪-≤≤=⎩,得最优解k d ,如果()Tk f x d ∇=0,计算结束,k x 是K —T 点;否则转3。
第五节可行方向法(FDM )可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法,也是求解大型约束优化设计问题的主要方法之一。
其收敛速度快,效果较好,适用于大中型约束最优化问题,但程序比较复杂。
可行方向法(Feasible Direction Method)是一种直接搜索方法,其搜索方向的获取利用了目标函数和约束函数的梯度信息。
用目标函数的梯度可以得到目标函数值的下降方向,而利用约束函数的梯度则可以得到可行的搜索方向。
因此,可行方向法的搜索方向实质上是既使目标函数值下降,同时又可行的方向,即可行下降方向。
满足这一条件的方法就称为可行方向法。
一、基本原理当求解目标函数的极小值min f (X) X R ns.t g u(X)M0 u =1,2,3川,m当设计点X(k)处于起作用约束g i 上时,下降可行方向S必须同时满足条件:S“g(X k)乞0S^f (X k) ::0由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点上,因此最优搜索如能沿着约束边界附近进行,就有可能加速最优化搜索的进程。
按照这一基本思路,在任意选定一初始点后到最后得到最优点必须解决三个问题:一是如何尽快使最优搜索从初始点到达约束边界二是到达边界后怎样判断所找到的边界点是否是最优点;三是如果边界点经判断不是最优点,那么下一步应如何进行最优搜索。
二、如何从初始点尽快到达边界在任意选定初始点X0之后,首先判断X0是否为可行点,若是可行点,则选择目标函数的负梯度方向作为下一步的搜索方向。
若是非可行点,则选择目标函数的梯度方向为搜索方向。
搜索的步长可采用试探的方法逐步缩小,直到最后到达边界。
如图5-13表示了初始点为可行点时的搜索过程。
从初始点X0出发沿-\f(X°)方向,取步长为t,进行搜索,得到X1x1=X° -r f (X0)若X1仍在可行区内,则把步长加大一倍继续搜索得到團银门初始負到达边界过理X^X-2t\f(X1 2 3)若X1仍在可行区内,则把步长再加大一倍继续搜索,如此方法得到新点只要仍在可行区内,则加大步长只到得到的点进入非可行区。
可行方向法基本算法
考虑线性规划问题: Min (),{|()0,1,2,...}
{n j f X X R E R X g X j l ∈⊂=≥= 设()k X 是它的一个可行解,但不是要求的极小点,为了求它的极小点或近似极小点,应在()k X 点的可行下降方向中选取某一方向()k D ,并确定步长k λ,使得 (1)()k k k k X X D R λ+=+∈
(1)()()()k k f X f X +<
若满足精度要求,迭代停止,(1)k X +就是所求的点。
否则,从(1)k X +出发继续进行迭代。
直到满足要求为止。
上述这种方法称为可行方向法。
设()k x 点的起作用约束集非空,为求()k x 点的可行下降方向,可由下述不等式组确定响亮D :
()()()0()0,k T k T i f X D g X D j J ⎧⎪⎨⎪⎩
∇<∇>∈ 这等价于由下面的不等式组求向量D 和实数η:
()()k T f X D η∇≤
()(),i k T g X D j J η-∇≤∈
0η<
现使()()k T f X D ∇和()()i k T g X D -∇(对所有j J ∈)的最大值极小化(必须同时
限制向量D 的模),即可将上述选取搜索方向的工作,转换为求解下述线性规划问题:
Min η
()()k T f X D η∇≤
()()(),()k i k T g X D j J X η-∇≤∈
11,1,2,3,..
i d i n -≤≤=
式中(1,2,3,...,)i d i n =为向量D 的分量。
在上式中加入最后一个限制条件,位的是使该线性规划有有限最优解;由于我们的目的在于寻找搜索方向D ,只需知道D 的各分量的相对大小即可。
将上述线性规划的最优解记为()(,)k k D η,如果求出的0k η=,说明在()k X 点不存在可行下降方向,在()()k j g X ∇(此处()()k j J X ∈)线性无关的条件下,()k X 为一K-T 点,若解出0k η<,则得到可行下降方向()k D ,这就是我们所要的所搜方向。
上述可行方向法的迭代步骤如下:
(1)确定允许误差10ε>和20ε>,选取初始近似点(0)X R ∈,并令:0k =。
(2)确定起作用约束指标集()()(){|()0,1}k k j J X j g X j l ==≤≤
①若()()21()||()||k k J X f X ε=∅∅∇≤(为空集),而且,停止迭代,得点()k X 。
②若 ()()21()|()||k k J X f X ε=∅∇>,但,则选搜索方向()()(),k k D f X =-∇然后转向第(5)步。
③若()()k J X ≠∅,转下一步
(3)求解线性规划
M i n η
()()k T f X D η∇≤
()()(),()k i k T g X D j J X η-∇≤∈
11,1,2,3,..
i d i n -≤≤= 设它的最优解为()(,)k k D η。
(4)检验是否满足2||k ηε≤,若满足则停止迭代,得到()k X ;否则,以()k D 为搜索方向,并转向下一步。
(5)解下述一维极值问题()()0:()k k k Min f X D λλ
λλ-≤≤+,此处 ()()max{|()0,1,2,...,}k k j g X D j l λλλ-=+≥=
(6)令 (1)()(
k k k k X X D λ+=+ :1k k =+
转回第(2)步。