Augmented Lagrangian Function for Semidefinite Programming Problems

Question

I am currently reading the paper "Alternating direction augmented Lagrangian methods for semidefinite programming" and was wondering about how one comes up with the Augmented Lagrangian Function that is presented in the paper (p. 207). When the standard SDP is defined as $$\min_{X \in S_n} \langle C, X \rangle \quad s.t. \quad \mathcal{A}(X)=b, X\succeq 0 $$ and its dual as $$\min -b^T y \quad s.t.\quad \mathcal{A}^*(y)+S=C, S\succeq 0$$ then the Augmented Lagrangian is defined as (according to the paper) $$\mathcal{L}_\mu(X, y, S)=b^Ty + \langle X, \mathcal{A}^*(y)+S-C\rangle + \frac{1}{2\mu}\|\mathcal{A}^*(y)+S-C\|_F^2$$

I'm finding it a bit hard to interpret the Augmented Lagrangian/understand the intuition behind it.

$-b^T y$ is the original objective (which makes sense to me).

$\frac{1}{2\mu}\|\mathcal{A}^*(y)+S-C\|_F^2$ looks like a regularization term (also makes sense to me - we want to keep the violation of the constraint in the dual problem small)

$\langle X, \mathcal{A}^*(y)+S-C\rangle$ is the bit I really don't understand...so this enforces orthogonality between the primal iterate and the violation of the dual constraint...but why? The primal iterate doesn't even appear in the dual problem so how can it become part of the Lagrangian?

Can someone maybe explain how one comes up with this Augmented Lagrangian function for the SDP by using the original notion of the Lagrange function as explained on Wikipedia or at least explain the "orthogonality" condition?

Answer 1

My way of reading it is $\langle X, \mathcal{A}^*(y)+S-C\rangle = \langle X, \mathcal{A}^*(y)-C\rangle + \langle X,S \rangle$. The first term is your standard inner product between dual variable and original primal constraints which you append to the objective in an augmented lagrangian method, and the second term which appeared here since they work with a slack is zero at optimality if the equality hold and complementary slackness has been achieved.

Answer 2

There's a good discussion of this in Convex Optimization by Stephen Boyd and Lieven Vandenberghe. See section 5.9.

With an ordinary scalar inequality constraint:

$f_{i}(x) \leq 0$,

you'll have a term $\lambda_{i}f_{i}(x)$ in the Lagrangian. Note that $\lambda$ is required to be nonnegative so that the product will be nonnegative if the inequality is violated. The complementary slackness condition is that $\lambda_{i}f_{i}(x)=0$ at optimality.

However, with a conic inequality

$f_{i}(x) \preceq 0$,

You can't multiply $\lambda_{i}f_{i}(x)$ because the result will not be a scalar and can't be added to $f_{0}(x)$. Rather, you need to use a conic inner product between the Lagrange multiplier (which most live in the dual cone) and $f_{i}(x)$. The complementary slackness condition is that the inner product of the Lagrange multiplier with $f_{i}(x)$ is 0.