可行方向法基本算法

(一) 、基本思想是：给定一个可行点)(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仍在可行区内，则把步长再加大一倍继续搜索，如此方法得到新点只要仍在可行区内，则加大步长只到得到的点进入非可行区。