带等式约束的 Newton 方法

本节描述 Newton 方法向等式约束问题的扩展。该方法与无约束的 Newton 方法几乎相同，只有两点差别：初始点必须是可行的（即 $x\in \mathrm{dom}f$ 且 $Ax=b$），并且 Newton 步的定义需要考虑等式约束。特别地，我们保证 Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 是一个可行方向​（feasible direction），即 $A\mathrm{\Delta }{x}_{\mathrm{nt}}=0$。

Newton 步

通过二阶近似定义

为在可行点 $x$ 处导出等式约束问题

$$\mathrm{minimize}f(x)\mathrm{subject}\mathrm{to}Ax=b$$

的 Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$，用目标函数在 $x$ 附近的二阶 Taylor 近似代替目标函数，得到问题

$$\mathrm{minimize}\hat{f}(x+v)=f(x)+\mathrm{\nabla }f(x{)}^{\mathrm{\top }}v+(1/2)v^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)v\mathrm{subject}\mathrm{to}A(x+v)=b$$

这是一个（凸的）等式约束二次极小化问题，可以解析求解。假设相应的 KKT 矩阵非奇异，我们定义该问题的解为 Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$。换言之，Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 是把目标函数换成二次近似后，为解出问题所需要加到 $x$ 上的一步。

由等式约束二次问题的分析可知，Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 由如下条件刻画：

$$\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }{x}_{\mathrm{nt}}\\ w\end{array}\right]=\left[\begin{array}{c}-\mathrm{\nabla }f(x)\\ 0\end{array}\right]$$

其中 $w$ 是该二次问题相应的最优对偶变量。与无约束情形一样，当 $f$ 恰为二次函数时，Newton 更新 $x+\mathrm{\Delta }{x}_{\mathrm{nt}}$ 精确解出等式约束极小化问题，且 $w$ 就是原问题的最优对偶变量。这提示我们：当 $f$ 接近二次函数时，$x+\mathrm{\Delta }{x}_{\mathrm{nt}}$ 应当是解 $x^{\star }$ 的很好估计，$w$ 应当是最优对偶变量 ${\nu }^{\star }$ 的很好估计。

线性化最优性条件的解

Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 与向量 $w$ 也可以解释为最优性条件

$$A{x}^{\star }=b,\mathrm{\nabla }f(x^{\star })+A^{\mathrm{\top }}{\nu }^{\star }=0$$

的线性化近似的解。将 $x+\mathrm{\Delta }{x}_{\mathrm{nt}}$ 代入 $x^{\star }$、$w$ 代入 ${\nu }^{\star }$，并把第二式中的梯度项换成在 $x$ 附近的线性近似，得到

$$A(x+\mathrm{\Delta }{x}_{\mathrm{nt}})=b,\mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}}+A^{\mathrm{\top }}w=0$$

利用 $Ax=b$，两式化为 $A\mathrm{\Delta }{x}_{\mathrm{nt}}=0$ 与 ${\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}}+A^{\mathrm{\top }}w=-\mathrm{\nabla }f(x)$，这正是定义 Newton 步的那组方程。

Newton 减量

等式约束问题的 Newton 减量​（Newton decrement）定义为

$$\lambda (x)={(\mathrm{\Delta }{x}_{\mathrm{nt}}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}})}^{1/2}$$

这与无约束情形的表达式完全一样，各种解释也仍然成立。例如，$\lambda (x)$ 是 Newton 步在 Hessian 所确定的范数下的范数。设 $\hat{f}$ 为二阶 Taylor 近似，则

$$f(x)-inf\{\hat{f}(x+v)\mid A(x+v)=b\}=\lambda (x{)}^2/2$$

与无约束情形完全一样：$\lambda (x{)}^2/2$ 给出了基于 $x$ 处二次模型的 $f(x)-p^{\star }$ 的估计，而且 $\lambda (x)$（或 $\lambda (x{)}^2$ 的某个倍数）可以作为一个好的终止准则的基础。

Newton 减量同样出现在直线搜索中，因为 $f$ 沿 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 方向的方向导数为

$${\frac{d}{dt}f(x+t\mathrm{\Delta }{x}_{\mathrm{nt}})|}_{t=0}=\mathrm{\nabla }f(x{)}^{\mathrm{\top }}\mathrm{\Delta }{x}_{\mathrm{nt}}=-\lambda (x{)}^2$$

可行下降方向

设 $Ax=b$。若 $v\in {\mathbf{R}}^n$ 满足 $Av=0$，则称 $v$ 为可行方向——此时形如 $x+tv$ 的点都可行。若对小的 $t>0$ 有 $f(x+tv)<f(x)$，则称 $v$ 为 $f$ 在 $x$ 处的下降方向​。

Newton 步总是一个可行下降方向（除非 $x$ 已最优，此时 $\mathrm{\Delta }{x}_{\mathrm{nt}}=0$）：定义 Newton 步的第二组方程 $A\mathrm{\Delta }{x}_{\mathrm{nt}}=0$ 表明它是可行方向，而方向导数 $\mathrm{\nabla }f(x{)}^{\mathrm{\top }}\mathrm{\Delta }{x}_{\mathrm{nt}}=-\lambda (x{)}^2$ 表明它是下降方向。

仿射不变性

与无约束情形一样，等式约束问题的 Newton 步与 Newton 减量都是仿射不变的。设 $T\in {\mathbf{R}}^{n\times n}$ 非奇异，$\overline{f}(y)=f(Ty)$，约束 $Ax=b$ 变为 $ATy=b$。对问题 $\mathrm{minimize}\overline{f}(y)\mathrm{s}.\mathrm{t}.ATy=b$ 写出其 Newton 步方程并与 $x=Ty$ 处的 Newton 步方程比较，可得

$$T\mathrm{\Delta }{y}_{\mathrm{nt}}=\mathrm{\Delta }{x}_{\mathrm{nt}}(\text{且 }w=\overline{w})$$

即 $y$ 与 $x$ 处的 Newton 步通过同一坐标变换相联系。

带等式约束的 Newton 方法

算法 10.1（等式约束极小化的 Newton 方法） 给定初始点 $x\in \mathrm{dom}f$ 且 $Ax=b$，容许误差 $ϵ>0$。

1. 计算 Newton 步与减量 $\mathrm{\Delta }{x}_{\mathrm{nt}}$，$\lambda (x)$。
2. 终止准则​：若 ${\lambda }^2/2⩽ϵ$ 则退出。
3. 直线搜索​：用回溯直线搜索选取步长 $t$。
4. 更新：$x:=x+t\mathrm{\Delta }{x}_{\mathrm{nt}}$。

该方法是一种可行下降方法​（feasible descent method）：所有迭代点都可行，且 $f(x^{(k+1)})<f(x^{(k)})$（除非 $x^{(k)}$ 已最优）。Newton 方法要求 KKT 矩阵在每个迭代点处可逆。

Newton 方法与消去法

可以证明：对等式约束问题应用带等式约束的 Newton 方法，其迭代点与应用 Newton 方法求解约简问题 $\mathrm{minimize}\tilde{f}(z)=f(Fz+\hat{x})$ 所得的迭代点完全一致（其中 $F$ 满足 $\mathcal{R}(F)=\mathcal{N}(A)$、$\mathrm{rank}F=n-p$，$\hat{x}$ 满足 $A\hat{x}=b$）。

约简目标函数的梯度与 Hessian 为

$$\mathrm{\nabla }\tilde{f}(z)=F^{\mathrm{\top }}\mathrm{\nabla }f(x),{\mathrm{\nabla }}^2\tilde{f}(z)=F^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)F,x=Fz+\hat{x}$$

由此可知：等式约束问题的 Newton 步有定义（即 KKT 矩阵可逆）当且仅当约简问题的 Newton 步有定义（即 ${\mathrm{\nabla }}^2\tilde{f}(z)$ 可逆）。约简问题的 Newton 步为

$$\mathrm{\Delta }{z}_{\mathrm{nt}}=-(F^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)F{)}^{-1}{F}^{\mathrm{\top }}\mathrm{\nabla }f(x)$$

它对应于原问题的方向 $F\mathrm{\Delta }{z}_{\mathrm{nt}}=-F(F^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)F{)}^{-1}{F}^{\mathrm{\top }}\mathrm{\nabla }f(x)$。可以验证（取 $\mathrm{\Delta }{x}_{\mathrm{nt}}=F\mathrm{\Delta }{z}_{\mathrm{nt}}$，$w=-(A{A}^{\mathrm{\top }}{)}^{-1}A(\mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}})$）这正是原问题由 KKT 方程定义的 Newton 方向。

类似地，约简问题在 $z$ 处的 Newton 减量 $\tilde{\lambda }(z)$ 与原问题在 $x$ 处的 Newton 减量相等：

$$\tilde{\lambda }(z{)}^2=\mathrm{\Delta }{z}_{\mathrm{nt}}^{\mathrm{\top }}{F}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)F\mathrm{\Delta }{z}_{\mathrm{nt}}=\mathrm{\Delta }{x}_{\mathrm{nt}}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}}=\lambda (x{)}^2$$

收敛性分析

既然带等式约束的 Newton 方法与对消去后的问题应用 Newton 方法完全相同，无约束 Newton 方法收敛性的一切结论都直接转移到等式约束的情形：一旦 $x^{(k)}$ 接近 $x^{\star }$，收敛极其迅速，只需几次迭代即可达到很高精度。

假设

• 下水平集 $S=\{x\mid x\in \mathrm{dom}f,f(x)⩽f(x^{(0)}),Ax=b\}$ 是闭集（当 $f$ 是闭函数时成立）。
• 在 $S$ 上，${\mathrm{\nabla }}^{2}f(x)⪯MI$，且

$${\Vert {\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]}^{-1}\Vert }_2⩽K$$

即 KKT 矩阵的逆在 $S$ 上有界（当然，为了 Newton 步在 $S$ 的每点有定义，其逆必须存在）。

• 对 $x,\tilde{x}\in S$，${\mathrm{\nabla }}^{2}f$ 满足 Lipschitz 条件 $\parallel {\mathrm{\nabla }}^{2}f(x)-{\mathrm{\nabla }}^{2}f(\tilde{x}){\parallel }_2⩽L\parallel x-\tilde{x}{\parallel }_2$。

KKT 矩阵有界逆假设​：条件“KKT 矩阵的逆有界”扮演了标准 Newton 方法分析中强凸性假设的角色。当没有等式约束时，该条件退化为 $\parallel {\mathrm{\nabla }}^{2}f(x{)}^{-1}{\parallel }_2⩽K$（取 $K=1/m$ 即强凸性）；带等式约束时，条件不如“最小特征值有正下界”那么简单：由于 KKT 矩阵是对称的，该条件即其 $n$ 个正特征值与 $p$ 个负特征值都有界远离零。

通过消去问题进行分析

上述假设意味着：消去后的目标函数 $\tilde{f}$ 及相应的初始点满足无约束 Newton 方法收敛分析所需的全部条件（常数 $\tilde{m}$、$\tilde{M}$、$\tilde{L}$ 不同）。因此，带等式约束的 Newton 方法收敛于 $x^{\star }$（以及 ${\nu }^{\star }$）。

其中最关键（也稍显微妙）的一环是：KKT 矩阵有界逆条件加上 Hessian 上界 ${\mathrm{\nabla }}^{2}f(x)⪯MI$，可以推出 ${\mathrm{\nabla }}^2\tilde{f}(z)⪰m\tilde{I}$（某正常数 $m$）。具体地，可以证明该不等式对

$$m=\frac{{\sigma }_{min}(F{)}^2}{K^{2}M}$$

成立（$F$ 满秩，故 $m>0$）。证明采用反证法：若 $F^{\mathrm{\top }}HF⪰̸mI$（$H={\mathrm{\nabla }}^{2}f(x)$），则存在 $\parallel u{\parallel }_2=1$ 使 $u^{\mathrm{\top }}{F}^{\mathrm{\top }}HFu<m$，即 $\parallel H^{1/2}Fu{\parallel }_2<m^{1/2}$；利用 $AF=0$ 构造 KKT 矩阵与向量 $(Fu,0)$ 的乘积，可得

$${\Vert {\left[\begin{array}{cc}H& A^{\mathrm{\top }}\\ A& 0\end{array}\right]}^{-1}\Vert }_2⩾\frac{\parallel Fu{\parallel }_2}{\parallel HFu{\parallel }_2}>\frac{{\sigma }_{min}(F)}{M^{1/2}{m}^{1/2}}=K$$

与假设矛盾。

自和谐函数的收敛分析

若 $f$ 自和谐，则 $\tilde{f}(z)=f(Fz+\hat{x})$ 也自和谐。因此若 $f$ 自和谐，等式约束 Newton 方法具有与无约束情形完全相同的复杂度估计：达到精度 $ϵ$ 所需的迭代次数不超过

$$\frac{20-8\alpha }{\alpha \beta (1-2\alpha {)}^2}(f(x^{(0)})-p^{\star })+{\log }_2{\log }_2(1/ϵ)$$

其中 $\alpha$、$\beta$ 为回溯参数。