Infeasibility Detection in the Alternating Direction Method of Multipliers for Convex Optimization

Abstract

The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they yield conclusive information regarding problem infeasibility for optimization problems with linear or quadratic objective functions and conic constraints, which includes quadratic, second-order cone, and semidefinite programs. In particular, we show that in the limit the iterates either satisfy a set of first-order optimality conditions or produce a certificate of either primal or dual infeasibility. Based on these results, we propose termination criteria for detecting primal and dual infeasibility.

Appendix A: Supporting Results

Lemma A.1

The first-order optimality conditions for problem (2) are conditions (3).

Proof

We first rewrite problem (2) in the form

$$\begin{aligned} \underset{(x,z)}{\mathrm{min}} \quad \left( \tfrac{1}{2}x^TP x + q^Tx + \mathcal {I}_\mathcal {C}(z) \right) \quad \mathrm{s.t.} \quad Ax=z \end{aligned}$$

and then form its Lagrangian

$$\begin{aligned} \mathcal {L}(x,z,y) :=\tfrac{1}{2}x^TP x + q^Tx + \mathcal {I}_\mathcal {C}(z) + y^T(Ax-z). \end{aligned}$$

(35)

Provided that the problem satisfies certain constraint qualification [15, Cor. 26.3], its solution can be characterized via a saddle point of (35). Therefore, the first-order optimality conditions can be written as [29, Ex. 11.52]

$$\begin{aligned} z&\in \mathcal {C} \\ 0&= -\nabla _x \mathcal {L}(x,z,y) = -(Px + q + A^Ty) \\ N_{\mathcal {C}}(z)&\ni \,-\nabla _z \mathcal {L}(x,z,y) = y \\ 0&= \nabla _y \mathcal {L}(x,z,y) = Ax - z. \end{aligned}$$

$\square$

Lemma A.2

The dual of problem (1) is given by problem (4).

Proof

The dual function can be derived from the Lagrangian (35) as follows:

$$\begin{aligned} g(y)&:=\inf _{(x,z)} \mathcal {L}(x,z,y) \\&= \inf _x \lbrace \tfrac{1}{2}x^TP x + (A^Ty + q)^Tx \rbrace + \inf _{z\in \mathcal {C}} \lbrace -y^Tz \rbrace \\&= \inf _x \lbrace \tfrac{1}{2}x^TP x + (A^Ty + q)^Tx \rbrace - \sup _{z\in \mathcal {C}} \lbrace y^Tz \rbrace . \end{aligned}$$

Note that the minimum of the Lagrangian over x is attained when $Px + A^Ty + q = 0$, and the second term in the last line is $S_{\mathcal {C}}(y)$. The dual problem, defined as the problem of maximizing the dual function, can then be written in the form (4), where the conic constraint on y is just the restriction of y to the domain of $S_{\mathcal {C}}$ [31, p.112 and Cor. 14.2.1]. $\square$

Lemma A.3

For any vectors $v\in \mathbb {R}^n$, $b\in \mathbb {R}^n$ and a nonempty, closed, and convex cone $\mathcal {K}\subseteq \mathbb {R}^n$,

• (i) ${\Pi }_{\mathcal {K}_b}(v) = b + {\Pi }_{\mathcal {K}}(v - b)$.

• (ii) $({{\,\mathrm{Id}\,}}- {\Pi }_{\mathcal {K}_b})(v) = {\Pi }_{{\mathcal {K}}^{\circ }}(v - b)$.

• (iii) $\left\langle {{\Pi }_{\mathcal {K}_b}(v)},{({{\,\mathrm{Id}\,}}- {\Pi }_{\mathcal {K}_b})(v)}\right\rangle = \left\langle {b},{{\Pi }_{{\mathcal {K}}^{\circ }}(v - b)}\right\rangle$.

• (iv) $\left\langle {{\Pi }_{\mathcal {K}}(v)},{v}\right\rangle = ||{\Pi }_{\mathcal {K}}(v)||^2$.

• (v) $S_{\mathcal {K}_b} ( {\Pi }_{{\mathcal {K}}^{\circ }}(v) ) = \left\langle {b},{{\Pi }_{{\mathcal {K}}^{\circ }}(v)}\right\rangle$.

Proof

Part (i) is from [15, Prop. 28.1(i)].

• (ii) From part (i), we have

  $$\begin{aligned} ({{\,\mathrm{Id}\,}}- {\Pi }_{\mathcal {K}_b})(v) = v - b - {\Pi }_{\mathcal {K}}(v - b) = {\Pi }_{{\mathcal {K}}^{\circ }}(v - b), \end{aligned}$$

  where the second equality follows from the Moreau decomposition [15, Thm. 6.29].

• (iii) Follows directly from parts (i) and (ii), and the Moreau decomposition.

• (iv) From the Moreau decomposition, we have

  $$\begin{aligned} \left\langle {{\Pi }_{\mathcal {K}}(v)},{v}\right\rangle = \left\langle {{\Pi }_{\mathcal {K}}(v)},{{\Pi }_{\mathcal {K}}(v) + {\Pi }_{{\mathcal {K}}^{\circ }}(v)}\right\rangle = ||{\Pi }_{\mathcal {K}}(v)||^2. \end{aligned}$$

  $\square$

• (v) Since the support function of $\mathcal {K}$ evaluated at any point in ${\mathcal {K}}^{\circ }$ is zero, we have

  $$\begin{aligned} S_{\mathcal {K}_b} ( {\Pi }_{{\mathcal {K}}^{\circ }}(v) ) = \left\langle {b},{{\Pi }_{{\mathcal {K}}^{\circ }}(v)}\right\rangle + S_{\mathcal {K}} ( {\Pi }_{{\mathcal {K}}^{\circ }}(v) ) = \left\langle {b},{{\Pi }_{{\mathcal {K}}^{\circ }}(v)}\right\rangle . \end{aligned}$$

Lemma A.4

Suppose that $\mathcal {K}\subseteq \mathbb {R}^n$ is a nonempty, closed, and convex cone and for some sequence $\lbrace {v^k} \rbrace _{k\in {\mathbb {N}}}$, where $v^k\in \mathbb {R}^n$, we denote by $\delta v :=\lim _{k\rightarrow \infty }\tfrac{1}{k}v^k$, assuming that the limit exists. Then for any $b\in \mathbb {R}^n$,

$$\begin{aligned} \lim _{k\rightarrow \infty }\tfrac{1}{k}{\Pi }_{\mathcal {K}_b}(v^k) = \lim _{k\rightarrow \infty }\tfrac{1}{k}{\Pi }_{\mathcal {K}}(v^k-b) = {\Pi }_{\mathcal {K}}(\delta v). \end{aligned}$$

Proof

Write the limit as

$$\begin{aligned} \lim _{k\rightarrow \infty }\tfrac{1}{k}{\Pi }_{\mathcal {K}_b}(v^k)&= \lim _{k\rightarrow \infty }\tfrac{1}{k}\left( b + {\Pi }_{\mathcal {K}}(v^k - b) \right) \\&= \lim _{k\rightarrow \infty }{\Pi }_{\mathcal {K}} \left( \tfrac{1}{k}(v^k - b) \right) \\&= {\Pi }_{\mathcal {K}} \left( \lim _{k\rightarrow \infty }\tfrac{1}{k} v^k \right) , \end{aligned}$$

where the first equality uses Lemma A.3(i) and the second and third follow from the positive homogeneity [15, Prop. 28.22] and continuity [15, Prop. 4.8] of ${\Pi }_{\mathcal {K}}$, respectively. $\square$

Lemma A.5

Suppose that $\mathcal {B}\subseteq \mathbb {R}^n$ is a nonempty, convex, and compact set, and for some sequence $\lbrace {v^k} \rbrace _{k\in {\mathbb {N}}}$, where $v^k\in \mathbb {R}^n$, we denote by $\delta v :=\lim _{k\rightarrow \infty }\tfrac{1}{k}v^k$, assuming that the limit exists. Then

$$\begin{aligned} \lim _{k\rightarrow \infty } \tfrac{1}{k} \left\langle {v^k},{{\Pi }_{\mathcal {B}}(v^k)}\right\rangle = \lim _{k\rightarrow \infty } \left\langle {\delta v},{{\Pi }_{\mathcal {B}}(v^k)}\right\rangle = S_{\mathcal {B}}(\delta v). \end{aligned}$$

Proof

Let $z^k :={\Pi }_{\mathcal {B}}(v^k)$. We have the following inclusion [15, Prop. 6.46]

$$\begin{aligned} v^k - z^k \in N_{\mathcal {B}}(z^k), \end{aligned}$$

which, due to [15, Thm. 16.23], and the facts that $S_{\mathcal {B}}$ is the Fenchel conjugate of $\mathcal {I}_\mathcal {B}$ and $N_{\mathcal {B}}$ is the subdifferential of $\mathcal {I}_\mathcal {B}$, is equivalent to

$$\begin{aligned} \left\langle {\tfrac{1}{k}(v^k-z^k)},{z^k}\right\rangle = S_{\mathcal {B}}\left( \tfrac{1}{k}(v^k-z^k)\right) . \end{aligned}$$

Taking the limit of the identity above, we obtain

$$\begin{aligned} \lim _{k\rightarrow \infty } \left\langle {\tfrac{1}{k}(v^k-z^k)},{z^k}\right\rangle= & {} \lim _{k\rightarrow \infty } S_{\mathcal {B}}\left( \tfrac{1}{k}(v^k-z^k)\right) \nonumber \\= & {} S_{\mathcal {B}}\big (\lim _{k\rightarrow \infty }\tfrac{1}{k}(v^k-z^k)\big ) = S_{\mathcal {B}}(\delta v), \end{aligned}$$

(36)

where the second equality follows from the continuity of $S_{\mathcal {B}}$ [15, Ex. 11.2] and the third from the compactness of $\mathcal {B}$. Since $\lbrace {z^k} \rbrace _{k\in {\mathbb {N}}}$ remains in the compact set $\mathcal {B}$, we can derive the following relation from (36):

$$\begin{aligned} \left|S_{\mathcal {B}}(\delta v) - \lim _{k\rightarrow \infty } \left\langle {\delta v},{z^k}\right\rangle \right|&= \left|\lim _{k\rightarrow \infty } \left\langle {\tfrac{1}{k}(v^k-z^k)},{z^k}\right\rangle - \left\langle {\delta v},{z^k}\right\rangle \right|\\&= \left|\lim _{k\rightarrow \infty } \left\langle {\tfrac{1}{k}v^k - \delta v},{z^k}\right\rangle - \tfrac{1}{k} \left\langle {z^k},{z^k}\right\rangle \right|\\&\le \lim _{k\rightarrow \infty } \underbrace{||\tfrac{1}{k} v^k - \delta v||}_{\rightarrow 0} \, ||z^k|| + \tfrac{1}{k} ||z^k||^2 \\&= 0, \end{aligned}$$

where the third row follows from the triangle and Cauchy-Schwarz inequalities and the fourth from the compactness of $\mathcal {B}$. Finally, we can derive the following identity from (36):

$$\begin{aligned} S_{\mathcal {B}}(\delta v) = \lim _{k\rightarrow \infty } \left\langle {\tfrac{1}{k}(v^k-z^k)},{z^k}\right\rangle = \lim _{k\rightarrow \infty } \left\langle {\tfrac{1}{k} v^k},{z^k}\right\rangle - \underbrace{\tfrac{1}{k}||z^k||^2}_{\rightarrow 0}. \end{aligned}$$

This concludes the proof. $\square$