第四章 约束非线性规划 § 4.3 可行方向法
作者：黄希勇 2013.5.28
引入：
对于非线性规划问题，如果不存在约束，从任一个初始点 )0(x 出发，沿)(x f 的负梯度方向进行一维收索，便可求得目标函数的无约束极小值；而对有约束的极小化问题来说，除要使目标函数在每次迭代有所下降之外，还要注意解的可行性问题，为此，在求解约束非线性规划迭代法的设计中，应在每个迭代点)(k x 出构造一个可行下降方向 )(k d 。

引入：有效约束和可行下降方向的概念 考虑非线性规划
⎪⎩
⎪⎨⎧=≥==m i x g l
j x h t
s x f i j .....2,10)(......2,10)(.)
(min （4.3.1）
其中，)(),(),(x g x h x f i j 均为实值连续函数，且具有二阶连续偏导数。

设)0(x 是非线性规划的一个可行解。

现考虑某一不等式约束条件
0)(≥x g i
满足它有两种可能：其一为0)(>x g i ，这时，点)0(x 不是处于由这一约束条件形成的可行域边界上，因而这一约束对)0(x 点的微小摄动不起限制作用，从而称这个约束条件是)0(x 点的不起作用约束(或无效约束)；其二是0)(=x g i ，这时)0(x 点处于该约束条件形成的可行域边界上，
它对)0(x 的摄动起到了某种限制作用，故称这个约束是点的起作用约束(有效约束)。

显而易见，等式约束对所有可行点来说都是起作用约束。

1.1
D e f ： 设可行域是非空集，D x ∈，若对某非零向量n R d ∈，存在0>δ，使对任意),0(δ∈t 均有D td x ∈+,则称d 为从x 出发的可行方向。

若非线性规划的某一可行点)0(x ，对该点的任一方向d 来说，若存在实数't ，使对任意
]',0[t t ∈均有
)()()0()0(x f td x f <+ 就称方向d 为)0(x 点的一个下降方向。

如果方向d 既是)0(x 点的可行方向，又是这个点的下降方向，就称它是该点的可行下降方向。

Eg 4.4: 略
现考虑非线性规划（4.3.1）式，设)(k x 是它的一个可行解，但不是要求的极小点。

为了求它的极小点或近似极小点，根据以前所说，应在)(k x 点的可行下降方向中选取某一方向)(k d ，并确定步长k t ，使
⎩⎨⎧<+=++)
()()
()1()
()()1(k k k k k k x f x f d t x x （4.3.2） 若满足精度要求，迭代停止，)1(+k x 就是所要的点。

否则，从)1(+k x 出发继续进行迭代，直到满足要求为止。

上述方法称为可行方向法； 其特点是：迭代过程中采用的搜索方向为可行方向，所产生的迭代
点列｛X(k)｝始终在可行域内，目标函数值单调下降。

下面介绍Zoutendijk 可行方向法
简 介
● Zoutendijk 可行方向法是Zoutendijk 于1960年提出的. ● Zoutendijk 可行方向法中选择搜索方向包括:起作用（有效）约束构造可行方向和ε起作用约束构造可行方向.
● Zoutendijk 可行方向法可以求解线性约束优化问题和非线性约束优化问题.
考虑线性约束问题
⎪⎩
⎪
⎨⎧
=≥c
Gx b Ax t
s x f .)(min （4.3.3）
其中)(x f 可微，n R x n l G n m A ∈⨯⨯矩阵，为矩阵，为，
维列向量和分别为和l m c b
怎样选择下降可行方向？
由于问题（4.3.3）中约束是线性的，)(x f 是非线性的，在)(k x 附近考察)(x f ，
我们用)(x f 在)(k x 处的一阶Taylor 多项式代替)(x f 。

设)(k x 满足c Gx b x A b x A k k k ==>)
(2)(21)(1,,，其中⎥⎦
⎤⎢⎣⎡=21A A A ,⎥⎦⎤⎢⎣⎡=21b b b ，令
d x f x f x f d x x T k k k )()()(,)()()(∇+≈+=，
于是（4.3.3）转化为下述线性规划：
⎪⎪⎩
⎪⎪⎨
⎧=+≥+≥+∇+c
d x G b d x A b d x A t
s d x f x f k k k T k k )()()(.)()(min )(2)(21
)(1)()(
由于)()(k x f 为常数且1)(1b x A k >，故上述线性规划等价于
⎪⎩
⎪
⎨⎧=≥∇00.)(min 2)(Gd d A t
s d x f T k （4.3.4） 因为0=d 为（4.3.4）的可行点，其对应的目标函数值为0，即*d 为（4.3.4）的最优解，则0)(*)(≤∇d x f T k ：
（1）若0)(*)(<∇d x f T k ，*d 为原问题（4.3.3）在)(k x 处的下降可行方向；
（2）若0)(*)(=∇d x f T k ，)(k x 为（4.3.3）的T K -点； 证明（2）：见课本P79 现在来确定一维搜索的步长？
设)(k x 是（4.3.3）的可行解，不妨设第k 次迭代的出发点)(k d 为)
(k x 处一个下降可行方向后继点)1(+k x 由下列迭代公式给出：
)()()1(k k k k d t x x +=+ 为确定k t ，k t 取值遵循下列原则：
（1）保持迭代)()(k k k d t x +的可行性； （2）使目标函数值尽可能减小；
根据上述原则,可以通过求解下列一维搜索问题来确定步长，这里不再赘述，我们只要知道怎么计算就可以了。

综上得Zoutendijk 可行方向法的步骤为：
（1）确定允许误差ε，任选可行点)0(x 作初始点，令0=k ； （2）根据)(k x 的有效约束把A 分解为2,1A A ,相应的把b 分解为21,b b ，使得2)(21)(1,b x A b x A k k >>； （3）求解线性规划
⎪⎩
⎪
⎨⎧=≥∇00.)(min 2)(Gd d A t
s d x f T k ,11≤≤-i d n i ,.......
2,1= 设最优解为*d ，式中i d 为向量d 的分量，限制i d 是为使该线性规划有有限最优解；
（4）若ε<∇*)()(d x f T k ，则)(k x 为所求最优点，停止，否则转（5）； （5）若0*1≥d A ，则由一维线收索)(min *)(td x f k +得*)()1(d t x x k k k +=+，令1+=k k 转（2），否则转（6）； （6）设*21)(1,d A v b x A u k =-=，计算
⎭
⎬⎫
⎩⎨⎧<-=-
0|min i i i v v u t
由)(min *)(0td x f k t
t +-
≤≤确定*)()1(d t x x k k k +=+，令1+=k k 转（2）；
例：见课本P80。