优化方法基础课程

发表于 2021-11-20 Waline：阅读次数：

今天刚考了优化方法，感觉还可以，但是据说改卷很严，我好像也感受到要是一严我就裂开了。唉，听天由命吧。

考前看到有之前上了的同学给这个课的评价，瘆得慌，博文链接在下面：

https://www.cnblogs.com/betelgeu/p/14999087.html

虽然他觉得罗老师不行，但是我们对罗老师印象其实挺好的，挠头。

不过呢，这个博主发的考试回忆还是挺准的，打消了不知道题型带来的考试懵逼感。

把考前复习整理的放在下面吧

数学基础

内积与范数

$n$ 维实向量集合 $\mathbb R^n$ 上，$\forall x=(x_1,x_2,\cdots,x_n)^\intercal\in\mathbb R^n$，$y=(y_1,y_2,\cdots,y_n)^\intercal\in \mathbb R^n$的标准内积： \[ \left<x,y\right>=x^\intercal y=\sum_{i=1}^n x_iy_i \]

范数的定义：满足以下条件的函数 $f:\mathbb R^n\to\mathbb R$ 称为范数

非负：$\forall x\in \mathbb R^n$，有 $f(x)\ge 0$；
正定：若 $f(x)=0$，则 $x=0$；
齐次：$\forall x\in \mathbb R^n$ 和 $t\in\mathbb R$，有 $f(tx)=|t|f(x)$；
三角不等式：$\forall x, y\in\mathbb R^n$，有 $f(x+y)\le f(x)+f(y)$

$l_p$ 范数（$p\ge 1$）： \[ \|x\|_p=\left(\sum_{i=1}^n |x_i|^p\right)^\frac{1}{p} \] $p=2$ 时称 Euclid 范数，$p=\infty$ 时称 Chebyshev 范数；“$l_0$ 范数”：向量中非零元的个数

Cauchy-Schwartz 不等式：$\forall x,y\in \mathbb R^n$，有 \[ |\left<x,y\right>|\le\|x\|_2\|y\|_2 \]

$P$-二次范数：$P\in S^n_{++}$（对称正定） \[ \|x\|_P=\sqrt{x^\intercal P x}=\|P^{\frac{1}{2} }x\|_2 \] 其单位球为椭球

范数等价性：对于所有 $\mathbb R^n$ 上范数 $\|\cdot\|_a$，$\|\cdot\|_b$，存在正常数 $\alpha$，$\beta$ 使对所有 $x\in \mathbb R^n$ 有 $\alpha\|x\|_a\le\|x\|_n\le\beta\|x\|_a$

对偶范数

令 $\|\cdot\|$ 是 $\mathbb R^n$ 上范数，其对偶范数 $\|\cdot\|_*$ 定义为 \[ \|z\|_* =\sup\{z^\intercal x: \|x\|\le 1\} =\sup\{z^\intercal x: \|x\|=1\} \] $l_p$ 范数的对偶为 $l_q$ 范数，$\frac{1}{p}+\frac{1}{q}=1$

P 范数的对偶范数 $\|z\|_*=\sup \{z^\intercal x\ |\ \|x\|_P=1\}=\|P^{-1/2}z\|_2$

求导与梯度

导数：$f:\mathbb R^n\to\mathbb R^m$ 的导数（Jacobian 矩阵）$Df(x)\in \mathbb R^{m\times n}$ 满足 \[ \lim_{z\to x\atop z\in\operatorname {dom} f, z\neq x} \frac{\|f(z)-f(x)-Df(x)(z-x)\|_2}{\|z-x\|_2}=0 \] 有 $Df(x)_{ij}=\dfrac{\partial f_i(x)}{\partial x_j}$（偏导数）

梯度 $\nabla f(x)=Df(x)^\intercal$

e.g., $\mathrm d\left(x^\intercal A x\right)=x^\intercal(A+A^\intercal)\mathrm dx$；

若有非奇异矩阵 $T$，令 $\bar f(y)=f(Tx)$，则 $\nabla\bar f(y)=T^\intercal\nabla f(y)$，$\nabla^2\bar f(y)=T^\intercal\nabla^2f(y)T$

实函数二阶导数：$f:\mathbb R^n\to\mathbb R$（Hessian 矩阵）为 \[ \nabla^2f(x)_{ij}=\frac{\partial^2f(x)}{\partial x_i\partial x_j} \]

二次逼近（在 $x_0$ 处二阶泰勒展开） \[ \hat f(x)=f(x_0)+\nabla f(x)^\intercal(x-x_0) +\frac{1}{2}(x-x_0)^\intercal\nabla^2f(x)(x-x_0) \] 有 $\hat f(x)=f(x)+o(\|x-x_0\|_2^2)$

梯度一阶近似 \[ \nabla f(x+d)\approx \nabla f(x) + \nabla^2 f(x)d \]

凸集合与凸函数

凸集

集合 $C\subset \mathbb R^n$ 称为凸集，如果 $\forall x,y\in C$ 及 $\forall \lambda\in [0,1]$，有 $z=\lambda x+(1-\lambda)y\in C$

集合保凸运算：交、闵科夫斯基和、仿射函数、透视函数 $P(z,t)=\dfrac{z}{t}$，$P:\mathbb R^n\times \mathbb R_{++}\to\mathbb R^n$

凸函数：令集合 $C$ 为凸集，如果 $\forall x,y\in C$ 及 $\forall \lambda\in [0,1]$，函数 $f:C\to \mathbb R$ 满足 $f(\lambda x + (1-\lambda)y) \le\lambda f(x) + (1-\lambda)f(y)$，则 $f$ 为凸函数

凸函数保凸运算：非负数乘、和、带权和、自变量仿射变换、对某几维求最小值、对（所有）非凸维求最大值、$\max$、作其透视函数 $g(x,t)=tf(x/t)$

凸函数一阶判定：$\forall x,y\in C$，$f(y)\ge f(x)+\nabla f(x)^\intercal(y-x)$

凸函数二阶判定：$\forall x\in C$，$\nabla^2 f(x)$ 为对称半正定矩阵

共轭函数：函数 $f:\mathbb R^n\to\mathbb R$ 的共轭函数 $f^*:\mathbb R^n\to\mathbb R$ 为仿射函数 $y^\intercal x$ 与 $f(x)$ 的最大差值，$f^*(y)=\sup (y^\intercal x-f(x))$；任意函数的共轭为凸函数

Jensen's Inequality：$f(E[x])\le E[f(x)]$

Min-Max 不等式：$\inf\limits_{z\in Z}\sup\limits_{w\in W} f(w,z) \ge \sup\limits_{w\in W}\inf\limits_{z\in Z} f(w,z)$；若满足等号则称 $f,W,Z$ 满足鞍点性质

线性代数

奇异矩阵：非满秩的方阵

优化问题

数学形式

\[ \begin {align} \min_x\ &f_0(x) \\ \text{s.t. } &f_i(x)\le 0, &i=1,2,\cdots,m \\ & h_j(x)=0, &j=1,2,\cdots,p \end{align} \]

目标函数、等式限制、不等式限制、可行解集

定义域 $\mathcal D=\bigcap_{i=0}^m\operatorname{dom} f_i \cap \bigcap_{i=1}^p\operatorname{dom}h_i$

凸优化问题：目标函数为凸函数，不等式限制函数为凸函数，等式限制函数为仿射函数

例子：线性规划、二次规划、二次函数限制的二次规划

优化问题的等价，增加松弛变量 $s_i\ge 0$ 将仿射函数不等式限制转为等式限制

局部最优解：若存在常数 $R>0$ 使 $x$ 是以下问题的最优解，则 $x$ 是一个局部最优解 \[ \begin {align} \min_z\ &f_0(z) \\ \text{s.t. } &f_i(z)\le 0, &i=1,2,\cdots,m \\ & h_j(z)=0, &j=1,2,\cdots,p \\ & \|z-x\|_2\le R \end{align} \]

对偶问题与最优性条件

对不等式约束引入拉格朗日乘子 $\lambda_i\in \mathbb R$，对等式约束引入拉格朗日乘子 $v_i\in \mathbb R$，记 $\lambda=(\lambda_1,\lambda_2,\cdots,\lambda_m)^\intercal$，$v=(v_1,v_2,\cdots,v_m)^\intercal$

拉格朗日函数 \[ L(x,\lambda, v)=f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^pv_ih_i(x) \] 拉格朗日对偶函数 \[ g(\lambda,v)=\inf_{x\in \mathcal D} L(x,\lambda,v) \] 线性函数是示性函数的下界，对偶函数是原问题最优解的下界，对偶函数是凹函数，$p^*\ge\max_{\lambda>0}\min_{x\in\mathcal D}L(x,\lambda,v)$

设 $f_0$ 的共轭函数为 $f_0^*$，不等式限制 $Ax\le b$，等式限制 $Cx=d$ 则对偶函数 $g(\lambda,v)=-f^*_0(-A^\intercal\lambda-C^\intercal v)-b^\intercal\lambda-d^\intercal v$

对偶问题 \[ \begin {align} \max_x\ &g(\lambda, v) \\ \text{s.t. } &\lambda \ge0 \end{align} \] 设对偶问题最优解 $d^*$，对偶间隙 $p^*-d^*$，弱对偶 $d^*\le p^*$ 对所有函数成立（$\inf\limits_{x\in\mathcal D}\sup\limits_{\lambda\ge 0} L\ge \sup\limits_{\lambda\ge 0}\inf\limits_{x\in\mathcal D} L$）；强对偶 $d^*=p^*$ 当凸优化问题满足 Slater 约束品性时成立

非启发式停止准则：对偶间隙 $f_0(x^{(k)})-g(\lambda^{(k)},v^{(k)})\le \varepsilon_{abs}$

Slater 约束品性：若存在集合 $\mathcal D$ 的一个内点 $x_0$，使得 $f_i(x_0)<0,\ i=1,2,\cdots,m$，$Ax_0=b$

通过解对偶问题求解原问题

若对偶问题存在解 $d^*=g(\lambda^*,v^*)$，且 $L(x,\lambda^*,v^*)$ 是 $x$ 的严格凸函数，则解优化问题 \[ \min_{x\in\mathcal D}L(x,\lambda^*,v^*) \] 若该问题解 $x^*$ 是原问题的可行解，则其为原问题的最优解；否则原问题不存在最优解

KKT 方程

（充要条件）假设原问题与对偶问题最优解可取得，分别为 $x^*$ 和 $(\lambda^*,v^*)$，且强对偶性成立，则 \[ \begin{cases} f_i(x^*)\le 0 ,& i=1,2,\cdots,m;\\ \lambda_i^*f_i(x^*)=0,& i=1,2,\cdots,m;\\ \lambda_i^*\ge 0,& i=1,2,\cdots,m;\\ h_i(x^*)=0,& i=1,2,\cdots,p;\\ \nabla f_0(x^*)+\sum_{i=1}^m\lambda_i^*\nabla f_i(x^*)+\sum_{i=1}^pv_i^*\nabla h_i(x^*)=0 \end{cases} \] 从上到下分别为

满足不等式限制
互补松弛性
对偶可行性条件
满足等式限制
对偶局部最小值

等式约束二次规划的 KKT 矩阵 \[ \begin{aligned} \min_x &\ \ \frac{1}{2}x^\intercal P x+q^\intercal x+r\\ \text{s.t.} &\ \ Ax=b \end{aligned} \] 其中 $P\in S_{++}^n$（$n$ 阶对称正定阵）。此问题 KKT 条件为 \[ \begin{cases} Ax=b\\ Px+q+A^\intercal v^*=0 \end{cases} \] 等价于线性方程 \[ \begin{bmatrix} P & A^\intercal\\ A & 0 \end{bmatrix} \begin{bmatrix} x^*\\ v^* \end{bmatrix}= \begin{bmatrix} -q\\ b \end{bmatrix} \]

无约束优化问题

\[ \min_x f(x) \]

其中 $f:\mathbb R^n \to \mathbb R$，假设 $f$ 是具有连续二阶导数的凸函数，最优解 $x^*=\arg\min f(x)$，最优值 $p^*=f(x)$，最优条件 $\nabla f(x^*)=0$

无约束最小化方法要求下水平集 $S=\{x|f(x)\le f(x^0)\}$ 是闭集

强凸性假设

Hessian 下界：存在 $m>0$ 使得 $\forall x\in S$，$\nabla ^2 f(x)\ge mI$

则 $f(x)-p^*\le\frac{1}{2m}\|\nabla f(x)\|_2^2$

（证明：任意 $y$，在 $x$ 展开，有 $f(y)\ge f(x)-\frac{1}{2m}\|\nabla f(x)\|_2^2$）

且 $\|x-x^*\|_2\le\frac{2}{m}\|\nabla f(x)\|_2$

（证明：$f(x^*)$ 在 $x$ 展开，柯西不等式）

上界

Hessian 上界：存在存在 $M>0$ 使得 $\forall x\in S$，有 $\nabla^2 f(x)\le MI$

则 $f(x)-p^*\ge\frac{1}{2M}\|\nabla f(x)\|_2^2$

（证明：$f(y)$ 在 $x$ 处展开，两边对 $y$ 求极小）

下降方法

产生优化点列 $x^{(k)}$，$k=1,2,3,\cdots$，其中 $x^{(k+1)}=x^{(k)}+t^{(k)}d^{(k)}$

下降方向 $d^{(k)}$ 满足 $\nabla f(x^{(k)})^\intercal d^{(k)}<0$

（$\exists t^{(k)}$，使得 $f(x^{(k+1)})=f(x^{(k)}+t^{(k)}d^{(k)})<f(x^{(k)})$）

收敛时，迭代次数上界 \[ f(x^{K})-p^*\le \varepsilon \Longrightarrow K\ge \frac{\log\left((f(x^{(0)})-p^*)/\varepsilon\right)}{\log(1/c)} \] 其中

	非规范化回溯直线搜索	回溯直线搜索	非规范化精确直线搜索	精确直线搜索
$c$	$1-2m\alpha \tilde\gamma^2\min\left\{1,\frac{\beta\gamma^2}{M}\right\}$	$1-2m\alpha \min\left\{1,\frac{\beta}{M}\right\}$	$1-\frac{m\gamma^2\hat\gamma^2}{M}$	$1-\frac{m}{M}$

对于非规范化方向，存在 $\gamma,\tilde \gamma\in (0,1]$，使得 $\|x\|\ge \gamma\|x\|_2$，$\|x\|_*\ge\tilde\gamma\|x\|_2$

对于牛顿方法，阻尼牛顿阶段 $K_1\ge \dfrac{M^2L^2/m^5}{\alpha\beta\min\{1,9(1-2\alpha)^2\} }(f(x^{(0)})-p^*)$

（$0\le \eta\le \dfrac{m^2}{L}$，$\|\nabla f(x^{(k)})\|_2\ge \eta$）；

二次收敛阶段 $\|\nabla f(x^{(k)})\|_2\le\dfrac{L}{2m^2}\|\nabla f(x)\|_2^2$，认为 $K_2\ge 6$

（$\|\nabla f(x^{(k)})\|_2\le \eta\le 3(1-2\alpha)^2\dfrac{m^2}{L}$）

精确直线搜索

$t^{(k)}=\arg\min_{s\ge 0} f(x^{(k)}+sd^{(k)})$

改进值下界 $f(x^{(k)})-f(x^{(k+1)})\ge\dfrac{|\nabla f(x^{(k)})^\intercal d^{(k)}|}{2(d^{(k)})^\intercal\nabla^2f(x^{(k)})d^{(k)} }\ge\dfrac{\|\nabla f(x^{(k)})\|_2^2}{2M}$

又有 $f(x^{(k)})-p^*\le\frac{1}{2m}\|\nabla f(x^{(k)})\|_2^2$

则 $2m(f(x^{(k)})-p^*)\le \|\nabla f(x^{(k)})\|_2^2\le 2M(f(x^{(k)})-f(x^{(k+1)}))$

回溯直线搜索

$0<\alpha\le 0.5$，$0<\beta<1$

While $f(x^{(k)}+t^{(k)}\nabla f^{(k)})>f(x^{(k)})+\alpha t^{(k)}\nabla f(x^{(k)})^\intercal d^{(k)}$

$t^{(k)}:= \beta t^{(k)}$

End

只要 $0\le t\le \frac{1}{M}$ 即可满足回溯停止条件，则回溯直线搜索将终止于 $t=1$ 或 $t>\frac{\beta}{M}$

则改进值下界 $f(x^{(k)})-f(x^{(k+1)})\ge\min\{1,\frac{\beta}{M}\}\alpha\|\nabla f(x^{(k)})\|_2^2$

最速下降方法

规范化最速下降方向（给定某范数） \[ d^{(k)}_{nsd}=\arg\min_d \{\nabla f(x^{(k)})^\intercal d\ |\ \|d\|=1\} \] 有 $\nabla f(x^{(k)})^\intercal d^{(k)}_{nsd}=-\|\nabla f(x^{(k)})\|_*$

非规范化最速下降方向 \[ d_{sd}^{(k)}=\|\nabla f(x^{(k)})\|_* d_{nsd}^{(k)} \]

采用 $l_1$ 范数的下降即坐标下降（收敛性证明见作业）

牛顿下降方法

\[ d_{nt}^{(k)}=-\nabla^2f(x^{(k)})^{-1}\nabla f(x^{(k)}) \]

有 $\arg\min_v \hat f(x^{(k)}+v)=-\nabla^2f(x^{(k)})^{-1}\nabla f(x^{(k)})$

是梯度线性近似的根：$f(x^{(k)}+v)\approx\nabla f(x^{(k)})+\nabla^2 f(x^{(k)})v=0$

是 Hessian 范数（P 范数）下的非规范化最速下降方向

牛顿减少量 \[ \begin{aligned} \lambda(x^{(k)})&= \sqrt{\nabla f(x^{(k)})^\intercal\nabla^2f(x^{(k)})^{-1}\nabla f(x^{(k)})} \\ &=\sqrt{-\nabla f(x^{(k)})^\intercal d_{nt}^{(k)} } \\ &=\sqrt{ {d_{nt}^{(k)} }^\intercal \nabla^2 f(x^{(k)}) d_{nt}^{(k)} } \end{aligned} \] $\dfrac{1}{2}\lambda(x^{(k)})^2$ 是在 $x^{(k)}$ 处二阶近似对 $f(x)-p^*$ 做出的估计

停止准则：$\frac{1}{2}\lambda(x^{(k)})^2\le \varepsilon$

牛顿回溯直线搜索（要求 $\alpha<\dfrac{1}{2}$）

While $f(x^{(k)}+t^{(k)}d_{nt}^{(k)})>f(x^{(k)})-\alpha t^{(k)}\lambda(x^{(k)})^2$

$t^{(k)}:= \beta t^{(k)}$

End

牛顿步径对座标的仿射变换是独立的

收敛阶段

假设：

强凸性
Hessian 矩阵 Lipschitz 连续，$\|\nabla^2f(y)-\nabla^2f(x)\|_F\le L\|y-x\|_2$

存在 $0<\eta\le\dfrac{m^2}{L}$ 和 $\gamma>0$

阻尼牛顿阶段：$\|\nabla f(x^{(k)})\|_2\ge \eta$，则 $f(x^{(k)})-f(x^{(k+1)})\ge \gamma$

二次收敛阶段：$\|\nabla f(x^{(k)})\|_2< \eta$，则 $\dfrac{L}{2m^2}\|\nabla f(x^{(k+1)})\|_2\le\left( \dfrac{L}{2m^2}\|\nabla f(x^{(k+1)})\|_2\right)^2$

且 $\|\nabla f(x^{(k)})\|_2< \eta\le 3(1-2\alpha)\dfrac{m^2}{L}$ 时有 $t^{(k)}=1$

等式约束优化问题

\[ \begin{aligned} \min_x &\ \ f(x)\\ \text{s.t.} &\ \ Ax=b \end{aligned} \]

其中 $A\in \mathbb R ^{p\times n}$，$\operatorname{rank}(A)=p<n$

消除方法

参数化（仿射）可行集： $\{x|Ax=b\}=\{Fz+\hat x|z\in \mathbb R^{n-p}\}$

$x f $ 是满足 $A\hat x=b$ 的任意特殊解

消除矩阵 $F\in\mathbb R^{n\times (n-p)}$ 是值域为 $A$ 的零空间（$Ax=0$ 的 $n-p$ 个线性无关一维解）的任何矩阵，也就是说，$\mathcal R(F)=\mathcal N(A)$，$AF=0$。

则转化为以下无约束问题 \[ \min_{z\in R^{n-p} } f(Fz+\hat x) \] 简化问题的牛顿方向 $d_z=-(F^\intercal\nabla^2 f(Fz+x)F)^{-1}F^\intercal\nabla f(Fz+x)$

$v^*=-(AA^\intercal)^{-1}A\nabla f(x^*)$ 为一个最优对偶变量

（证明对偶可行性条件 $\nabla f(x^*)+A^\intercal v^*=0$，左乘非奇异矩阵 $\begin{bmatrix}F^\intercal \\ A\end{bmatrix}$）

求矩阵 $F$ 亦可选取初等列变换矩阵 $P$ 使得 $\tilde A=AP=\begin{bmatrix}A_1&A_2\end{bmatrix}$ 前 $p$ 个列向量线性无关，令 $\tilde A\tilde x=\begin{bmatrix}A_1&A_2\end{bmatrix}\begin{bmatrix}\tilde x_1\\\tilde x_2\end{bmatrix}=b$，有 \[ x=P\tilde x=P \left( \begin{bmatrix}-A_1^{-1}A_2\\I\end{bmatrix}\tilde x_2 + \begin{bmatrix}-A_1^{-1}b\\0\end{bmatrix} \right) \]

对偶方法

目标函数的对偶函数是 $g(\lambda,v)=-f^*_0(-A^\intercal\lambda-C^\intercal v)-b^\intercal\lambda-d^\intercal v$，其中 $f^*$ 是 $f_0$ 的对偶函数

则对偶问题是 \[ \max_v -f^*(-A^\intercal v)-b^\intercal v \] 则可求解关于 $v$ 的无约束最优化问题，Slater 条件成立，得 $g(v^*)=p^*$，再求解以下无约束最优化问题得到原问题的最优条件 $x^*$ \[ \min_x f(x)+(v^*)^\intercal (Ax-b) \]

直接求解（Newton 方法）

可行初始点

牛顿方向 $d_x$ 为等式约束的二次近似模型的极小解（$f(x+d)$ 在 $x$ 处展开） \[ \begin{aligned} \min_d &\ \ \frac{1}{2}d^\intercal \nabla^2 f(x) d+\nabla f(x)^\intercal d+f(x)\\ \text{s.t.} &\ \ Ad=0 \end{aligned} \] 得 KKT 方程 \[ \begin{bmatrix} \nabla^2 f(x) & A^\intercal\\ A & 0 \end{bmatrix} \begin{bmatrix} d_x\\ w \end{bmatrix}= \begin{bmatrix} -\nabla f(x)\\ 0 \end{bmatrix} \] 其中 $w$ 是该问题的最优对偶变量

等式约束问题的牛顿方法与简化后无约束问题牛顿方法的迭代过程完全一致：

令 $d_x=Fd_z$，其能满足 KKT 方程，其中 $w=-(AA^\intercal)^{-1}A(\nabla f(x^*)+\nabla^2f(x)d_x)$；

减少量相等：$\tilde \lambda(z)^2=d_z^\intercal\nabla^2\tilde f(z)d_z=d_z^\intercal F^\intercal\nabla^2f(x)Fd_z=d_x^\intercal\nabla^2 f(x)d_x=\lambda(x)^2$.

其中 $x=Fz+\hat x$

不可行初始点

假设 $x+d_x$ 满足最优性条件 $A(x+d_x)=b$，$\nabla f(x+d_x)+A^\intercal w=0$；利用梯度一阶近似，有 $\nabla f(x+d_x)=\nabla f(x)+\nabla^2f(x)d_x$，则得到方程组 \[ \begin{bmatrix} \nabla^2 f(x) & A^\intercal\\ A & 0 \end{bmatrix} \begin{bmatrix} d_x\\ w \end{bmatrix}= \begin{bmatrix} -\nabla f(x)\\ b-Ax \end{bmatrix} \] 原对偶解释：令 $y=[x\ v]^\intercal$，原对偶残差 \[ r(y)= \begin{bmatrix} \nabla f(x)+A^\intercal v\\ Ax-b \end{bmatrix} \triangleq \begin{bmatrix} r_{dual}(y)\\ r_{pri}(y) \end{bmatrix} \] 原残差 $r_{\text{pri} }(x,v)=Ax-b$，对偶残差 $r_{\text{dual} }(x,v)=\nabla f(x)+A^\intercal v$；

对原对偶残差使用一阶近似，$r(y+\Delta y)\approx r(y)+Dr(y)\Delta y$，可以得到 \[ \begin{bmatrix} \nabla^2 f(x) & A^\intercal\\ A & 0 \end{bmatrix} \Delta y= \begin{bmatrix} -\nabla f(x)-A^\intercal v\\ b-Ax \end{bmatrix} \] 整理一下得 \[ \begin{bmatrix} \nabla^2 f(x) & A^\intercal\\ A & 0 \end{bmatrix} \begin{bmatrix} d_x\\ v+d_v \end{bmatrix}= \begin{bmatrix} -\nabla f(x)\\ b-Ax \end{bmatrix} \] 有 $w=v^+=v+d_v$

原问题等价于找到原对偶残差为零的点，停止准则 $\|r(x^{(k)},v^{(k)})\|_2\le \varepsilon$

While $\|r(x^{(k)}+td_x^{(k)}, v^{(k)}+td_v^{(k)})\|_2>(1-\alpha t)\|r(x^{(k)},v^{(k)})\|_2$

$t^{(k)}:= \beta t^{(k)}$

End

收敛性分析

假设

$S=\{(x,v)\ |\ x\in\operatorname {dom} f,\|r(x,v)\|_2<\|r(x^{(0)},v^{(0)})\|_2\}$ 是闭集
KKT 逆矩阵有界（$\le K$）
Lipschitz 条件：存在 $L$ 满足导数差的范数比 $L$ 倍线性函数小

阻尼牛顿阶段 $\|r(y^{(k)})\|_2>\frac{1}{K^2L}$，二次收敛阶段 $\|r(y^{(k)})\|_2\le \frac{1}{K^2L}$

等式不等式约束优化问题

\[ \begin {align} \min_x\ &f_0(x) \\ \text{s.t. } &f_i(x)\le 0, &i=1,2,\cdots,m \\ & Ax=b \end{align} \]

函数 $f_i:\mathbb R^n\to \mathbb R$ 为二次连续可微凸函数；
定义域 $D=\bigcap_{i=0}^m \operatorname {dom} f_i$；
$A\in \mathbb R^{p\times n}$，$\operatorname{rank} (A)=p<n$；
$p^*=f(x^*)$ 是原问题的解。

示性函数 \[ I_{-}(u)= \begin{cases} 0, &u\le 0 \\ \infty, & u > 0 \end{cases} \] 将不等式限制转化为示性函数 \[ \begin {align} \min_x&\ \ f_0(x)+\sum_{i=1}^{m} I_{-}(f_i(x)) \\ \text{s.t.}&\ \ Ax=b \end{align} \] 示性函数不可微，则使用近似示性函数代替（$t$ 越大，近似精度逐渐增加） \[ \hat I_{-}(u)=-\frac{1}{t}\log(-u) \] 记对数障碍函数 $\phi(x)=-\sum_{i=1}^m\log(-f_i(x))$，有

$\nabla \phi(x)=\sum_{i=1}^m\dfrac{\nabla f_i(x)}{-f_i(x)}$
$\nabla^2\phi(x)=\sum_{i=1}^m\dfrac{\nabla f_i(x)\nabla f_i(x)^\intercal}{f_i(x)^2}+\sum_{i=1}^m\dfrac{\nabla^2 f_i(x)}{-f_i(x)}$

不等式线性规划 $Ax\le b$ 的障碍函数 $\phi(x)=-\sum_{i=1}^m\log(b_i-a_i^\intercal x)$

$\nabla\phi(x)=\sum_{i=1}^{m}\dfrac{a_i}{b_i-a_i^\intercal x}=A^\intercal d$
$\nabla^2\phi(x)=\sum_{i=1}^{m}\dfrac{a_ia_i^\intercal}{(b_i-a_i^\intercal x)^2}=A^\intercal\operatorname{diag}(d)^2A$

其中 $d_i=1/(b_i-a_i^\intercal x)$

中心路径

\[ \begin {align} \min_x&\ \ tf_0(x)+\phi(x) \\ \text{s.t.}&\ \ Ax=b \end{align} \]

假定 $\forall t>0$ 该问题能用牛顿方法求解，唯一解 $x^*(t)$

中心路径：$\{x^*(t)\ |\ t>0\}$，满足（KKT条件）

严格可行性 $Ax^*(t)=b$，$f_i(x^*(t))<0$
存在 $\hat v\in\mathbb R^p$ 使得 $t\nabla f_0(x^*(t))+\nabla\phi(x^*(t))+A^\intercal \hat v =0$

现在来研究原对偶问题的原对偶可行性，有 $\lambda^*_i(t)=-\dfrac{1}{t f_i(x^*(t))}$，$v^*(t)=\hat v /t$，使得 $\nabla f_0(x^*(t))+\sum_{i=1}^m\lambda_i^*(t)\nabla f_i(x^*(t))+ A^\intercal v^*(t)=0$；则 $\lambda^*,v^*$ 为对偶可行解

而对偶函数 \[ \begin{aligned} g(\lambda^*(t), v^*(t))&=f_0(x^*(t))+\sum_{i=1}^m\lambda_i^*(t)f_i(x^*(t))+ v^*(t)^\intercal(Ax^*(t)-b)\\ &= f_0(x^*(t))-\frac{m}{t} \end{aligned} \] 则对偶间隙 $m/t$，随着 $t$ 增大而收敛

修改的 KKT 方程 \[ \begin{cases} f_i(x^*)\le 0 ,& i=1,2,\cdots,m;\\ -\lambda_i^*f_i(x^*)=\dfrac{1}{t},& i=1,2,\cdots,m;\\ \lambda_i^*\ge 0,& i=1,2,\cdots,m;\\ Ax=b\\ \nabla f_0(x^*)+\sum_{i=1}^m\lambda_i^*\nabla f_i(x^*)+A^\intercal v=0 \end{cases} \] 牛顿步径（等价于求解修改的 KKT 方程一阶线性逼近） \[ \begin{bmatrix} t\nabla^2 f_0(x)+\nabla^2\phi(x) & A^\intercal \\ A & 0 \end{bmatrix} \begin{bmatrix} d_x \\ d_v \end{bmatrix} =-\begin{bmatrix} t\nabla f_0(x) + \nabla\phi(x)\\ 0 \end{bmatrix} \]

障碍方法

给定 $t^{(0)}$，$\mu>1$，$\varepsilon > 0$，外循环迭代 $t^{(k+1)}=\mu t^{(k)}$ 直到 $m/t\le\varepsilon$

外层迭代次数 $N\ge \left\lceil\dfrac{\log\frac{m}{\varepsilon t^{(0)} }}{\log \mu}\right\rceil$ 时满足精度要求

阶段 1 方法

确定 $x$ 满足 $f_i(x)\le 0$，$i=1,2,\cdots,m$ 且 $Ax =b$

情况一

已知 $x^{(0)}\in \bigcap \operatorname {dom} f_i$，且 $Ax^{(0)}=b$，则用障碍方法求解阶段 1 优化问题（极小化不可行值的最大值） \[ \begin {align} \min_{x,s}&\ \ s \\ \text{s.t.}&\ \ f_i(x)\le s,\ (i=1,2,\cdots, m) \\ & \ \ Ax=b \end{align} \] 记目标最优值 $\bar p^*$：

$\bar p^*<0$ 则有严格可行解
$\bar p^*>0$ 则不可行
$\bar p^*=0$ 则不等式组可行但不存在严格可行解，如果 $\bar p^*$ 不可取到，则不等式组不可行

可加入限制条件 $f_0(x)\le M$（有限制的极小化不可行值的最大值），其中 $M\ge\max\{f_0(x^{(0)}), p^*\}$

也可以将问题构造为极小化不可行值之和

情况二

已知 $x^{(0)}\in \bigcap \operatorname {dom} f_i$，但不满足 $Ax^{(0)}=b$，则用不可行初始点牛顿方法求解 \[ \begin {align} \min_{x,s}&\ \ t^{(0)}f_0(x)-\sum_{i=1}^{m}\log(s-f_i(x)) \\ \text{s.t.}&\ \ Ax=b,\ s=0 \\ \end{align} \]

情况三

不能在 $\bigcap \operatorname {dom} f_i$ 中确定一点，用不可行初始点牛顿方法求解 \[ \begin {align} \min_{x,s}&\ \ t^{(0)}f_0(x+z_0)-\sum_{i=1}^{m}\log(s-f_i(x+z_i)) \\ \text{s.t.}&\ \ Ax=b,\ s=0,\ z_i=0 \\ \end{align} \]

原对偶内点法

仅有一层迭代，原对偶迭代值不需要可行；由修改的 KKT 条件定义对偶-中心-原残差 \[ r_{t}(x,\lambda,v)= \begin{bmatrix} r_{\text{dual} }\\ r_{\text{cent} }\\ r_{\text{pri} } \end{bmatrix} =\begin{bmatrix} \nabla f_0(x) + \nabla f(x)\lambda+A^\intercal v\\ -\operatorname{diag}(\lambda) f(x)-(1/t)1\\ Ax-b \end{bmatrix} \] 由下式计算原对偶搜索方向 $\Delta y_{\text{pd} }$（牛顿步径）

\[ \begin{bmatrix} \nabla^2 f_0(x)+\sum_{i=1}^m\lambda_i\nabla^2 f_i(x) & \nabla f(x) & A^\intercal\\ -\operatorname{diag}(\lambda) \nabla f(x)^\intercal &-\operatorname{diag}(f(x)) & 0\\ A & 0 & 0 \end{bmatrix} \begin{bmatrix} \Delta x\\ \Delta \lambda\\ \Delta v \end{bmatrix} = \begin{bmatrix} r_{\text{dual} }\\ r_{\text{cent} }\\ r_{\text{pri} } \end{bmatrix} \]

代理对偶间隙 $\hat\eta (x,\lambda)=-f(x)^\intercal \lambda$

步骤：

while $\|r_{\text{pri} }\|,\|r_{\text{dual} }\|,\hat\eta>\varepsilon$

$t:=\mu m/\hat\eta$
计算 $\Delta y_{\text{pd} }$
确定步长，更新