ADMM 交替方向乘子法

前言

• ADMM by Boyd, 2010
• 收敛速率和算法复杂度分析可见南大何教授的分析 主页
• 对于基础知识，建议简要阅读一下 Boyd 的凸优化。(Convex Optimization, Stephen Boyd)

等式约束优化问题

拉格朗日乘子法

• 即求 $\min f(x) \ \ s.t.g_i(x)=0$
  使用拉格朗日乘子 $\ L(x,\lambda)=f(x)+\sum\lambda_i g_i(x)$ ，使 $$\frac{\partial L}{\partial x}=\frac{\partial L}{\partial \lambda_i}=0$$ 可以得到最优解。
• 即多元微积分中求多元函数的条件极值。

罚函数

• 即求 $\min f(x) \ \ s.t.g_i(x)=0$ 。
  引入惩罚因子 $\sigma$ 与增广函数 $P$ ，有 $\min F(x,\sigma)=f(x)+\sigma P(x)$
  其中 $\sigma$ 取很大的正数， $P=g^T g$ 。增广函数指示偏离约束的程度，并由一个很大的惩罚因子给予惩罚。由此求解的极值几乎不会脱离约束。

增广拉格朗日乘子法 Augmented Lagrange Method

• 在拉格朗日函数中引入罚函数，具体形式见后。

共轭问题和对偶问题

共轭问题

• $f(x): R^n\rightarrow R$
• $f^*(y): R^n\rightarrow R$
• $f^*(y)=\sup_{x\in D}(y^Tx-f(x))$
• (重要) $f^*(y)$ 一定是凸的。这是因为逐点最大和逐点上确界操作是保凸的。在 $y\in R$ 的情况下， $f^*$ 相当于遍历仿射函数 $yx(kx)$ 的斜率，并取 $kx+b$ 与 $f(x)$ 相交的时候最小的 $b$ ($b=-f(x)$)。
• (重要) 若 $f$ 是凸的且可微，则使 $y^Tx-f(x)$ 取最大的 $x^*$ 满足 $y=\triangledown f(x^*)$（遍历的仿射函数和 $f(x)$ 相切）。即，给定任意 $y$ ，可以求解梯度方程 $y=\triangledown f(z)$ 得到 $y$ 处共轭函数 $f^*(y)$
• 此处 $x$ 带有 $\sup$ 即要对 $x$ 做遍历，所以并不是常数。

拉格朗日对偶函数

• $g(\lambda,t)=\inf_{x\in D}L(x,\lambda,\nu)$
• 由于$\inf$的影响，$g$ 只能在一系列 $x$ 的取值中取最小的 $g(\lambda,\nu)$ 中取，是一族关于 $(\lambda,\nu)$ 的仿射函数的逐点下确界，是一定凸的。
  所以对 $g(\lambda,\nu)=\min L(x,\lambda,\nu)\leq \minx \max{\lambda,\nu} L(x,\lambda,\nu)=\min f(x)$ 恒成立
• 拉格朗日对偶函数给出了优化问题的最优值的一个下界 $(d^*\leq p^*)$

线性约束下两者关系

$\min f(x),s.t. Ax=a, Bx\leq b.$
$L(x,\lambda,t)=f(x)+\lambda(Ax-a)+\nu(Bx-b)$
对偶函数 $g(\lambda,\nu)=\inf{x\in D} L(x,\lambda,\nu)=-\lambda a-\nu b-\sup{x\in D}[(-\lambda A-\nu B)x-f(x)]$
$=-\lambda a-\nu b-f^*(-\lambda A-\nu B)$

对偶问题

• $\max g(\lambda,\nu ),\ \ s.t.\ \ \lambda,\nu \geq 0.$
• 对偶问题的引出是因为 $g(\lambda,\nu)$ 描述一个最优值的下界，那么 $\max g(\lambda,\nu)$ 则是最优值的最好下界。
• $\lambda,\nu$ 可代回 $L(x,\lambda,\nu)$ 对 $x$ 求 $\min L.$
• 此问题是无约束问题，拉格朗日方程不带约束项。这一过程消除了约束的限制(并入 $g$ 中)。且对偶问题一定是一个凸优化问题。
• 注意强对偶条件下对偶问题的解才和原问题解相同。凸优化问题满足Slater条件，即凸优化问题存在严格可行解（约束中的仿射函数不等式约束满足严格小于），问题具有强对偶性质。Slater条件确保原函数存在鞍点（？）。
• 凸问题下满足KKT条件的点 $\tilde{x},\tilde{\lambda},\tilde{\nu}$ ， $\tilde{x}$ 和 $(\tilde{\lambda},\tilde{\nu})$ 分别是原问题和对偶问题的最优解，且对偶间隙为0。

ADMM与相关优化算法

对偶上升法 Dual Ascent Method

• 使用梯度上升法更新 $\lambda$ 和 $\nu$ 。不断迭代求对偶问题的最优解（最大值，故用上升法）。每次更新 $\lambda$ 和 $\nu$ 都可以从此带入 $L$ 求出一个新的 $x$ ，此时得到一条新曲线（也可能是原曲线，但永远不会在原曲线上方），可以得到新的对偶问题继续更新 $\lambda$ 和 $\nu$ 。

• $\lambda, \nu$ 的上标表示迭代次数，在迭代中不断将解更新为满足不同约束条件的解。(剩余约束条件是多余的)(等式约束对所有可行解都是起作用的)

• 原问题：$\min f(x) \s.t. Ax=b$
  其拉格朗日函数为：

  $$L(x,\lambda)=f(x)+\lambda^T(Ax-b)$$

  对偶函数为：

  $$\begin{align} g(\lambda)&=\inf_x L(x,\lambda)=\inf_x (f(x)+\lambda^T(Ax-b))\\&=-\sup_x (-f(x)-\lambda^TAx)-\lambda^Tb\\&=-f^※(-A^T\lambda)-b^T\lambda \end{align}$$

  对偶问题：$\max g(\lambda)$
  在强对偶条件成立的情况下，原问题最优解(minimizer) $x^*$ 可以通过 $y^*$ (即上述 $\lambda^*$) 使用下式计算：
  $x^*=\arg\min_x L(x,\lambda^*)$ 。

• 若 $g$ 可微，对任意点 $(x,\lambda)$ ，令（有?） $x^+=\arg\min_xL(x,y)$ ,则其梯度 $\triangledown g(y)=Ax^+-b$ ，则点的迭代（即梯度上升迭代）式如下：

  $$\begin{align} x^{k+1}&:=\arg\min_x L(x,y^k)\\ y^{k+1}&:=y^k+\alpha^k(Ax^{k+1}-b) \end{align}$$

  利用梯度上升迭代更新对偶问题的答案 $y$ ，并用 $y$ 反过来更新 $x$ 。 $\alpha^k>0$ 是步长，所有上标都为迭代计数器。

• 若 $f$ 为 $x$ 的任何分量的非零仿射函数，则 $x$ 无法更新，因为大多数情况下 $L$ 对 $x$ 无界（例 $y=kx+b$ 在 $k\neq0$ 时 $y$ 无下界）。

对偶分解法 Dual Decomposition

• 对 $x$ 的更新可以并行执行。

增广拉格朗日乘子法 Augmented Lagrange Method

• 在拉格朗日函数中引入二次罚函数因子（即二次正则项，设约束为线性约束） $$L_\rho(x,y)=f(x)+y^T(Ax-b)+(\rho/2)||Ax-b||^2_2$$
• 迭代过程： $$\begin{align} x^{k+1}&:=\arg\min_x L_\rho(x,y^k)\\ y^{k+1}&:=y^k+\rho(Ax^{k+1}-b) \end{align}$$
• 由于二次惩罚项的存在无法并行更新 $x$

交替方向乘子法 Alternating Direction Method of Multipliers

ADMM 基本形式(Unscale form)

• ADMM将原来的变量 $x$ 分成 $x$ 和 $z$ 两部分。优化问题如下（一次等式约束）： $$\min f(x)+g(z)\\ s.t. Ax+Bz=c$$
• 最优值可表示为(?)： $$p^*=\inf\{f(x)+g(z)\ |\ Ax+Bz=c\}$$
• 其拉格朗日函数可表示为： $$L_\rho(x,z,y)=f(x)+g(z)+y^T(Ax+Bz-c)+(\rho/2)||Ax+Bz-c||^2_2$$
• 迭代过程： $$\begin{align} x^{k+1}&:=\arg\min_x L_\rho(x,z^k,y^k)\\ z^{k+1}&:=\arg\min_z L_\rho(x^{k+1},z,y^k)\\ y^{k+1}&:=y^k+\rho(Ax^{k+1}+Bz^{k+1}-c) \end{align}$$
• ADMM的可以并行迭代更新x,z

Scale form

• 定义残差(residual) $r=Ax+Bz-c$ 和 Scale dual variable $u=(1/\rho)y$ ，我们有 $$y^Tr+(\rho/2)||r||^2_2=(\rho/2)||r+(1/\rho)y||^2_2-(1/2\rho)||y||^2_2$$ ADMM迭代式可以重写为： $$\begin{align} x^{k+1}&:=\arg\min_x (f(x)+(\rho/2)||Ax+Bz^k-c+u^k||^2_2)\\ z^{k+1}&:=\arg\min_z (g(x)+(\rho/2)||Ax^{k+1}+Bz-c+u^k||^2_2)\\ u^{k+1}&:=u^k+Ax^{k+1}+Bz^{k+1}-c \end{align}$$ 即为ADMM的Scale form

停止条件

• 原变量满足收敛条件时残差必定满足收敛于0的条件，所以可以取 $$||r^k||_2\leq\epsilon^{pri}\ \ \ \ and\ \ \ \ ||s^k||_2\leq\epsilon^{dual}$$
• 其中的 $\epsilon$ 取法需满足一定条件，可见Boyd 2011论文式(3.12)部分。

对一般约束问题

• 优化问题如下： $$\min f(x)\\ s.t. x\in \mathcal{C}$$ 其中 $x\in R^n$ ，$f$ 和 $\mathcal{C}$ 都是凸的，转化为ADMM形式： $$\min f(x)+g(z)\\ s.t. x-z=0$$ 其中 $g$ 是 $\mathcal{C}$ 的指示函数（即 $x\in \mathcal{C}$ 则 $g(x)=0$ ，否则 $g(x)=+\infty$
  迭代式为： $$\begin{align} x^{k+1}&:=\arg\min_x (f(x)+(\rho/2)||x-z^k+u^k||^2_2)\\ z^{k+1}&:=\Pi_C(x^{k+1}+u^k)\\ u^{k+1}&:=u^k+x^{k+1}-z^{k+1} \end{align}$$ 其中 $\Pi_{\mathcal{C}(x)}$ 即 $x$ 在集合 $\mathcal{C}$ 上的欧几里得投影。

对非凸问题

• 优化问题如下： $$\min f(x)\\ s.t. x\in S$$ 其中 $f$ 凸而 $S$ 非凸，ADMM迭代式为： $$\begin{align} x^{k+1}&:=\arg\min_x (f(x)+(\rho/2)||x-z^k+u^k||^2_2)\\ z^{k+1}&:=\Pi_S(x^{k+1}+u^k)\\ u^{k+1}&:=u^k+x^{k+1}-z^{k+1} \end{align}$$ 对 $z$ 的更新由于 $S$ 的非凸性变得难以计算，但仍然有容易计算的特例存在：
  • 基数运算：
    如果 $S=\{x| card(x)\leq c\}$ ，其中 $card$ 给出集合中非零元的数量，那么 $\Pi_S(v)$ 是将 $v$ 的最大 $c$ 个元素保留并将其余元素置零。
  • 秩运算：
    如果 $S$ 是秩为 $c$ 的矩阵的集合，那么 $\PiS(v)$ 通过SVD计算并保留前 $c$ 对，即 $\Pi_S(v)=\sum^c{i=1}\sigma_i u_i v_i^T$
  • 布尔约束：
    如果 $S={x|xi\in{0,1}}$ ，那么 $\PiS(v)$ 直接取 0、1 中更近的那个。__整数约束可以被同样的方式处理。