线性等式约束问题的投影方法

1 回顾最速下降法

无约束最优化问题:

\[\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ R^n \end{aligned} \]

其中\(f(x)\)是可微的。在\(x =\bar{x}\)处，\(f(x)\)可以通过线性展开逼近

\[f(\bar{x} + d) ≈ f(\bar{x}) + ∇f(\bar{x})^T d \]

为了使d小。这就导致了d的选择，由方向查找问题所决定的:

\[minimize~~~ ∇f(\bar{x})^T d\\ s.t. ~~\|d\| ≤ 1, \]

等于:

\[minimize~~~ ∇f(\bar{x})^T d\\ s.t.~ ~~d^T Id ≤ 1. \]

这个方向查找问题的解决方法为:

\[\bar{d}=\frac{-∇f(\bar{x})}{\|∇f(\bar{x})\|} \]

因为我们选择了下一步

\[x' = \bar{x} + α\bar{d} \]

对于一些步长尺寸\(α\)的选择，那么我们可以简单地将\(\bar{d}\)方向重新缩放为:

\[\bar{d} = −∇f(\bar{x}) \]

也就是说，最速下降法方向就是f(x)在\(x =\bar{x}\)处的梯度的负值。

2 等式限制问题

现在考虑稍微复杂一点的问题

\[\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~x ∈ R^n \end{aligned} \]

其中f(x)是可微的。这个问题的KKT条件如下:

\[A\bar{x}= b \\∇f(\bar{x}) +A^T\bar{π} = 0. \]

我们希望找到KKT点。

假设我们在点\(x =\bar{x}\)，其中\(A\bar{x}= b\)，即\(\bar{x}\)是一个可行点。我们有

\[f(\bar{x} + d) ≈ f(\bar{x}) + ∇f(\bar{x})^T d \]

使d小。为了选择\(\bar{d}\)方向并计算下一个点

\[x' = \bar{x} + α\bar{d} \]

对于某些步长\(α\)，我们将解决以下方向查找问题:

\[\begin{aligned} ~ ~ ~ \min &~ ~ ~ f(\bar{x}) + ∇f(\bar{x})^T (x-\bar{x})\\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~\|x-\bar{x}\|\leq1 \end{aligned} \]

或者相等地设\(d = x-\bar{x}\)

\[\begin{aligned} ~ ~ ~ \min &~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~d^T Id ≤ 1\end{aligned} \]

请注意，\(Ad = 0\)确保\(A(\bar{x} + α{d}) = A\bar{x} = b\),对于任何\(α\)而言。还要注意，约束“\(d^T Id ≤ 1\)”表示\(d\)必须位于欧几里得单位球\(B\)中，定义为:

\[B = \{d ∈ R^n | d^T Id ≤ 1\}. \]

然而，欧几里得球只是一个度规，我们可以更一般化，选择将\(d\)限制在一个椭球内

\[E_Q = \{d ∈ R^n | d^T Qd ≤ 1\}. \]

其中Q是给定的对称正定矩阵。这导致了更普遍的方向查找问题:

\[\begin{aligned} ~ ~ ~ \min &~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T Qd ≤ 1\end{aligned} \]

\(\large\color{#70f3ff}{\boxed{\color{brown}{投影最速下降算法为:} }}\)

• 第一步：\(\bar{x}\)满足\(A\bar{x}= b\)计算\(∇f(\bar{x})\)
• 第二步：解决方向查找问题(DFP):

DFP:

\[\begin{aligned} ~ ~ ~ \bar{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T Qd ≤ 1\end{aligned} \]

若\(∇f(\bar{x})^T d= 0\)，则停止。在这种情况下，\(\bar{x}\)是一个KKT点。

• 第三步：步长\(\bar{α}\)通过精确或不精确的直线搜索获得，求出$\min_\alpha ~f(\bar{x} + α\bar{d}) $。
• 第四步：\(\bar{x} = \bar{x} + \bar{α}\bar{d}\),返回第一步。

注意，如果\(Q = I\)和等式约束\(Ax = b\)不存在，那么这个算法就是最速下降算法。

3投影最速下降方向\(\bar{d}\)的性质

注意，DFP是一个凸程序，\(d = 0\)是Slater点。因此，Karush-Kuhn-Tucker条件是DFP最优性的充分必要条件。这些条件是:

\[\begin{aligned} A\bar{d}=0 \\ \bar{d}^T Q\bar{d} ≤ 1\\ ∇f(\bar{x}) +A^T\bar{π} + 2 \bar{\beta}Q\bar{d} = 0\\ \bar{\beta} \geq0\\ \bar{\beta}(1-\bar{d}^T Q\bar{d})=0 \end{aligned}\tag1 \]

结果是，解这些方程非常容易。(我们将很快看到这个。)让\(\bar{d}\)用乘数$ \bar{\beta},\bar{π}$ 求解(1式。

\(\large\color{magenta}{\boxed{\color{brown}{命题1} }}\)\(\bar{x}\)是P的Karush-Kuhn-Tucker点充分必要条件是\(∇f(\bar{x})^T \bar{d}=0\).

\(\large\color{magenta}{\boxed{\color{brown}{命题2} }}\)\(\bar{x}\)是P的Karush-Kuhn-Tucker点充分必要条件是\(\bar{\beta} =0\).

\(\large\color{magenta}{\boxed{\color{brown}{命题3} }}\)如果\(\bar{x}\)不是P的Karush-Kuhn-Tucker点，那么\(\bar{d}\)就是一个下降方向。

\(\large\color{magenta}{\boxed{\color{brown}{命题4} }}\)投影最速下降算法与最速下降算法具有相同的收敛性质和线性收敛性。在与最速下降算法相同的条件下，迭代收敛到一个Karush-Kuhn-Tucker点，并且收敛速率是线性的，与最速下降算法相同，其收敛常数是根据特征值且有界的。

4 解决方向查找问题(DFP)

\(\large\color{#70f3ff}{\boxed{\color{brown}{DFP的求解方法1:求解线性方程组} }}\)

创建线性方程组:

\[\begin{aligned} Q\widetilde{d} +A^T\widetilde{π} = -∇f(\bar{x}) \\ A\widetilde{d} =0 \\ \end{aligned}\tag2 \]

解决线性方程\((\widetilde{d} ,\widetilde{π})\)通过任何方法处理。

如果\(Q\widetilde{d}=0\),然后

\[A^T\widetilde{π}+∇f(\bar{x}) = 0 \]

所以\(\bar{x}\)是P的Karush-Kuhn-Tucker点。

如果\(Q\widetilde{d}\neq 0\),然后按照如下方法重新调节该方程:

\[\bar{d} = \frac{\widetilde{d}}{\sqrt{\widetilde{d}^T Q\widetilde{d}}} \]

\[\bar{π}=\widetilde{π} \]

\[\bar{\beta} = \frac{1}{2\sqrt{\widetilde{d}^T Q\widetilde{d}}} \]

\(\large\color{magenta}{\boxed{\color{brown}{命题5} }}\)$\bar{d} ,\bar{π},\bar{\beta} $定义如上满足公式（1）。

注意，由于我们使用的是线搜索，所以在实践中重新调节步骤是不必要的。

\(\large\color{#70f3ff}{\boxed{\color{brown}{DFP的求解方法2:公式} }}\)

令

\[P = [Q^{−1} − Q^{−1}A^T (AQ^{−1}A^T )^{−1}AQ^{−1}] \]

\[\bar{\beta} = \frac{\sqrt{(∇f(\bar{x}))^T P(∇f(\bar{x}))}}{2} \]

\[\bar{π}=-(AQ^{−1}A^T )^{−1}AQ^{−1}(∇f(\bar{x})) \]

如果\(\bar{\beta}>0\),让

\[\bar{d} = \frac{-P(∇f(\bar{x}))}{\sqrt{(∇f(\bar{x}))^T P(∇f(\bar{x}))}} \]

如果\(\bar{\beta}=0\),让\(\bar{d}=0\)

\(\large\color{magenta}{\boxed{\color{brown}{命题6} }}\)\(P\)是对称的正半定的。因此\(\bar{\beta}≥0\)

\(\large\color{magenta}{\boxed{\color{brown}{命题7} }}\)$\bar{d} ,\bar{π},\bar{\beta} $定义如上满足公式（1）。

5 牛顿法的修正在线性等式约束

这里我们考虑以下问题:

\[\begin{aligned} (P:) ~ ~ ~ \text{minimize}_x &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~x ∈ R^n \end{aligned} \]

正如在牛顿法的常规版本中，我们用\(f(x)\)在\(x =\bar{x}\)处的二次展开来近似目标。

\[\begin{aligned} (P:) ~ ~ ~ \text{minimize}_x &~ ~ ~ h(x)=f(\bar{x})+∇f(\bar{x})^T(x-\bar{x})+\frac{1}{2}(x-\bar{x})^TH(\bar{x})(x-\bar{x}) \\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~x ∈ R^n \end{aligned} \]

现在我们利用KKT条件来解决这个问题，所以我们求解(x, u)的方程组:

\[Ax = b \\∇h(x) +A^T u = 0 . \]

现在让我们代入这样一个事实:

\[∇h(x)=∇f(\bar{x})+H(\bar{x})(x-\bar{x}),A\bar{x}=b \]

把这个和\(d = x-\bar{x}\)相加，我们就得到了这样一个方程:

\[Ad = 0\\H(\bar{x})d+A^T u = -∇f(\bar{x}) \]

这个方程组的解\((d, u)\)得到\(\bar{x}\)处的牛顿方向d。

注意，这个方程组实际上有一个封闭的解，如果我们想沿着这条路走的话。它是:

\[\begin{aligned} d &= -H(\bar{x})^{−1}∇f(\bar{x}) + H(\bar{x})^{−1}A^T (AH(\bar{x})^{−1}A^T )^{−1}AH(\bar{x})^{−1}∇f(\bar{x})\\ u&=- (AH(\bar{x})^{−1}A^T )^{−1}AH(\bar{x})^{−1}∇f(\bar{x}) \end{aligned} \]

这导致了线性约束问题的牛顿方法的以下版本.

\(\large\color{#70f3ff}{\boxed{\color{brown}{线性约束问题的牛顿法:} }}\)

给定起始点$ x_0\in dom \ f,让Ax^0 = b,k=0 $，容许误差 $\epsilon >0 $,

• 第一步：\(\bar{x}=x^k\),解决\((\bar{d}, \bar{u})\):

• \[A\bar{d} = 0\\H(\bar{x})\bar{d}+A^T \bar{u} = -∇f(\bar{x})\tag3 \]

• ​ 如果\(H(\bar{x})\bar{d}= 0\)，则停止。

• 第二步：选择步长\(α_k = 1\)

• 第三步：迭代： \(x^{k+1} = \bar{x}+ α_k\bar{d}, k = k + 1\). 转到第一步。

请注意以下几点:

如果\(H(\bar{x})\bar{d}= 0\)，那么\(\bar{x}\)是一个KKT点。从步骤1注意，\(∇f(\bar{x})+A^T \bar{u} = 0\)，这就是这个问题的KKT条件。

式(3)称为“正规方程”。它们是在假定\(H(\bar{x})\)是正定的情况下推导出来的，但即使在\(H(\bar{x})\)不是正定的情况下也可以使用。

如果\(H(\bar{x})\)是正定，那么\(\bar{d}\)是一个下降方向。注意，在(3)得到\(∇f(\bar{x})^T\bar{d}=-\bar{d}^TH(\bar{x})\bar{d}<0\)，因为\(H(\bar{x})\)是正定的。

6 变度量法

在投影最速下降算法中，d方向必须在椭球面上

\[E_Q = \{d ∈ R^n | d^T Qd ≤ 1\}. \]

其中\(Q\)对于所有迭代都是固定的。在可变度量方法中，\(Q\)在每次迭代中变化。变度量算法为:

• 第一步：\(\bar{x}\)满足\(A\bar{x}= b\)计算\(∇f(\bar{x})\)
• 第二步：选择一个正定对称矩阵\(Q\)(或许\(Q = Q(\bar{x})\)，即\(Q\)的选择可能取决于当前点)。解决方向查找问题(DFP):

DFP:

\[\begin{aligned} ~ ~ ~ \bar{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T Qd ≤ 1\end{aligned} \]

若\(∇f(\bar{x})^T d= 0\)，则停止。在这种情况下，\(\bar{x}\)是一个KKT点。

• 第三步：步长\(\bar{α}\)通过精确或不精确的直线搜索获得，求出$\min_\alpha ~f(\bar{x} + α\bar{d}) $。
• 第四步：\(\bar{x} = \bar{x} + \bar{α}\bar{d}\),返回第一步。

投影最速下降算法的所有性质在这里仍然成立。

在每次迭代中选择Q的一些策略是:

• \(Q=I\)
• \(Q\)是在所有迭代中保持不变的给定矩阵
• \(Q = H(\bar{x})\)其中\(H(x)\)是\(f(x)\)的Hessian。很容易证明，在这种情况下，变度量算法等价于线搜索的牛顿法，见下面的命题。
• \(Q = H(\bar{x}) + δI\)，在早期迭代中，选择了较大的\(δ\)，但在后期迭代中，选择了较小的\(δ\)。我们可以把这个策略看作是在早期迭代中近似投影下降下降算法，然后在后期迭代中近似牛顿法。

\(\large\color{magenta}{\boxed{\color{brown}{命题8} }}\)假设变度量算法中的\(Q = H(\bar{x})\)。那么变度规法中的方向\(\bar{d}\)是一个正标量乘以牛顿方向。

证明：

\[\begin{aligned} ~ ~ ~ \bar{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T H(\bar{x})d ≤ 1\end{aligned} \]

牛顿方向$\widetilde{d} \(对于P在\)\bar{x}$点是以下问题的解:

NDP:

\[\begin{aligned} ~ ~ ~ \hat{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d+\frac{1}{2}d^TH(\bar{x}){d}\\\text{s.t.} &~ ~ ~ Ad = 0\end{aligned} \]

如果你写下Karush-Kuhn-Tucker条件这两个问题,然后可以很容易地验证\(\bar{d}=\gamma \hat{d}\)。