Lecture 15 - Barrier Method

References

• Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/lectures/barr-method.pdf
• Reading: Boyd and Vandenberghe, Convex Optimization, Chapter 11

本章讨论内点法中最基础的 barrier method. 核心思想是用一个在约束边界处发散的光滑函数替代不等式约束, 从而把含不等式约束的凸优化问题转化为一系列只含等式约束的光滑优化问题.

1. Inequality Constrained Optimization

考虑如下含约束凸优化问题:

$$\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,\dots ,f_m:{\mathbb{R}}^n\to \mathbb{R}$ 是凸函数且二阶连续可微, $\mathbf{A}\in {\mathbb{R}}^{p\times n}$ 行满秩, 即 $\mathrm{rank}(\mathbf{A})=p<n$.

• 许多标准问题都可以写成这种形式, 例如 LP, QP, QCQP (quadratically constrained quadratic program).

• 一些看似不同的问题也可以通过引入辅助变量转化为上述形式. 例如

  $$\underset{\mathbf{x}}{\min }\underset{i=1,\dots ,m}{\max }{\mathbf{a}}_i^{\top }\mathbf{x}$$

  可以等价写成

  $$\begin{array}{rlrl}& \underset{\mathbf{x},t}{\min }& & t\\ & \text{subject to}& & {\mathbf{a}}_i^{\top }\mathbf{x}-t\le 0,i=1,\dots ,m.\end{array}$$

• SOCP 和 SDP 也可以在更一般的锥规划框架下用类似的内点法思想处理.

假设最优解 ${\mathbf{x}}^{\star }$ 存在, 并记 $p^{\star }:=f_0({\mathbf{x}}^{\star })$. 此外假设 Slater 条件成立, 即存在 $\mathbf{x}$ 使得

$$f_i(\mathbf{x})<0,i=1,\dots ,m,\mathbf{Ax}=\mathbf{b}.$$

因此该问题严格可行. 根据 Slater 定理, 强对偶成立, 原问题最优值等于对偶问题最优值.

原问题的 Lagrangian 为

$$L_P(\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}),{\lambda }_i\ge 0.$$

对应的 dual function 为

$$g(\mathbf{\lambda },\mathbf{\nu })=\underset{\mathbf{x}}{\inf }{L}_P(\mathbf{x},\mathbf{\lambda },\mathbf{\nu }),$$

对偶问题为

$$\begin{array}{rlrl}& \underset{\mathbf{\lambda },\mathbf{\nu }}{\max }& & g(\mathbf{\lambda },\mathbf{\nu })\\ & \text{subject to}& & {\lambda }_i\ge 0,i=1,\dots ,m.\end{array}\text{\hspace{1em}(D-P)}$$

在强对偶和适当正则性条件下, 最优解满足 KKT 条件:

$$\begin{array}{rlrl}& \text{Primal feasibility:}& & f_i({\mathbf{x}}^{\star })\le 0,i=1,\dots ,m;\mathbf{A}{\mathbf{x}}^{\star }=\mathbf{b},\\ & \text{Dual feasibility:}& & {\lambda }_i^{\star }\ge 0,i=1,\dots ,m,\\ & \text{Complementary slackness:}& & {\lambda }_i^{\star }{f}_i({\mathbf{x}}^{\star })=0,i=1,\dots ,m,\\ & \text{Stationarity:}& & \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.\end{array}$$

因此, 求解原问题可以等价地看作寻找满足 KKT 条件的三元组 $({\mathbf{x}}^{\star },{\mathbf{\lambda }}^{\star },{\mathbf{\nu }}^{\star })$.

2. Logarithmic Barrier Function and Central Path

等式约束可以用 equality-constrained Newton method 相对直接地处理, 参见 Newton Method. Barrier method 的主要目标是处理不等式约束.

忽略等式约束的困难后, 我们可以把不等式约束写入目标函数:

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

其中

$$I_{-}(u)=\{\begin{array}{ll}0,& u\le 0,\\ +\infty ,& u>0.\end{array}$$

这个 hard indicator 精确表达了可行性, 但不可微, 难以直接用 Newton 方法优化. Barrier method 用光滑近似替代它.

2.1 Logarithmic Barrier

Definition (Logarithmic barrier). 对 $t>0$, 定义

$${\hat{I}}_{-}(u)=-\frac{1}{t}\log (-u),\mathrm{dom}({\hat{I}}_{-})=\{u:u<0\}.$$

该函数只在严格可行区域 $u<0$ 内有定义, 且当 $u\to 0^{-}$ 时发散到 $+\infty$. 因此它会把迭代点限制在可行域内部, 这也是 interior-point method 名称的来源.

Figure: Log barrier 对 hard indicator 的光滑近似.

定义原问题的 log-barrier 函数

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

则原问题可以近似为如下只含等式约束的问题:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & f_0(\mathbf{x})+\frac{1}{t}\varphi (\mathbf{x})=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}$$

为了后续使用 Newton 方法, 计算 $\varphi$ 的梯度和 Hessian:

$$\begin{array}{rl}\nabla \varphi (\mathbf{x})& =-\sum _{i=1}^m\frac{1}{f_i(\mathbf{x})}\nabla f_i(\mathbf{x}),\\ {\nabla }^2\varphi (\mathbf{x})& =\sum _{i=1}^m\frac{1}{f_i(\mathbf{x}{)}^2}\nabla f_i(\mathbf{x})\nabla f_i(\mathbf{x}{)}^{\top }-\sum _{i=1}^m\frac{1}{f_i(\mathbf{x})}{\nabla }^2{f}_i(\mathbf{x}).\end{array}$$

参数 $t$ 控制近似精度. 当 $t$ 越大时, barrier 项 $\frac{1}{t}\varphi (\mathbf{x})$ 对目标函数的扰动越小, 近似越接近原问题; 但对应问题也越病态, 因为最优点会更靠近约束边界. 实践中通常取一列递增参数

$$t_0<t_1<\cdots ,$$

先求解较容易的低精度问题, 再用 warm start 逐步求解高精度问题.

2.2 Central Path

Definition (Central path). 对每个 $t>0$, 令 ${\mathbf{x}}^{\star }(t)$ 是如下 barrier subproblem 的最优解:

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & t{f}_0(\mathbf{x})+\varphi (\mathbf{x})\\ & \text{subject to}& & \mathbf{Ax}=\mathbf{b}.\end{array}\text{\hspace{1em}(CP(t))}$$

则

$$\{{\mathbf{x}}^{\star }(t):t>0\}$$

称为 central path. 这里把目标函数乘以 $t$ 与最小化 $f_0+\frac{1}{t}\varphi$ 是等价的.

给定原问题 $(\text{P})$, 我们可以构造一族 barrier subproblem $(\text{CP}(t))$. 对 $(\text{CP}(t))$ 写出 Lagrangian:

$$L_{CP}(\mathbf{x},\hat{\mathbf{\nu }})=t{f}_0(\mathbf{x})+\varphi (\mathbf{x})+{\hat{\mathbf{\nu }}}^{\top }(\mathbf{Ax}-\mathbf{b}).$$

由于 ${\mathbf{x}}^{\star }(t)$ 是该问题的最优解, 其满足 KKT 条件:

$$\begin{array}{rlrl}& \text{Primal feasibility:}& & \mathbf{A}{\mathbf{x}}^{\star }(t)=\mathbf{b},f_i({\mathbf{x}}^{\star }(t))<0,i=1,\dots ,m,\\ & \text{Stationarity:}& & t\nabla f_0({\mathbf{x}}^{\star }(t))-\sum _{i=1}^m\frac{1}{f_i({\mathbf{x}}^{\star }(t))}\nabla f_i({\mathbf{x}}^{\star }(t))+{\mathbf{A}}^{\top }{\hat{\mathbf{\nu }}}^{\star }(t)=0.\end{array}$$

注意 stationarity 条件中第二项来自 $\nabla \varphi (\mathbf{x})$.

2.3 Central Path and KKT Conditions

观察 central path 的 KKT 条件, 可以发现它与原问题 KKT 条件之间只差一个被扰动的 complementary slackness 条件.

对 stationarity 条件两边同时除以 $t$, 得到

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

也即

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

其中

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

逐项比较:

• Primal feasibility. Central path 上的 ${\mathbf{x}}^{\star }(t)$ 满足 $\mathbf{A}{\mathbf{x}}^{\star }(t)=\mathbf{b}$ 且 $f_i({\mathbf{x}}^{\star }(t))<0$, 因此也满足原问题的 primal feasibility.

• Dual feasibility. 因为 $t>0$ 且 $f_i({\mathbf{x}}^{\star }(t))<0$, 所以 ${\lambda }_i^{\star }(t)>0$, 自动满足 dual feasibility.

• Stationarity. 式 $(1)$ 正是原问题 Lagrangian 对 $\mathbf{x}$ 的 stationarity 条件.

• Complementary slackness. 原问题要求 ${\lambda }_i^{\star }{f}_i({\mathbf{x}}^{\star })=0$, 而 central path 上有

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

  这是一个 perturbed complementary slackness 条件. 当 $t\to +\infty$ 时, $-1/t\to 0$, 因而逐渐逼近原问题的 complementary slackness.

因此, barrier method 可以理解为求解一系列 perturbed KKT systems. 随着 $t$ 增大, 扰动逐渐消失, central path 逐渐逼近原问题最优解.

2.4 Dual Feasibility and Duality Gap

下面说明 central path 诱导出的

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

是原问题对偶问题 $(\text{D-P})$ 的一个可行解.

首先 ${\lambda }_i^{\star }(t)\ge 0$ 已经由严格可行性得到. 还需要说明

$$g({\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))>-\infty .$$

由式 $(1)$ 可知, ${\mathbf{x}}^{\star }(t)$ 是

$$L_P(\mathbf{x},{\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))$$

关于 $\mathbf{x}$ 的 stationary point. 又因为 $L_P$ 关于 $\mathbf{x}$ 是凸函数, 所以 ${\mathbf{x}}^{\star }(t)$ 是其 global minimizer. 因此

$$g({\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))=L_P({\mathbf{x}}^{\star }(t),{\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))>-\infty .$$

接着计算 duality gap:

$$\begin{array}{rl}g({\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))& =L_P({\mathbf{x}}^{\star }(t),{\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))\\ & =f_0({\mathbf{x}}^{\star }(t))+\sum _{i=1}^m{\lambda }_i^{\star }(t)f_i({\mathbf{x}}^{\star }(t))+{\mathbf{\nu }}^{\star }(t{)}^{\top }(\mathbf{A}{\mathbf{x}}^{\star }(t)-\mathbf{b})\\ & =f_0({\mathbf{x}}^{\star }(t))+\sum _{i=1}^m\frac{1}{t}\frac{1}{-f_i({\mathbf{x}}^{\star }(t))}{f}_i({\mathbf{x}}^{\star }(t))\\ & =f_0({\mathbf{x}}^{\star }(t))-\frac{m}{t}.\end{array}$$

由于 $({\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))$ 是 dual feasible, 弱对偶给出

$$g({\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))\le p^{\star }.$$

又因为 ${\mathbf{x}}^{\star }(t)$ 是 primal feasible, 所以 $p^{\star }\le f_0({\mathbf{x}}^{\star }(t))$. 于是

$$0\le f_0({\mathbf{x}}^{\star }(t))-p^{\star }\le f_0({\mathbf{x}}^{\star }(t))-g({\mathbf{\lambda }}^{\star }(t),{\mathbf{\nu }}^{\star }(t))=\frac{m}{t}.$$

这给出了 barrier method 的关键停止准则:

$$f_0({\mathbf{x}}^{\star }(t))-p^{\star }\le \frac{m}{t}.$$

当 $t\to +\infty$ 时, 上界趋于 $0$, 因而 central path 的目标值收敛到原问题最优值.

3. Barrier Method Algorithm

3.1 Algorithm Details

由上一节可知, 若希望得到 $\epsilon$-optimal 解, 只需使

$$\frac{m}{t}\le \epsilon ,$$

即 $t\ge m/\epsilon$. 直接取很大的 $t=m/\epsilon$ 通常不高效, 因为对应 barrier subproblem 可能非常难解. 实践中更常用 warm start: 从较小的 $t_0$ 开始, 逐步放大 $t$.

给定 $t_0>0$ 和增大因子 $\mu >1$, 令

$$t_k=t_0{\mu }^k.$$

依次求解

$$\begin{array}{rlrl}& \underset{\mathbf{x}}{\min }& & t_k{f}_0(\mathbf{x})+\varphi (\mathbf{x})\\ & \text{subject to}& & \mathbf{Ax}=\mathbf{b}.\end{array}\text{\hspace{1em}(CP(tk))}$$

每一步都用上一个问题的解作为 Newton 初始点. 当 $m/t_k\le \epsilon$ 时停止, 此时 ${\mathbf{x}}^{\star }(t_k)$ 是 $\epsilon$-optimal 解.

Algorithm (Barrier method).

• Input: 严格可行初始点 ${\mathbf{x}}_0$, 初始 barrier 参数 $t_0>0$, 增大因子 $\mu >1$, 精度要求 $\epsilon >0$.
• Repeat:

  1. 对当前 $t$, 用 equality-constrained Newton method 求解

     $${\mathbf{x}}^{\star }(t)=\arg \underset{\mathbf{Ax}=\mathbf{b}}{\min }\left\{t{f}_0(\mathbf{x})+\varphi (\mathbf{x})\right\}.$$

  2. 更新 $\mathbf{x}\leftarrow {\mathbf{x}}^{\star }(t)$, 作为下一个子问题的 warm start.

  3. 若 $m/t\le \epsilon$, 停止并输出 $\mathbf{x}$.

  4. 否则更新 $t\leftarrow \mu t$.

该算法有内外两层迭代结构. 外层迭代更新 $t$, 每次定义一个新的 barrier subproblem; 内层迭代用 Newton 方法求解当前 barrier subproblem.

3.2 Implementation Considerations

Centering accuracy. 理论推导常假设每个 centering step 都精确求得 ${\mathbf{x}}^{\star }(t)$. 实际数值计算中只能得到近似解 $\hat{\mathbf{x}}(t)\approx {\mathbf{x}}^{\star }(t)$. 只要每次求解足够精确, barrier method 仍可在渐近意义下保持收敛; 但近似误差会影响 stationarity 判断和 $m/t$ gap 估计, 因此实现中通常需要同时监控 Newton residual.

Choice of $\mu$. 若 $\mu$ 过小, 外层迭代次数会增加; 若 $\mu$ 过大, 相邻 barrier subproblem 差异太大, 内层 Newton 迭代可能变多. 经验上 barrier method 对 $\mu$ 并不极端敏感, 常见选择是 $\mu =10$ 或 $\mu =20$. 若做 worst-case complexity 分析, 往往取 $\mu$ 接近 $1^{+}$, 使相邻子问题更接近.

Choice of $t_0$. 若 $t_0$ 过小, 初始子问题容易求解但 gap $m/t_0$ 较大; 若 $t_0$ 过大, 第一个 centering step 可能很难. 如果已有 primal feasible 点 ${\mathbf{x}}_0$ 和 dual feasible 点 $({\mathbf{\lambda }}_0,{\mathbf{\nu }}_0)$, 可用初始 duality gap 选择

$$t_0=\frac{m}{f_0({\mathbf{x}}_0)-g({\mathbf{\lambda }}_0,{\mathbf{\nu }}_0)}.$$

如果只有严格可行的 ${\mathbf{x}}_0$, 但没有对偶可行点, 可以尝试选择 $t_0$ 使 ${\mathbf{x}}_0$ 尽量接近 $(\text{CP}(t_0))$ 的 central path. 一个启发式做法是求解

$$\underset{\mathbf{\nu },t>0}{\min }\Vert t\nabla f_0({\mathbf{x}}_0)+\nabla \varphi ({\mathbf{x}}_0)+{\mathbf{A}}^{\top }\mathbf{\nu }\Vert ,$$

即让 ${\mathbf{x}}_0$ 尽量满足对应 barrier subproblem 的 stationarity 条件. 范数也可用 Hessian 诱导范数度量, 以更好反映局部曲率.

Initial point. 传统 barrier method 需要严格可行初始点:

$$f_i({\mathbf{x}}_0)<0,i=1,\dots ,m,\mathbf{A}{\mathbf{x}}_0=\mathbf{b}.$$

其中不等式严格可行性通常不可违反, 因为 log barrier 在边界外无定义. 对等式约束 $\mathbf{A}{\mathbf{x}}_0=\mathbf{b}$, 可以使用 infeasible-start Newton method 从不满足等式约束的点开始, 逐步把迭代拉回等式可行域.

3.3 Convergence

若每个 centering step 都精确求解, 则第 $k$ 次外层迭代后

$$f_0({\mathbf{x}}^{(k)})-p^{\star }\le \frac{m}{t_k}=\frac{m}{t_0{\mu }^k}.$$

为了达到 $f_0({\mathbf{x}}^{(k)})-p^{\star }\le \epsilon$, 只需

$$k\ge \frac{\log (m/(t_0\epsilon ))}{\log \mu }.$$

因此外层 centering steps 的数量是

$$O\left(\log \frac{1}{\epsilon }\right).$$

在 self-concordance 条件下, 可以进一步证明每个 centering step 所需 Newton 迭代数近似为常数级, 因而总 Newton 迭代数也保持对 ${\epsilon }^{-1}$ 的对数依赖.

4. Feasibility and Phase I Problem

Barrier method 的一个关键前提是存在严格可行初始点. 因此在进入 Phase II 的原问题求解前, 通常需要先解决一个 Phase I feasibility problem.

4.1 Basic Phase I Problem

为了寻找严格可行点, 考虑辅助问题

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

直观上, $s$ 是所有不等式约束的最大 violation 上界. 若能找到 $s<0$, 则有

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

从而 $\mathbf{x}$ 是原问题的严格可行点.

对 Phase I 问题应用 barrier method, 得到 centering problem:

$$\begin{array}{rlrl}& \underset{\mathbf{x},s}{\min }& & ts-\sum _{i=1}^m\log (s-f_i(\mathbf{x}))\\ & \text{subject to}& & \mathbf{Ax}=\mathbf{b}.\end{array}\text{\hspace{1em}(CP-Phase I(t))}$$

初始时可以选择足够大的 $s^{(0)}$ 使

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

从而 log barrier 有定义. 迭代过程中, 一旦得到 $s^{(k)}<0$, 就可以提前停止; 此时 ${\mathbf{x}}^{(k)}$ 已经是 Phase II 可用的严格可行初始点, 不需要把 Phase I 问题高精度求到最优.

设 Phase I 最优值为 $p_{\text{Phase I}}^{\star }$, 则:

• 若 $p_{\text{Phase I}}^{\star }<0$, 原问题严格可行.
• 若 $p_{\text{Phase I}}^{\star }>0$, 原问题不可行.
• 若 $p_{\text{Phase I}}^{\star }=0$, 则处于边界情形. 如果最优解可达, 原问题可行但没有严格可行点; 如果最优值不可达, 则不能得到可行点.

4.2 Sum-of-Infeasibilities Variant

Basic Phase I 使用一个共享 slack $s$, 它度量最大 violation. 另一种常见变体是为每个不等式引入单独的 slack variable:

$$\begin{array}{rlrl}& \underset{\mathbf{x},\mathbf{s}}{\min }& & \sum _{i=1}^m{s}_i\\ & \text{subject to}& & f_i(\mathbf{x})\le s_i,i=1,\dots ,m,\\ & & & \mathbf{Ax}=\mathbf{b},\\ & & & s_i\ge 0,i=1,\dots ,m.\end{array}\text{\hspace{1em}(P-Phase I-Sum)}$$

相比共享一个 $s$, 该形式能更细致地反映每个约束的违背程度. 当原不等式系统不可行时, 非零的 $s_i$ 可以提示哪些约束无法同时满足.

Figure: Basic Phase I 与 sum-of-infeasibilities variant 的 violation 分布比较.

在图示例子中, basic Phase I 只满足 100 个约束中的 39 个; sum-of-infeasibilities variant 满足 79 个约束, 说明单独 slack 能诱导更稀疏、更有解释性的 violation pattern.

4.3 Termination Near the Phase II Central Path

Basic Phase I 的目标只是找到严格可行点. 但即使已经得到

$$\mathbf{x}\in \{\mathbf{x}:f_i(\mathbf{x})<0,\mathbf{Ax}=\mathbf{b}\},$$

该点也可能离 Phase II 的 central path 很远, 导致后续 barrier method 需要较多 Newton 迭代才能回到 central path 附近.

一种改造方式是在 Phase I 中加入目标函数上界约束:

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

其中 $M$ 是足够大的常数, 例如满足

$$M>\max \{f_0({\mathbf{x}}^{(0)}),p^{\star }\}.$$

对该问题使用 log barrier, 给定 $\tilde{t}$, 得到

$$\begin{array}{rlrl}& \underset{\mathbf{x},s}{\min }& & \tilde{t}s-\sum _{i=1}^m\log (s-f_i(\mathbf{x}))-\log (M-f_0(\mathbf{x}))\\ & \text{subject to}& & \mathbf{Ax}=\mathbf{b}.\end{array}\text{\hspace{1em}(CP-Phase I-Modified(t))}$$

其 stationarity 条件为

$$\begin{array}{rl}& \tilde{t}-\sum _{i=1}^m\frac{1}{s-f_i(\mathbf{x})}=0,\\ & \sum _{i=1}^m\frac{1}{s-f_i(\mathbf{x})}\nabla f_i(\mathbf{x})+\frac{1}{M-f_0(\mathbf{x})}\nabla f_0(\mathbf{x})+{\mathbf{A}}^{\top }\hat{\mathbf{\nu }}=0.\end{array}$$

当 $s=0$ 时, 第二个条件变为

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

对比 Phase II barrier subproblem 的 stationarity:

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

只要令

$$t=\frac{1}{M-f_0(\mathbf{x})},$$

两者形式一致. 因此, 加入 $f_0(\mathbf{x})\le M$ 后, Phase I 在接近 $s=0$ 时能更自然地靠近 Phase II central path, 从而减少后续 centering 的代价.

4.4 Phase I via Infeasible-Start Newton Method

若一开始难以找到满足 $\mathbf{Ax}=\mathbf{b}$ 的点, 可以对 Phase I centering problem 使用 infeasible-start Newton method.

考虑

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

只要能找到某个 $\mathbf{x}\in \mathcal{D}:={\bigcap }_{i=0}^m\mathrm{dom}(f_i)$, 就可以取

$$s>\underset{i}{\max }{f}_i(\mathbf{x}),$$

从而保证所有 log barrier 项都有定义. 即使此时 $\mathbf{Ax}\ne \mathbf{b}$, infeasible-start Newton method 也可以同时降低 residual 并逼近等式可行域.

如果连公共定义域中的初始点都难以构造, 还可以引入 shift variables $z_0,\dots ,z_m$:

$$\begin{array}{rlrl}& \underset{\mathbf{x},s,z_0,\dots ,z_m}{\min }& & \bar{t}{f}_0(\mathbf{x}+z_0)+\bar{t}s-\sum _{i=1}^m\log (s-f_i(\mathbf{x}+z_i))\\ & \text{subject to}& & \mathbf{Ax}=\mathbf{b},\\ & & & z_i=0,i=0,\dots ,m.\end{array}$$

这些 shift variables 允许每个函数先在自己的定义域内启动, 再通过等式约束逐步把 $z_i$ 推回 $0$. 最终 $z_i=0$ 后, 求得的 $\mathbf{x}$ 才是原问题的可行点.

Related Notes

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