可行方向法（Feasible Direction Methods）是一类保持迭代点可行性的约束优化算法。每步迭代在当前可行点处寻找一个既使目标函数下降又保持可行性的方向。本章介绍Zoutendijk可行方向法和投影梯度法。

定义 10.1（可行方向）

设 $\mathbf{x} \in \mathcal{F}$，非零向量 $\mathbf{d}$ 称为在 $\mathbf{x}$ 处的可行方向，如果存在 $\bar{\delta} > 0$ 使得： $$\mathbf{x} + \delta \mathbf{d} \in \mathcal{F}, \quad \forall \delta \in [0, \bar{\delta}]$$

定义 10.2（下降可行方向）

若 $\mathbf{d}$ 是可行方向且满足 $\nabla f(\mathbf{x})^T \mathbf{d} < 0$，则称 $\mathbf{d}$ 为下降可行方向。

考虑问题： $$\min f(\mathbf{x}) \quad \text{s.t.} \quad A\mathbf{x} \leq \mathbf{b}$$

在可行点 $\mathbf{x}_k$ 处，定义起作用约束指标集： $$\mathcal{A}_k = \{i \mid \mathbf{a}_i^T \mathbf{x}_k = b_i\}$$

求解线性规划： $$\begin{aligned} \min_{\mathbf{d}, \xi} \quad & \nabla f(\mathbf{x}_k)^T \mathbf{d}
\text{s.t.} \quad & \mathbf{a}_i^T \mathbf{d} \leq 0, \quad i \in \mathcal{A}_k
& -1 \leq d_j \leq 1, \quad j = 1, \ldots, n \end{aligned}$$

或等价地： $$\begin{aligned} \min_{\mathbf{d}, \xi} \quad & \xi
\text{s.t.} \quad & \nabla f(\mathbf{x}_k)^T \mathbf{d} \leq \xi
& \mathbf{a}_i^T \mathbf{d} \leq 0, \quad i \in \mathcal{A}_k
& -1 \leq d_j \leq 1 \end{aligned}$$

算法 10.1（Zoutendijk可行方向法）

1. 选择可行初始点 $\mathbf{x}_0$
2. **for** $k = 0, 1, 2, \ldots$ **do**
   - 确定 $\mathcal{A}_k$
   - 求解方向寻找子问题得 $(\mathbf{d}_k, \xi_k)$
   - **if** $\xi_k = 0$ **then** **break**（达到KKT点）
   - 线搜索求 $\alpha_k$ 使 $f(\mathbf{x}_k + \alpha_k \mathbf{d}_k)$ 最小且保持可行
   - $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
3. **return** $\mathbf{x}_k$

定义 10.3（投影矩阵）

设 $A$ 是 $m \times n$ 矩阵，行满秩。到 $A$ 的零空间的投影矩阵为： $$P = I - A^T(AA^T)^{-1}A$$

性质：$PA^T = \mathbf{0}$，$P^2 = P$，$P^T = P$

搜索方向：$\mathbf{d}_k = -P_k \nabla f(\mathbf{x}_k)$

其中 $P_k$ 是到起作用约束梯度张成空间正交补的投影矩阵。

算法 10.2（投影梯度法）

1. 选择可行初始点 $\mathbf{x}_0$
2. **for** $k = 0, 1, 2, \ldots$ **do**
   - 确定 $\mathcal{A}_k$
   - 构造投影矩阵 $P_k$
   - $\mathbf{d}_k = -P_k \nabla f(\mathbf{x}_k)$
   - **if** $\|\mathbf{d}_k\| > 0$ **then**
     - 线搜索求 $\alpha_k$
     - $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
   - **else**
     - 计算乘子 $\boldsymbol{\mu} = (A_k A_k^T)^{-1} A_k \nabla f(\mathbf{x}_k)$
     - **if** $\boldsymbol{\mu} \geq \mathbf{0}$ **then** **break**
     - **else** 从 $\mathcal{A}_k$ 中移除负乘子对应的约束
3. **return** $\mathbf{x}_k$

定理 10.1

设 $f$ 连续可微，水平集有界。若算法产生的方向满足某种正则性条件，则： 1. 算法有限步终止于KKT点，或 2. 产生无穷序列收敛到KKT点

理论题

1. 证明投影矩阵 $P = I - A^T(AA^T)^{-1}A$ 满足 $P^2 = P$ 和 $P^T = P$。

2. 解释为什么当 $\mathbf{d}_k = -P_k \nabla f(\mathbf{x}_k) = \mathbf{0}$ 时需要检查乘子的符号。

计算题

3. 用Zoutendijk法求解：

 $$\min (x-2)^2 + (y-1)^2 \quad \text{s.t.} \quad x + y \leq 1, \quad x \geq 0, \quad y \geq 0$$

4. 对于问题：

 $$\min x^2 + 2y^2 \quad \text{s.t.} \quad x + y = 1$$
 在点 $(1, 0)$ 处计算投影梯度方向。

—

*本章完*