Zoutendijk 可行方向法

约束优化中的搜索方向必须同时满足两件事：让目标下降，并且小步走后仍可行。Zoutendijk 法把这两件事合成一个方向子问题。

可行方向锥

考虑

\min f(x),\qquad Ax\ge b,\qquad Ex=e.

在可行点 $x$ ，把不等式分为活动组 $A_Ix=b_I$ 与非活动组。非活动约束已有正松弛，小步不会立即违反；活动约束要求

A_Id\ge0.

等式要求

Ed=0.

因此非零 $d$ 是局部可行方向，当且仅当满足这两式。

若 $f$ 可微，

\nabla f(x)^Td<0

保证充分小正步长使目标下降。于是可行下降方向是可行方向锥与开半空间的交集。

为避免任意缩放 $d$ 使内积无限负，加入归一化，例如 $-1\le d_j\le1$ 。方向子问题可写成

\begin{aligned} \min_{d,\eta}\quad &\eta\\ \text{s.t.}\quad &\nabla f(x)^Td\le\eta,\\ &A_Id\ge0,\\ &Ed=0,\\ &-1\le d_j\le1. \end{aligned}

若最优 $\eta^*<0$ ，得到可行下降方向；若 $\eta^*=0$ ，通常说明不存在一阶可行下降方向，当前点满足相应一阶驻点条件。

也常把最大分量范数归一化与目标直接写成 $\min \nabla f(x)^Td$ ，本质相同。

得到方向后，步长必须先保证所有非活动约束也不被穿过。对线性约束，若某行 $a_i^Td<0$ ，最大可行步长为

\bar\alpha_i=\frac{a_i^Tx-b_i}{-a_i^Td}.

取

0\le\alpha\le\min_i\bar\alpha_i

内再做一维搜索。走到新边界后，活动集随之更新。

若方向 LP 的最优值为零，其对偶乘子给出

\nabla f(x)-A_I^T\mu+E^T\lambda=0,\qquad \mu\ge0,

这正是线性约束问题的 KKT 驻点关系。换句话说，不存在可行下降方向与梯度落在法锥中是同一事实的原始/对偶表达。