Lecture 16 - Primal-Dual Interior-Point Methods

References

• Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/lectures/primal-dual.pdf
• Reading:
  1. Boyd and Vandenberghe, Convex Optimization, Section 11.7
  2. 刘浩洋等, 《最优化: 建模、算法与理论》, Section 7.3

本章讨论 primal-dual interior-point method. 它与 barrier method 都可以由 perturbed KKT conditions 推出, 但 primal-dual method 不再把问题拆成外层更新 $t$ 和内层精确 centering 两层循环, 而是在每一步同时更新 primal variables, dual variables 和 equality multipliers.

1. Problem Setup and Perturbed KKT Conditions

1.1 Original Problem

考虑如下含不等式约束和等式约束的凸优化问题:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & f_0(\mathbf{x})\\ & \text{subject to}& & f_i(\mathbf{x})\le 0,i=1,\dots ,m,\\ & & & \mathbf{Ax}=\mathbf{b}.\end{array}\text{\hspace{1em}(P)}$$

其中 $f_0,f_1,\dots ,f_m$ 都是二阶连续可微的凸函数, $\mathbf{A}\in {\mathbb{R}}^{p\times n}$ 行满秩. 假设 Slater 条件成立, 因而强对偶成立.

记

$$f(\mathbf{x})=\left[\begin{array}{c}{f}_1(\mathbf{x})\\ ⋮\\ f_m(\mathbf{x})\end{array}\right]\in {\mathbb{R}}^m,Df(\mathbf{x})=\left[\begin{array}{c}\nabla f_1(\mathbf{x}{)}^{\top }\\ ⋮\\ \nabla f_m(\mathbf{x}{)}^{\top }\end{array}\right]\in {\mathbb{R}}^{m\times n}.$$

原问题的 KKT 条件为

$$\begin{array}{rl}& \nabla f_0({\mathbf{x}}^{\star })+Df({\mathbf{x}}^{\star }{)}^{\top }{\mathbf{\lambda }}^{\star }+{\mathbf{A}}^{\top }{\mathbf{\nu }}^{\star }=0,\\ & f_i({\mathbf{x}}^{\star })\le 0,i=1,\dots ,m,\\ & \mathbf{A}{\mathbf{x}}^{\star }=\mathbf{b},\\ & {\lambda }_i^{\star }\ge 0,i=1,\dots ,m,\\ & {\lambda }_i^{\star }{f}_i({\mathbf{x}}^{\star })=0,i=1,\dots ,m.\end{array}$$

第一行等价于

$$\nabla f_0({\mathbf{x}}^{\star })+\sum _{i=1}^m{\lambda }_i^{\star }\nabla f_i({\mathbf{x}}^{\star })+{\mathbf{A}}^{\top }{\mathbf{\nu }}^{\star }=0.$$

1.2 Review of Barrier Method

Barrier method 求解如下子问题:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & f_0(\mathbf{x})-\frac{1}{t}\sum _{i=1}^m\log (-f_i(\mathbf{x}))\\ & \text{subject to}& & \mathbf{Ax}=\mathbf{b}.\end{array}$$

其 KKT stationarity condition 为

$$\nabla f_0({\mathbf{x}}^{\star }(t))+\sum _{i=1}^m\frac{1}{t}\frac{1}{-f_i({\mathbf{x}}^{\star }(t))}\nabla f_i({\mathbf{x}}^{\star }(t))+{\mathbf{A}}^{\top }{\mathbf{\nu }}^{\star }(t)=0.$$

若定义

$${\lambda }_i^{\star }(t)=\frac{1}{t}\frac{1}{-f_i({\mathbf{x}}^{\star }(t))},$$

则 barrier method 满足

$${\lambda }_i^{\star }(t)f_i({\mathbf{x}}^{\star }(t))=-\frac{1}{t},$$

而不是原始 KKT 中的 complementary slackness:

$${\lambda }_i^{\star }{f}_i({\mathbf{x}}^{\star })=0.$$

因此, barrier method 可以看作在求解如下 perturbed KKT conditions:

$$\{\begin{array}{l}\nabla f_0(\mathbf{x})+{\sum }_{i=1}^m{\lambda }_i\nabla f_i(\mathbf{x})+{\mathbf{A}}^{\top }\mathbf{\nu }=0,\\ -{\lambda }_i{f}_i(\mathbf{x})=\frac{1}{t},i=1,\dots ,m,\\ \mathbf{Ax}=\mathbf{b},\\ f_i(\mathbf{x})<0,{\lambda }_i>0,i=1,\dots ,m.\end{array}\text{\hspace{1em}(Perturbed KKT)}$$

Barrier method 的流程是: 对一列逐渐增大的 $t$, 先求 ${\mathbf{x}}^{\star }(t)$, 再由

$${\lambda }_i^{\star }(t)=\frac{1}{t}\frac{1}{-f_i({\mathbf{x}}^{\star }(t))}$$

恢复 dual variables. Primal-dual method 则不同: 它在给定 $t$ 的情况下, 直接同时求解 $\mathbf{x}(t)$, $\mathbf{\lambda }(t)$ 和 $\mathbf{\nu }(t)$.

2. Primal-Dual Search Direction

2.1 Residual Form

将 perturbed KKT conditions 写成 nonlinear system:

$${\mathbf{r}}_t(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })=\left[\begin{array}{c}\nabla f_0(\mathbf{x})+Df(\mathbf{x}{)}^{\top }\mathbf{\lambda }+{\mathbf{A}}^{\top }\mathbf{\nu }\\ -\mathrm{diag}(\mathbf{\lambda })f(\mathbf{x})-\frac{1}{t}1\\ \mathbf{Ax}-\mathbf{b}\end{array}\right]:=\left[\begin{array}{c}{\mathbf{r}}_{\mathrm{dual}}(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })\\ {\mathbf{r}}_{\mathrm{cent}}(\mathbf{x},\mathbf{\lambda })\\ {\mathbf{r}}_{\mathrm{primal}}(\mathbf{x})\end{array}\right].$$

其中 $\mathrm{diag}(\mathbf{\lambda })$ 是以 ${\lambda }_1,\dots ,{\lambda }_m$ 为对角元素的对角矩阵.

这三个 residual 的含义如下:

• ${\mathbf{r}}_{\mathrm{primal}}(\mathbf{x})$ 衡量 equality constraint 的 violation. 当 ${\mathbf{r}}_{\mathrm{primal}}(\mathbf{x})=0$ 时, 满足 $\mathbf{Ax}=\mathbf{b}$.

• ${\mathbf{r}}_{\mathrm{dual}}(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })$ 衡量 stationarity violation. 当 ${\mathbf{r}}_{\mathrm{dual}}=0$ 时, Lagrangian 对 $\mathbf{x}$ 的梯度为 $0$.

• ${\mathbf{r}}_{\mathrm{cent}}(\mathbf{x},\mathbf{\lambda })$ 衡量 centrality violation. 当第 $i$ 个分量满足

  $$-{\lambda }_i{f}_i(\mathbf{x})-\frac{1}{t}=0,$$

  就有 perturbed complementary slackness:

  $${\lambda }_i{f}_i(\mathbf{x})=-\frac{1}{t}.$$

因此, 当

$${\mathbf{r}}_t(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })=0$$

且 $f_i(\mathbf{x})<0$, ${\lambda }_i>0$ 时, 就满足 perturbed KKT conditions.

2.2 Newton Step for the Residual System

Primal-dual method 的核心是用 Newton’s method 解 nonlinear system:

$${\mathbf{r}}_t(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })=0.$$

记

$$\mathbf{y}=\left[\begin{array}{c}\mathbf{x}\\ \mathbf{\lambda }\\ \mathbf{\nu }\end{array}\right],\Delta \mathbf{y}=\left[\begin{array}{c}\Delta \mathbf{x}\\ \Delta \mathbf{\lambda }\\ \Delta \mathbf{\nu }\end{array}\right].$$

对当前点一阶展开:

$${\mathbf{r}}_t(\mathbf{y}+\Delta \mathbf{y})\approx {\mathbf{r}}_t(\mathbf{y})+D{\mathbf{r}}_t(\mathbf{y})\Delta \mathbf{y}.$$

为了使下一步 residual 尽量接近 $0$, 令

$${\mathbf{r}}_t(\mathbf{y})+D{\mathbf{r}}_t(\mathbf{y})\Delta \mathbf{y}=0,$$

即求解线性系统

$$D{\mathbf{r}}_t(\mathbf{y})\Delta \mathbf{y}=-{\mathbf{r}}_t(\mathbf{y}).$$

计算 Jacobian 中的各个 block:

$$\begin{array}{rlrlrl}& {\nabla }_{\mathbf{x}}{\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})={\nabla }^2{f}_0(\mathbf{x})+\sum _{i=1}^m{\lambda }_i{\nabla }^2{f}_i(\mathbf{x}),& & {\nabla }_{\mathbf{\lambda }}{\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})=Df(\mathbf{x}{)}^{\top },& & {\nabla }_{\mathbf{\nu }}{\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})={\mathbf{A}}^{\top },\\ & {\nabla }_{\mathbf{x}}{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y})=-\mathrm{diag}(\mathbf{\lambda })Df(\mathbf{x}),& & {\nabla }_{\mathbf{\lambda }}{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y})=-\mathrm{diag}(f(\mathbf{x})),& & {\nabla }_{\mathbf{\nu }}{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y})=0,\\ & {\nabla }_{\mathbf{x}}{\mathbf{r}}_{\mathrm{primal}}(\mathbf{y})=\mathbf{A},& & {\nabla }_{\mathbf{\lambda }}{\mathbf{r}}_{\mathrm{primal}}(\mathbf{y})=0,& & {\nabla }_{\mathbf{\nu }}{\mathbf{r}}_{\mathrm{primal}}(\mathbf{y})=0.\end{array}$$

其中

$$\mathrm{diag}(f(\mathbf{x}))=\mathrm{diag}(f_1(\mathbf{x}),\dots ,f_m(\mathbf{x})).$$

于是 primal-dual Newton direction 由下列线性系统给出:

$$\left[\begin{array}{ccc}{\nabla }^2{f}_0(\mathbf{x})+{\sum }_{i=1}^m{\lambda }_i{\nabla }^2{f}_i(\mathbf{x})& Df(\mathbf{x}{)}^{\top }& {\mathbf{A}}^{\top }\\ -\mathrm{diag}(\mathbf{\lambda })Df(\mathbf{x})& -\mathrm{diag}(f(\mathbf{x}))& 0\\ \mathbf{A}& 0& 0\end{array}\right]\left[\begin{array}{c}\Delta \mathbf{x}\\ \Delta \mathbf{\lambda }\\ \Delta \mathbf{\nu }\end{array}\right]=-\left[\begin{array}{c}{\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})\\ {\mathbf{r}}_{\mathrm{cent}}(\mathbf{y})\\ {\mathbf{r}}_{\mathrm{primal}}(\mathbf{y})\end{array}\right].$$

该方向同时更新 primal variables 和 dual variables, 因而称为 primal-dual search direction.

3. Relation to Barrier Method

3.1 Eliminating $\Delta \mathbf{\lambda }$

为了比较 primal-dual method 与 barrier method, 先从 Newton system 的第二行出发:

$$-\mathrm{diag}(\mathbf{\lambda })Df(\mathbf{x})\Delta \mathbf{x}-\mathrm{diag}(f(\mathbf{x}))\Delta \mathbf{\lambda }=-{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y}).$$

解出

$$\Delta \mathbf{\lambda }=-\mathrm{diag}(f(\mathbf{x}){)}^{-1}\mathrm{diag}(\mathbf{\lambda })Df(\mathbf{x})\Delta \mathbf{x}+\mathrm{diag}(f(\mathbf{x}){)}^{-1}{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y}).$$

代回第一行, 得到关于 $\Delta \mathbf{x}$ 和 $\Delta \mathbf{\nu }$ 的 reduced system:

$${\mathbf{H}}_{\mathrm{pd}}\Delta \mathbf{x}+{\mathbf{A}}^{\top }\Delta \mathbf{\nu }=-{\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})-Df(\mathbf{x}{)}^{\top }\mathrm{diag}(f(\mathbf{x}){)}^{-1}{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y}),$$

其中

$$\begin{array}{rl}{\mathbf{H}}_{\mathrm{pd}}& ={\nabla }^2{f}_0(\mathbf{x})+\sum _{i=1}^m{\lambda }_i{\nabla }^2{f}_i(\mathbf{x})-Df(\mathbf{x}{)}^{\top }\mathrm{diag}(f(\mathbf{x}){)}^{-1}\mathrm{diag}(\mathbf{\lambda })Df(\mathbf{x})\\ & ={\nabla }^2{f}_0(\mathbf{x})+\sum _{i=1}^m{\lambda }_i{\nabla }^2{f}_i(\mathbf{x})+\sum _{i=1}^m\frac{{\lambda }_i}{-f_i(\mathbf{x})}\nabla f_i(\mathbf{x})\nabla f_i(\mathbf{x}{)}^{\top }.\end{array}$$

再代入

$${\mathbf{r}}_{\mathrm{cent}}(\mathbf{y})=-\mathrm{diag}(\mathbf{\lambda })f(\mathbf{x})-\frac{1}{t}1$$

和

$${\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})=\nabla f_0(\mathbf{x})+Df(\mathbf{x}{)}^{\top }\mathbf{\lambda }+{\mathbf{A}}^{\top }\mathbf{\nu },$$

得到 RHS:

$$\begin{array}{rl}& -{\mathbf{r}}_{\mathrm{dual}}(\mathbf{y})-Df(\mathbf{x}{)}^{\top }\mathrm{diag}(f(\mathbf{x}){)}^{-1}{\mathbf{r}}_{\mathrm{cent}}(\mathbf{y})\\ & =-\nabla f_0(\mathbf{x})-Df(\mathbf{x}{)}^{\top }\mathbf{\lambda }-{\mathbf{A}}^{\top }\mathbf{\nu }+Df(\mathbf{x}{)}^{\top }\mathrm{diag}(f(\mathbf{x}){)}^{-1}\mathrm{diag}(\mathbf{\lambda })f(\mathbf{x})+\frac{1}{t}Df(\mathbf{x}{)}^{\top }\mathrm{diag}(f(\mathbf{x}){)}^{-1}1\\ & =-\nabla f_0(\mathbf{x})-{\mathbf{A}}^{\top }\mathbf{\nu }-\frac{1}{t}\sum _{i=1}^m\frac{1}{-f_i(\mathbf{x})}\nabla f_i(\mathbf{x})\\ & =-\left(\nabla f_0(\mathbf{x})+\frac{1}{t}\sum _{i=1}^m\frac{1}{-f_i(\mathbf{x})}\nabla f_i(\mathbf{x})+{\mathbf{A}}^{\top }\mathbf{\nu }\right).\end{array}$$

因此 reduced system 可以写成

$$\left[\begin{array}{cc}{\mathbf{H}}_{\mathrm{pd}}& {\mathbf{A}}^{\top }\\ \mathbf{A}& 0\end{array}\right]\left[\begin{array}{c}\Delta \mathbf{x}\\ \Delta \mathbf{\nu }\end{array}\right]=-\left[\begin{array}{c}\nabla f_0(\mathbf{x})+\frac{1}{t}{\sum }_{i=1}^m\frac{1}{-f_i(\mathbf{x})}\nabla f_i(\mathbf{x})+{\mathbf{A}}^{\top }\mathbf{\nu }\\ \mathbf{Ax}-\mathbf{b}\end{array}\right].$$

3.2 Comparison with Barrier Newton Step

Barrier method 的目标函数为

$$\psi (\mathbf{x}):=f_0(\mathbf{x})-\frac{1}{t}\sum _{i=1}^m\log (-f_i(\mathbf{x})).$$

其梯度为

$$\nabla \psi (\mathbf{x})=\nabla f_0(\mathbf{x})+\frac{1}{t}\sum _{i=1}^m\frac{1}{-f_i(\mathbf{x})}\nabla f_i(\mathbf{x}),$$

Hessian 为

$${\nabla }^2\psi (\mathbf{x})={\nabla }^2{f}_0(\mathbf{x})+\frac{1}{t}\sum _{i=1}^m\frac{1}{-f_i(\mathbf{x})}{\nabla }^2{f}_i(\mathbf{x})+\frac{1}{t}\sum _{i=1}^m\frac{1}{f_i(\mathbf{x}{)}^2}\nabla f_i(\mathbf{x})\nabla f_i(\mathbf{x}{)}^{\top }.$$

Barrier method 的 equality-constrained Newton step 满足

$$\left[\begin{array}{cc}{\nabla }^2\psi (\mathbf{x})& {\mathbf{A}}^{\top }\\ \mathbf{A}& 0\end{array}\right]\left[\begin{array}{c}\Delta {\mathbf{x}}^{\mathrm{barrier}}\\ \Delta {\mathbf{\nu }}^{\mathrm{barrier}}\end{array}\right]=-\left[\begin{array}{c}\nabla \psi (\mathbf{x})+{\mathbf{A}}^{\top }\mathbf{\nu }\\ \mathbf{Ax}-\mathbf{b}\end{array}\right].$$

若 primal-dual method 中的 dual variables 恰好满足 central path relation:

$${\lambda }_i=\frac{1}{t}\frac{1}{-f_i(\mathbf{x})},$$

则

$${\mathbf{H}}_{\mathrm{pd}}={\nabla }^2\psi (\mathbf{x}),$$

且 reduced primal-dual system 的 RHS 也与 barrier Newton system 相同. 因此, barrier method 的 Newton step 可以看作 primal-dual Newton step 的一个特殊情形.

更一般地, primal-dual method 不要求 $\mathbf{\lambda }$ 已经满足 central path relation. 它直接在 $(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })$ 空间中做 Newton step, 因而 primal 和 dual updates 被绑定在同一个线性系统中.

4. Surrogate Duality Gap and Algorithm

4.1 Surrogate Duality Gap

对原问题, Lagrangian 为

$$L(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })=f_0(\mathbf{x})+\sum _{i=1}^m{\lambda }_i{f}_i(\mathbf{x})+{\mathbf{\nu }}^{\top }(\mathbf{Ax}-\mathbf{b}).$$

若 $\tilde{\mathbf{x}}$ primal feasible, 且 $\mathbf{\lambda }\ge 0$, 则

$$\begin{array}{rl}L(\tilde{\mathbf{x}},\mathbf{\lambda },\mathbf{\nu })& =f_0(\tilde{\mathbf{x}})+\sum _{i=1}^m{\lambda }_i{f}_i(\tilde{\mathbf{x}})+{\mathbf{\nu }}^{\top }(\mathbf{A}\tilde{\mathbf{x}}-\mathbf{b})\\ & \le f_0(\tilde{\mathbf{x}}).\end{array}$$

因此 dual function 满足

$$g(\mathbf{\lambda },\mathbf{\nu })=\underset{\mathbf{x}}{\inf }L(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })\le L(\tilde{\mathbf{x}},\mathbf{\lambda },\mathbf{\nu })\le f_0(\tilde{\mathbf{x}}).$$

如果进一步有 dual residual 为 $0$:

$${\mathbf{r}}_{\mathrm{dual}}(\tilde{\mathbf{x}},\mathbf{\lambda },\mathbf{\nu })=\nabla f_0(\tilde{\mathbf{x}})+Df(\tilde{\mathbf{x}}{)}^{\top }\mathbf{\lambda }+{\mathbf{A}}^{\top }\mathbf{\nu }=0,$$

则 $\tilde{\mathbf{x}}$ 是 $L(\cdot ,\mathbf{\lambda },\mathbf{\nu })$ 的 global minimizer, 所以

$$g(\mathbf{\lambda },\mathbf{\nu })=L(\tilde{\mathbf{x}},\mathbf{\lambda },\mathbf{\nu }).$$

此时真实 duality gap 为

$$\begin{array}{rl}{f}_0(\tilde{\mathbf{x}})-g(\mathbf{\lambda },\mathbf{\nu })& =f_0(\tilde{\mathbf{x}})-\left[f_0(\tilde{\mathbf{x}})+\sum _{i=1}^m{\lambda }_i{f}_i(\tilde{\mathbf{x}})+{\mathbf{\nu }}^{\top }(\mathbf{A}\tilde{\mathbf{x}}-\mathbf{b})\right]\\ & =-\sum _{i=1}^m{\lambda }_i{f}_i(\tilde{\mathbf{x}})=-{\mathbf{\lambda }}^{\top }f(\tilde{\mathbf{x}}).\end{array}$$

Primal-dual method 的迭代点通常不是 exactly primal feasible 或 dual feasible, 即

$${\mathbf{r}}_{\mathrm{primal}}({\mathbf{y}}^{(k)})\ne 0,{\mathbf{r}}_{\mathrm{dual}}({\mathbf{y}}^{(k)})\ne 0.$$

因此

$$-{\mathbf{\lambda }}^{(k)\top }f({\mathbf{x}}^{(k)})$$

不能严格称为真实 duality gap, 而称为 surrogate duality gap.

Definition (Surrogate duality gap). 对满足 $f_i(\mathbf{x})<0$ 和 $\mathbf{\lambda }>0$ 的 primal-dual iterate, 定义

$$\hat{\eta }:=-{\mathbf{\lambda }}^{\top }f(\mathbf{x})=\sum _{i=1}^m-{\lambda }_i{f}_i(\mathbf{x}).$$

它也可以看作 complementary slackness violation 的总量. 若每个 $-{\lambda }_i{f}_i(\mathbf{x})$ 都接近 $0$, 则 complementary slackness 近似成立.

若当前点正好在 central path 上, 则

$$-{\lambda }_i{f}_i(\mathbf{x})=\frac{1}{t},$$

所以

$$\hat{\eta }=\frac{m}{t},t=\frac{m}{\hat{\eta }}.$$

4.2 Primal-Dual Interior-Point Method

Algorithm (Primal-dual interior-point method).

• Input: 初始点 ${\mathbf{x}}^{(0)}$ 满足 $f_i({\mathbf{x}}^{(0)})<0$, $i=1,\dots ,m$; 初始 ${\mathbf{\lambda }}^{(0)}>0$; 任意 ${\mathbf{\nu }}^{(0)}$; 参数 $\mu >1$, ${\epsilon }_{\mathrm{feas}}>0$, ${\epsilon }_{\mathrm{gap}}>0$.

• Repeat: 对当前点 ${\mathbf{y}}^{(k)}=({\mathbf{x}}^{(k)},{\mathbf{\lambda }}^{(k)},{\mathbf{\nu }}^{(k)})$:

  1. 计算 surrogate gap:

     $${\hat{\eta }}^{(k)}=-{\mathbf{\lambda }}^{(k)\top }f({\mathbf{x}}^{(k)}).$$

  2. 选择 centering parameter:

     $$t^{(k)}=\mu \frac{m}{{\hat{\eta }}^{(k)}}.$$

  3. 求解 primal-dual Newton system, 得到方向

     $$\Delta {\mathbf{y}}_{\mathrm{nt}}^{(k)}=\left[\begin{array}{c}\Delta {\mathbf{x}}_{\mathrm{nt}}^{(k)}\\ \Delta {\mathbf{\lambda }}_{\mathrm{nt}}^{(k)}\\ \Delta {\mathbf{\nu }}_{\mathrm{nt}}^{(k)}\end{array}\right].$$

  4. 通过 backtracking line search 选择步长 $s^{(k)}$.

  5. 更新

     $${\mathbf{y}}^{(k+1)}={\mathbf{y}}^{(k)}+s^{(k)}\Delta {\mathbf{y}}_{\mathrm{nt}}^{(k)}.$$

• Stop when:

  $$\Vert {\mathbf{r}}_{\mathrm{primal}}({\mathbf{y}}^{(k)}){\Vert }_2\le {\epsilon }_{\mathrm{feas}},\Vert {\mathbf{r}}_{\mathrm{dual}}({\mathbf{y}}^{(k)}){\Vert }_2\le {\epsilon }_{\mathrm{feas}},{\hat{\eta }}^{(k)}\le {\epsilon }_{\mathrm{gap}}.$$

该算法的几个关键点:

• 若当前点恰好在某条 central path 上, 则 $\hat{\eta }=m/t$. 因此选择 $t^{(k)}=\mu m/{\hat{\eta }}^{(k)}$ 等价于把对应 central path parameter 放大 $\mu$ 倍.
• Primal-dual method 每次只做一个 Newton step, 然后立即重新计算 surrogate gap 和新的 $t$. 因此它不像 barrier method 那样显式区分内层 centering 和外层更新.
• 迭代过程中 ${\mathbf{x}}^{(k)}$ 和 ${\mathbf{\lambda }}^{(k)}$ 通常保持 strictly feasible, 但 $\mathbf{A}{\mathbf{x}}^{(k)}=\mathbf{b}$ 与 dual stationarity 不一定精确成立, 只要求 residual 逐步下降.

4.3 Backtracking Line Search

Line search 需要同时保证三件事:

1. 保持 $\mathbf{\lambda }>0$.
2. 保持 $f_i(\mathbf{x})<0$, 即 primal inequality strict feasibility.
3. 使 residual norm 有足够下降.

首先, 为保证

$$\mathbf{\lambda }+s\Delta \mathbf{\lambda }>0,$$

取最大安全步长

$$s_{\max }=\min \left\{1,\underset{i:\Delta {\lambda }_i<0}{\min }\left(-\frac{{\lambda }_i}{\Delta {\lambda }_i}\right)\right\}.$$

实际中通常从稍小的步长开始, 例如

$$s=0.99s_{\max }.$$

接着用 backtracking 保证

$$f_i(\mathbf{x}+s\Delta \mathbf{x})<0,i=1,\dots ,m.$$

若不满足, 则令 $s\leftarrow \beta s$, 其中 $\beta \in (0,1)$, 直到严格可行.

最后要求 residual 有足够下降, 例如

$$\Vert {\mathbf{r}}_t(\mathbf{y}+s\Delta \mathbf{y}){\Vert }_2\le (1-\alpha s)\Vert {\mathbf{r}}_t(\mathbf{y}){\Vert }_2,\alpha \in (0,1).$$

若不满足, 同样令 $s\leftarrow \beta s$ 继续回溯.

Related Notes

• Barrier Method
• Newton Method
• Optimality Conditions for Constrained Optimization
• Numerical Linear Algebra