ADMM

In this blog, we introduce the alternating direction method of multipliers (ADMM) for quadratic programming. This is the idea behind the well-known QP solver, OSQP. As usual, we consider the following convex quadratic program

\[\begin{equation} \label{eq:qp_formulation} \begin{aligned} \min_x\; &\frac{1}{2} x^\top Q x + c^\top x \\ \text{s.t.}\; & Ax \in \mathcal{C}, \end{aligned} \end{equation}\]

where $A \in \mathbb{R}^{m \times n}$, $Q \in \mathbb{R}^{n \times n}$ is positive semi-definite, and

\[\mathcal{C} := \left\{ z \mid l \leq z \leq u \right\}\]

is a convex set. By using the indicator function, we rewrite \eqref{eq:qp_formulation} as

\[\begin{equation} \label{eq:qp_formulation_v1} \min_x\; \frac{1}{2} x^\top Q x + c^\top x + \mathcal{I}_{\mathcal{C}}(Ax), \end{equation}\]

where the indicator function is given by

\[\mathcal{I}_{\mathcal{C}}(z) = \begin{cases} 0 & \text{if } z \in \mathcal{C} \\ +\infty & \text{otherwise}. \end{cases}\]

To solve \eqref{eq:qp_formulation_v1}, we first consider using projected gradient descent. However, this is not an ideal choice, as projecting onto a convex set is typically a nontrivial task. To overcome this challenge, we decompose the expensive projection into two relatively cheap ones. By introducing a new decision variable $z$, we reformulate \eqref{eq:qp_formulation} as

\[\begin{equation} \label{eq:qp_formulation_v2} \begin{aligned} \min_{x, z}\; &\frac{1}{2} x^\top Q x + c^\top x + \mathcal{I}_{\mathcal{C}}(z) \\ \text{s.t.}\; & Ax = z. \end{aligned} \end{equation}\]

The core idea is to optimize over $x$ and $z$ alteratively. However, we now encounter another issue: the matrix $A$ is likely to be rank-deficient. To address this, as mentioned in our previous blog, we relax the equality constraint in \eqref{eq:qp_formulation_v2} using the augmented Lagrangian method. Then, we minimize the corresponding augmented Lagrangian function:

\[\min_{x, z}\; \frac{1}{2} x^\top Q x + c^\top x + \mathcal{I}_{\mathcal{C}}(z) + \dfrac{\rho}{2} \Vert Ax - z + \rho^{-1} y \Vert^2,\]

where $\rho > 0$ is a scalar penalty weight and $y$ is the dual variable associated with the equality constraint. Let the superscript $k$ denote the iteration index. We first optimize over $x$ as follows:

\[\begin{aligned} x^{k+1} &\leftarrow \arg\min_{x} \left\{ \frac{1}{2} x^\top Q x + c^\top x + \dfrac{\rho}{2} \Vert Ax - z^k + \rho^{-1} y^k \Vert^2 \right\} \\ &\quad = - \left( Q + \rho A^\top A \right)^{-1} \left( c + A^\top \left( y^k - \rho z^k \right) \right) \end{aligned}\]

Given $x^{k+1}$, we then optimize over $z$:

\[\begin{aligned} z^{k+1} \leftarrow &\arg\min_{z} \left\{ \mathcal{I}_{\mathcal{C}}(z) + \dfrac{\rho}{2} \Vert Ax^{k+1} - z + \rho^{-1} y^k \Vert^2 \right\} \\ &\arg\min_{z} \left\{ \mathcal{I}_{\mathcal{C}}(z) + \dfrac{\rho}{2} \Vert z - \left(Ax^{k+1} + \rho^{-1} y^k\right) \Vert^2 \right\} \\ &= \Pi_{\mathcal{C}} \left( Ax^{k+1} + \rho^{-1} y^k \right), \end{aligned}\]

where the projection operator $\Pi_{\mathcal{C}}$ is defined as

\[\Pi_{\mathcal{C}}(v) = \arg\min_{z \in \mathcal{C}} \| z - v \|^2.\]

For a box set $\mathcal{C}$, the projection simplifies to:

\[\Pi_{\mathcal{C}}(v) = \max(l, \min(v, u)).\]

Finally, given $x^{k+1}$ and $z^{k+1}$, we the dual variable $y$:

\[y^{k+1} \leftarrow y^k + \rho \left( Ax^{k+1} - z^{k+1} \right).\]

The overall ADMM algorithm for quadratic programming can be summarized as follows:

\[\begin{aligned} x^{k+1} &= - \left( Q + \rho A^\top A \right)^{-1} \left( c + A^\top \left( y^k - \rho z^k \right) \right) \\ z^{k+1} &= \Pi_{\mathcal{C}} \left( Ax^{k+1} + \rho^{-1} y^k \right) \\ y^{k+1} &= y^k + \rho \left( Ax^{k+1} - z^{k+1} \right) \end{aligned}\]