8 Duality in conic optimization

In Sec. 2 (Linear optimization) we introduced duality and related concepts for linear optimization. Here we present a more general version of this theory for conic optimization and we illustrate it with examples. Although this chapter is self-contained, we recommend familiarity with Sec. 2 (Linear optimization), which some of this material is a natural extension of.

Duality theory is a rich and powerful area of convex optimization, and central to understanding sensitivity analysis and infeasibility issues. Furthermore, it provides a simple and systematic way of obtaining non-trivial lower bounds on the optimal value for many difficult non-convex problems.

From now on we consider a conic problem in standard form

(8.1)$$\begin{array}{r}\begin{array}{ll}\text{minimize}& c^{T}x\\ \text{subject to}& Ax=b,\\ & x\in K,\end{array}\end{array}$$

where $K$ is a convex cone. In practice $K$ would likely be defined as a product

$$K=K_1\times \cdots \times K_m$$

of smaller cones corresponding to actual constraints in the problem formulation. The abstract formulation (8.1) encompasses such special cases as $K={\mathbb{R}}_{+}^n$ (linear optimization), $K_i=\mathbb{R}$ (unconstrained variable) or $K_i={\mathcal{S}}_{+}^n$ ($\frac{1}{2}n(n+1)$ variables representing the upper-triangular part of a matrix).

The feasible set for (8.1):

$${\mathcal{F}}_p=\{x\in {\mathbb{R}}^n\mid Ax=b\}\cap K$$

is a section of $K$. We say the problem is feasible if ${\mathcal{F}}_p\ne \mathrm{\varnothing }$ and infeasible otherwise. The value of (8.1) is defined as

$$p^{\star }=inf\{c^{T}x:x\in {\mathcal{F}}_p\},$$

allowing the special cases of $p^{\star }=+\mathrm{\infty }$ (the problem is infeasible) and $p^{\star }=-\mathrm{\infty }$ (the problem is unbounded). Note that $p^{\star }$ may not be attained, i.e. the infimum is not necessarily a minimum, although this sort of problems are ill-posed from a practical point of view (see Sec. 7 (Practical optimization)).

Example 8.1 Unattained problem value

The conic quadratic problem

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& x\\ \text{subject to}& (x,y,1)\in {\mathcal{Q}}_r^3,\end{array}\end{array}$$

with constraint equivalent to $2xy\ge 1,x,y\ge 0$ has $p^{\star }=0$ but this optimal value is not attained by any point in ${\mathcal{F}}_p$.

8.1 Dual cone

Suppose $K\subseteq {\mathbb{R}}^n$ is a closed convex cone. We define the dual cone $K^{\ast }$ as

(8.2)$$K^{\ast }=\{y\in {\mathbb{R}}^n:y^{T}x\ge 0\mathrm{\forall }x\in K\}.$$

For simplicity we write $y^{T}x$, denoting the standard Euclidean inner product, but everything in this section applies verbatim to the inner product of matrices in the semidefinite context. In other words $K^{\ast }$ consists of vectors which form an acute (or right) angle with every vector in $K$. We see easily that $K^{\ast }$ is in fact a convex cone. The main example, associated with linear optimization, is the dual of the positive orthant:

Lemma 8.1 Dual of linear cone

$$({\mathbb{R}}_{+}^n{)}^{\ast }={\mathbb{R}}_{+}^n.$$

Proof

8.1

This is obvious for $n=1$, and then we use the simple fact

$$(K_1\times \cdots \times K_m{)}^{\ast }=K_1^{\ast }\times \cdots \times K_m^{\ast },$$

which we invite the reader to prove.

All cones studied in this cookbook can be explicitly dualized as we show next.

Lemma 8.2 Duals of nonlinear cones

We have the following:

• The quadratic, rotated quadratic and semidefinite cones are self-dual:

  $$({\mathcal{Q}}^n{)}^{\ast }={\mathcal{Q}}^n,({\mathcal{Q}}_{\mathit{r}}^n{)}^{\ast }={\mathcal{Q}}_{\mathit{r}}^n,({\mathcal{S}}_{+}^n{)}^{\ast }={\mathcal{S}}_{+}^n.$$

• The dual of the power cone (4.4) is

  $$({\mathcal{P}}_n^{{\alpha }_1,\cdots ,{\alpha }_m}{)}^{\ast }=\{y\in {\mathbb{R}}^n:(\frac{y_1}{{\alpha }_1},\dots ,\frac{y_m}{{\alpha }_m},y_{m+1},\dots ,y_n)\in {\mathcal{P}}_n^{{\alpha }_1,\cdots ,{\alpha }_m}\}.$$

• The dual of the geometric mean cone (4.5) is

  $$({\mathcal{GM}}^n{)}^{\ast }=\{x\in {\mathbb{R}}^n:(n-1){\left(\prod _{i=1}^{n-1}{x}_i\right)}^{1/(n-1)}\ge |x_n|,x_1,\dots ,x_{n-1}\ge 0\}.$$

• The dual of the exponential cone (5.2) is the closure

  $$(K_{\exp }{)}^{\ast }=\mathrm{cl}\{y\in {\mathbb{R}}^3:y_1\ge -y_3{e}^{y_2/y_3-1},y_1>0,y_3<0\}.$$

Proof

8.2

We only sketch some parts of the proof and indicate geometric intuitions. First, let us show $({\mathcal{Q}}^n{)}^{\ast }={\mathcal{Q}}^n$. For $(t,x),(s,y)\in {\mathcal{Q}}^n$ we have

$$st+y^{T}x\ge \Vert y{\Vert }_2\Vert x{\Vert }_2+y^{T}x\ge 0$$

by the Cauchy-Schwartz inequality $|u^{T}v|\le \Vert u{\Vert }_2\Vert v{\Vert }_2$, therefore ${\mathcal{Q}}^n\subseteq ({\mathcal{Q}}^n{)}^{\ast }$. Geometrically we are just saying that the quadratic cone ${\mathcal{Q}}^n$ has a right angle at the apex, so any two vectors inside the cone form at most a right angle. Now suppose $(s,y)$ is a point outside ${\mathcal{Q}}^n$. If $(-s,-y)\in {\mathcal{Q}}^n$ then $-s^2-y^{T}y<0$ and we showed $(s,y)\notin ({\mathcal{Q}}^n{)}^{\ast }$. Otherwise let $(t,x)={\mathrm{proj}}_{{\mathcal{Q}}^n}(s,y)$ be the projection (see Sec. 7.7 (Distance to a cone)); note that $(s,y)$ and $(t,-x)\in {\mathcal{Q}}^n$ form an obtuse angle.

For the semidefinite cone we use the property $⟨X,Y⟩\ge 0$ for $X,Y\in {\mathcal{S}}_{+}^n$ (see Sec. 6.1.2 (Properties of semidefinite matrices)). Conversely, assume that $Z\notin {\mathcal{S}}_{+}^n$. Then there exists a $w$ satisfying $⟨w{w}^T,Z⟩=w^{T}Zw<0$, so $Z\notin ({\mathcal{S}}_{+}^n{)}^{\ast }$.

As our last exercise let us check that vectors in $K_{\exp }$ and $(K_{\exp }{)}^{\ast }$ form acute angles. By definition of $K_{\exp }$ and $(K_{\exp }{)}^{\ast }$ we take $x,y$ such that:

$$x_1\ge x_2\exp (x_3/x_2),y_1\ge -y_3\exp (y_2/y_3-1),x_1,x_2,y_1>0,y_3<0,$$

and then we have

$$\begin{array}{r}\begin{array}{ll}{y}^{T}x=x_1{y}_1+x_2{y}_2+x_3{y}_3& \ge -x_2{y}_3\exp (\frac{x_3}{x_2}+\frac{y_2}{y_3}-1)+x_2{y}_2+x_3{y}_3\\ & \ge -x_2{y}_3(\frac{x_3}{x_2}+\frac{y_2}{y_3})+x_2{y}_2+x_3{y}_3=0,\end{array}\end{array}$$

using the inequality $\exp (t)\ge 1+t$. We refer to the literature for full proofs of all the statements.

Finally it is nice to realize that $(K^{\ast }{)}^{\ast }=K$ and that the cones $\{0\}$ and $\mathbb{R}$ are each others’ duals. We leave it to the reader to check these facts.

8.2 Infeasibility in conic optimization

We can now discuss infeasibility certificates for conic problems. Given an optimization problem, the first basic question we are interested in is its feasibility status. The theory of infeasibility certificates for linear problems, including the Farkas lemma (see Sec. 2.3 (Infeasibility in linear optimization)) extends almost verbatim to the conic case.

Lemma 8.3 Farkas' lemma, conic version

Suppose we have the conic optimization problem (8.1). Exactly one of the following statements is true:

1. Problem (8.1) is feasible.

2. Problem (8.1) is infeasible, but there is a sequence $x_n\in K$ such that $\Vert A{x}_n-b\Vert \to 0$.

3. There exists $y$ such that $-A^{T}y\in K^{\ast }$ and $b^{T}y>0$.

Problems which fall under option 2. (limit-feasible) are ill-posed: an arbitrarily small perturbation of input data puts the problem in either category 1. or 3. This fringe case should therefore not appear in practice, and if it does, it signals issues with the optimization model which should be addressed.

Example 8.2 Limit-feasible model

Here is an example of an ill-posed limit-feasible model created by fixing one of the root variables of a rotated quadratic cone to $0$.

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& u\\ \text{subject to}& (u,v,w)\in {\mathcal{Q}}_r^3,\\ & v=0,\\ & w\ge 1.\end{array}\end{array}$$

The problem is clearly infeasible, but the sequence $(u_n,v_n,w_n)=(n,1/n,1)\in {\mathcal{Q}}_r^3$ with $(v_n,w_n)\to (0,1)$ makes it limit-feasible as in alternative 2. of Lemma 8.3. There is no infeasibility certificate as in alternative 3.

Having cleared this detail we continue with the proof and example for the actually useful part of conic Farkas’ lemma.

Proof

8.3

Consider the set

$$A(K)=\{Ax:x\in K\}.$$

It is a convex cone. Feasibility is equivalent to $b\in A(K)$. If $b\notin A(K)$ but $b\in \mathrm{cl}(A(K))$ then we have the second alternative. Finally, if $b\notin \mathrm{cl}(A(K))$ then the closed convex cone $\mathrm{cl}(A(K))$ and the point $b$ can be strictly separated by a hyperplane passing through the origin, i.e. there exists $y$ such that

$$b^{T}y>0,(Ax{)}^{T}y\le 0\mathrm{\forall }x\in K.$$

But then $0\le -(Ax{)}^{T}y=(-A^{T}y{)}^{T}x$ for all $x\in K$, so by definition of $K^{\ast }$ we have $-A^{T}y\in K^{\ast }$, and we showed $y$ satisfies the third alternative. Finally, 1. and 3. are mutually exclusive, since otherwise we would have

$$0\le (-A^{T}y{)}^{T}x=-y^{T}Ax=-y^{T}b<0$$

and the same argument works in the limit if $x_n$ is a sequence as in 2. That proves the lemma.

Therefore Farkas’ lemma implies that (up to certain ill-posed cases) either the problem (8.1) is feasible (first alternative) or there is a certificate of infeasibility $y$ (last alternative). In other words, every time we classify a model as infeasible, we can certify this fact by providing an appropriate $y$. Note that when $K={\mathbb{R}}_{+}^n$ we recover precisely the linear version, Lemma 2.1.

Example 8.3 Infeasible conic problem

Consider a minimization problem:

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& x_1\\ \text{subject to}& -x_1+x_2-x_4=1,\\ & 2x_3-3x_4=-1,\\ & x_1\ge \sqrt{x_2^2+x_3^2},\\ & x_4\ge 0.\end{array}\end{array}$$

It can be expressed in the standard form (8.1) with

$$\begin{array}{r}A=\left[\begin{array}{cccc}-1& 1& 0& -1\\ 0& 0& 2& -3\end{array}\right],b=\left[\begin{array}{c}1\\ -1\end{array}\right],K={\mathcal{Q}}^3\times {\mathbb{R}}_{+},c=[1,0,0,0{]}^T.\end{array}$$

A certificate of infeasibility is $y=[1,0{]}^T$. Indeed, $b^{T}y=1>0$ and $-A^{T}y=[1,-1,0,1]\in K^{\ast }={\mathcal{Q}}^3\times {\mathbb{R}}_{+}$. The certificate indicates that the first linear constraint alone causes infeasibility, which is indeed the case: the first equality together with the conic constraints yield a contradiction:

$$x_2-1\ge x_2-1-x_4=x_1\ge |x_2|.$$

8.3 Lagrangian and the dual problem

Classical Lagrangian

In general constrained optimization we consider an optimization problem of the form

(8.3)$$\begin{array}{r}\begin{array}{ll}\text{minimize}& f_0(x)\\ \text{subject to}& f(x)\le 0,\\ & h(x)=0,\end{array}\end{array}$$

where $f_0:{\mathbb{R}}^n\mapsto \mathbb{R}$ is the objective function, $f:{\mathbb{R}}^n\mapsto {\mathbb{R}}^m$ encodes inequality constraints, and $h:{\mathbb{R}}^n\mapsto {\mathbb{R}}^p$ encodes equality constraints. Readers familiar with the method of Lagrange multipliers or penalization will recognize the Lagrangian for (8.3), a function $L:{\mathbb{R}}^n\times {\mathbb{R}}^m\times {\mathbb{R}}^p\mapsto \mathbb{R}$ that augments the objective with a weighted combination of all the constraints,

(8.4)$$L(x,y,s)=f_0(x)+y^{T}h(x)+s^{T}f(x).$$

The variables $y\in {\mathbb{R}}^p$ and $s\in {\mathbb{R}}_{+}^m$ are called Lagrange multipliers or dual variables. The Lagrangian has the property that $L(x,y,s)\le f_0(x)$ whenever $x$ is feasible for (8.1) and $s\in {\mathbb{R}}_{+}^m$. The optimal point satisfies the first-order optimality condition ${\mathrm{\nabla }}_{x}L(x,y,s)=0$. Moreover, the dual function $g(y,s)=\underset{x}{inf}L(x,y,s)$ provides a lower bound for the optimal value of (8.3) for any $y\in {\mathbb{R}}^p$ and $s\in {\mathbb{R}}_{+}^m$, which leads to considering the dual problem of maximizing $g(y,s)$.

Lagrangian for a conic problem

We next set up an analogue of the Lagrangian theory for the conic problem (8.1)

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& c^{T}x\\ \text{subject to}& Ax=b,\\ & x\in K,\end{array}\end{array}$$

where $x,c\in {\mathbb{R}}^n$, $b\in {\mathbb{R}}^m$, $A\in {\mathbb{R}}^{m\times n}$ and $K\subseteq {\mathbb{R}}^n$ is a convex cone. We associate with (8.1) a Lagrangian of the form $L:{\mathbb{R}}^n\times {\mathbb{R}}^m\times K^{\ast }\to \mathbb{R}$

$$L(x,y,s)=c^{T}x+y^T(b-Ax)-s^{T}x.$$

For any feasible $x^{\ast }\in {\mathcal{F}}_p$ and any $(y^{\ast },s^{\ast })\in {\mathbb{R}}^m\times K^{\ast }$ we have

(8.5)$$L(x^{\ast },y^{\ast },s^{\ast })=c^T{x}^{\ast }+(y^{\ast }{)}^T\cdot 0-(s^{\ast }{)}^T{x}^{\ast }\le c^T{x}^{\ast }.$$

Note the we used the definition of the dual cone to conclude that $(s^{\ast }{)}^T{x}^{\ast }\ge 0$. The dual function is defined as the minimum of $L(x,y,s)$ over $x$. Thus the dual function of (8.1) is

$$\begin{array}{r}g(y,s)=\underset{x}{min}L(x,y,s)=\underset{x}{min}{x}^T(c-A^{T}y-s)+b^{T}y=\{\begin{array}{ll}{b}^{T}y,& c-A^{T}y-s=0,\\ -\mathrm{\infty },& \text{otherwise}.\end{array}\end{array}$$

Dual problem

From (8.5) every $(y,s)\in {\mathbb{R}}^m\times K^{\ast }$ satisfies $g(y,s)\le p^{\star }$, i.e. $g(y,s)$ is a lower bound for $p^{\star }$. To get the best such bound we maximize $g(y,s)$ over all $(y,s)\in {\mathbb{R}}^m\times K^{\ast }$ and get the dual problem:

(8.6)$$\begin{array}{r}\begin{array}{ll}\text{maximize}& b^{T}y\\ \text{subject to}& c-A^{T}y=s,\\ & s\in K^{\ast },\end{array}\end{array}$$

or simply:

(8.7)$$\begin{array}{r}\begin{array}{ll}\text{maximize}& b^{T}y\\ \text{subject to}& c-A^{T}y\in K^{\ast }.\end{array}\end{array}$$

The optimal value of (8.6) will be denoted $d^{\star }$. As in the case of (8.1) (which from now on we call the primal problem), the dual problem can be infeasible ($d^{\star }=-\mathrm{\infty }$), have an optimal solution ($-\mathrm{\infty }<d^{\star }<+\mathrm{\infty }$) or be unbounded ($d^{\star }=+\mathrm{\infty }$). As before, the value $d^{\star }$ is defined as a supremum of $b^{T}y$ and may not be attained. Note that the roles of $-\mathrm{\infty }$ and $+\mathrm{\infty }$ are now reversed because the dual is a maximization problem.

Example 8.4 More general constraints

We can just as easily derive the dual of a problem with more general constraints, without necessarily having to transform the problem to standard form beforehand. Imagine, for example, that some solver accepts conic problems of the form:

(8.8)$$\begin{array}{r}\begin{array}{ll}\text{minimize}& c^{T}x+c^f\\ \text{subject to}& l^c\le Ax\le u^c,\\ & l^x\le x\le u^x,\\ & x\in K.\end{array}\end{array}$$

Then we define a Lagrangian with one set of dual variables for each constraint appearing in the problem:

$$\begin{array}{r}\begin{array}{rl}L(x,s_l^c,s_u^c,s_l^x,s_u^x,s_n^x)=& c^{T}x+c^f-(s_l^c{)}^T(Ax-l^c)-(s_u^c{)}^T(u^c-Ax)\\ & -(s_l^x{)}^T(x-l^x)-(s_u^x{)}^T(u^x-x)-(s_n^x{)}^{T}x\\ =& x^T(c-A^T{s}_l^c+A^T{s}_u^c-s_l^x+s_u^x-s_n^x)\\ & +(l^c{)}^T{s}_l^c-(u^c{)}^T{s}_u^c+(l^x{)}^T{s}_l^x-(u^c{)}^T{s}_u^x+c^f\end{array}\end{array}$$

and that gives a dual problem

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& (l^c{)}^T{s}_l^c-(u^c{)}^T{s}_u^c+(l^x{)}^T{s}_l^x-(u^c{)}^T{s}_u^x+c^f\\ \text{subject to}& c+A^T(-s_l^c+s_u^c)-s_l^x+s_u^x-s_n^x=0,\\ & s_l^c,s_u^c,s_l^x,s_u^x\ge 0,\\ & s_n^x\in K^{\ast }.\end{array}\end{array}$$

Example 8.5 Dual of simple portfolio

Consider a simplified version of the portfolio optimization problem, where we maximize expected return subject to an upper bound on the risk and no other constraints:

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& {\mu }^{T}x\\ \text{subject to}& \Vert Fx{\Vert }_2\le \gamma ,\end{array}\end{array}$$

where $x\in {\mathbb{R}}^n$ and $F\in {\mathbb{R}}^{m\times n}$. The conic formulation is

(8.9)$$\begin{array}{r}\begin{array}{ll}\text{maximize}& {\mu }^{T}x\\ \text{subject to}& (\gamma ,Fx)\in {\mathcal{Q}}^{m+1},\end{array}\end{array}$$

and we can directly write the Lagrangian

$$L(x,v,w)={\mu }^{T}x+v\gamma +w^{T}Fx=x^T(\mu +F^{T}w)+v\gamma$$

with $(v,w)\in ({\mathcal{Q}}^{m+1}{)}^{\ast }={\mathcal{Q}}^{m+1}$. Note that we chose signs to have $L(x,v,w)\ge {\mu }^{T}x$ since we are dealing with a maximization problem. The dual is now determined by the conditions $F^{T}w+\mu =0$ and $v\ge \Vert w{\Vert }_2$, so it can be formulated as

(8.10)$$\begin{array}{r}\begin{array}{ll}\text{minimize}& \gamma \Vert w{\Vert }_2\\ \text{subject to}& F^{T}w=-\mu .\end{array}\end{array}$$

Note that it is actually more natural to view problem (8.9) as the dual form and problem (8.10) as the primal. Indeed we can write the constraint in (8.9) as

$$\begin{array}{r}\left[\begin{array}{c}\gamma \\ 0\end{array}\right]-\left[\begin{array}{c}0\\ -F\end{array}\right]x\in (Q^{m+1}{)}^{\ast }\end{array}$$

which fits naturally into the form (8.7). Having done this we can recover the dual as a minimization problem in the standard form (8.1). We leave it to the reader to check that we get the same answer as above.

8.4 Weak and strong duality

Weak duality

Suppose $x^{\ast }$ and $(y^{\ast },s^{\ast })$ are feasible points for the primal and dual problems (8.1) and (8.6), respectively. Then we have

(8.11)$$b^T{y}^{\ast }=(A{x}^{\ast }{)}^T{y}^{\ast }=(x^{\ast }{)}^T(A^T{y}^{\ast })=(x^{\ast }{)}^T(c-s^{\ast })=c^T{x}^{\ast }-(s^{\ast }{)}^T{x}^{\ast }\le c^T{x}^{\ast }$$

so the dual objective value is a lower bound on the objective value of the primal. In particular, any dual feasible point $(y^{\ast },s^{\ast })$ gives a lower bound:

$$b^T{y}^{\ast }\le p^{\star }$$

and we immediately get the next lemma.

Lemma 8.4 Weak duality

$d^{\star }\le p^{\star }$.

It follows that if $b^T{y}^{\ast }=c^T{x}^{\ast }$ then $x^{\ast }$ is optimal for the primal, $(y^{\ast },s^{\ast })$ is optimal for the dual and $b^T{y}^{\ast }=c^T{x}^{\ast }$ is the common optimal objective value. This way we can use the optimal dual solution to certify optimality of the primal solution and vice versa.

Complementary slackness

Moreover, (8.11) asserts that $b^T{y}^{\ast }=c^T{x}^{\ast }$ is equivalent to orthogonality

$$(s^{\ast }{)}^T{x}^{\ast }=0$$

i.e. complementary slackness. It is not hard to verify what complementary slackness means for particular types of cones, for example

• for $s,x\in {\mathbb{R}}_{+}$ we have $sx=0$ iff $s=0$ or $x=0$,

• vectors $(s_1,\tilde{s}),(x_1,\tilde{x})\in {\mathcal{Q}}^{n+1}$ are orthogonal iff $(s_1,\tilde{s})$ and $(x_1,-\tilde{x})$ are parallel,

• vectors $(s_1,s_2,\tilde{s}),(x_1,x_2,\tilde{x})\in {\mathcal{Q}}_{\mathit{r}}^{n+2}$ are orthogonal iff $(s_1,s_2,\tilde{s})$ and $(x_2,x_1,-\tilde{x})$ are parallel.

One implicit case is worth special attention: complementary slackness for a linear inequality constraint $a^{T}x\le b$ with a non-negative dual variable $y$ asserts that $(a^T{x}^{\ast }-b)y^{\ast }=0$. This can be seen by directly writing down the appropriate Lagrangian for this type of constraint. Alternatively, we can introduce a slack variable $u=b-a^{T}x$ with a conic constraint $u\ge 0$ and let $y$ be the dual conic variable. In particular, if a constraint is non-binding in the optimal solution ($a^T{x}^{\ast }<b$) then the corresponding dual variable $y^{\ast }=0$. If $y^{\ast }>0$ then it can be related to a shadow price, see Sec. 2.4.4 (Dual values as shadow prices) and Sec. 8.5.2 (Constraint attribution).

Strong duality

The obvious question is now whether $d^{\star }=p^{\star }$, that is if optimality of a primal solution can always be certified by a dual solution with matching objective value, as for linear programming. This turns out not to be the case for general conic problems.

Example 8.6 Positive duality gap

Consider the problem

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& x_3\\ \text{subject to}& x_1\ge \sqrt{x_2^2+x_3^2},\\ & x_2\ge x_1,x_3\ge -1.\end{array}\end{array}$$

The only feasible points are $(x,x,0)$, so $p^{\star }=0$. The dual problem is

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& -y_2\\ \text{subject to}& y_1\ge \sqrt{y_1^2+(1-y_2{)}^2},\end{array}\end{array}$$

with feasible points $(y,1)$, hence $d^{\star }=-1$.

Similarly, we consider a problem

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& x_1\\ \text{subject to}& \left[\begin{array}{ccc}0& x_1& 0\\ x_1& x_2& 0\\ 0& 0& 1+x_1\end{array}\right]\in {\mathcal{S}}_{+}^3,\end{array}\end{array}$$

with feasible set $\{x_1=0,x_2\ge 0\}$ and optimal value $p^{\star }=0$. The dual problem can be formulated as

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& -z_2\\ \text{subject to}& \left[\begin{array}{ccc}{z}_1& (1-z_2)/2& 0\\ (1-z_2)/2& 0& 0\\ 0& 0& z_2\end{array}\right]\in {\mathcal{S}}_{+}^3,\end{array}\end{array}$$

which has a feasible set $\{z_1\ge 0,z_2=1\}$ and dual optimal value $d^{\star }=-1$.

To ensure strong duality for conic problems we need an additional regularity assumption. As with the conic version of Farkas’ lemma Lemma 8.3, we stress that this is a technical condition to eliminate ill-posed problems which should not be formed in practice. In particular, we invite the reader to think that strong duality holds for all well formed conic problems one is likely to come across in applications, and that having a duality gap signals issues with the model formulation.

We say problem (8.1) is very nicely posed if for all values of $c_0$ the feasibility problem

$$c^{T}x=c_0,Ax=b,x\in K$$

satisfies either the first or third alternative in Lemma 8.3.

Lemma 8.5 Strong duality

Suppose that (8.1) is very nicely posed and $p^{\star }$ is finite. Then $d^{\star }=p^{\star }$.

Proof

8.4

For any $\epsilon >0$ consider the feasibility problem with variable $x$ and constraints

$$\begin{array}{r}\begin{array}{rcl}\left[\begin{array}{c}-c^T\\ A\end{array}\right]x& =& \left[\begin{array}{c}-p^{\star }+\epsilon \\ b\end{array}\right]\\ x& \in & K\end{array}\text{that is}\begin{array}{r}\begin{array}{rcl}{c}^{T}x& =& p^{\star }-\epsilon ,\\ Ax& =& b,\\ x& \in & K.\end{array}\end{array}\end{array}$$

Optimality of $p^{\star }$ implies that the above problem is infeasible. By Lemma 8.3 and because we assumed very-nice-posedness there exists $\hat{y}=[y_{0}y{]}^T$ such that

$$[c,-A^T]\hat{y}\in K^{\ast }\text{and}[-p^{\star }+\epsilon ,b^T]\hat{y}>0.$$

If $y_0=0$ then $-A^{T}y\in K^{\ast }$ and $b^{T}y>0$, which by Lemma 8.3 again would mean that the original problem was infeasible, which is not the case. Hence we can rescale so that $y_0=1$ and then we get

$$c-A^{T}y\in K^{\ast }\text{and}{b}^{T}y\ge p^{\star }-\epsilon .$$

The first constraint means that $y$ is feasible for the dual problem. By letting $\epsilon \to 0$ we obtain $d^{\star }\ge p^{\star }$.

There are more direct conditions which guarantee strong duality, such as below.

Lemma 8.6 Slater constraint qualification

Suppose that (8.1) is strictly feasible: there exists a point $x\in \mathrm{int}(K)$ in the interior of $K$ such that $Ax=b$. Then strong duality holds if $p^{\star }$ is finite. Moreover, if both primal and dual problem are strictly feasible then $p^{\star }$ and $d^{\star }$ are attained.

We omit the proof which can be found in standard texts. Note that the first problem from Example 8.6 does not satisfy Slater constraint qualification: the only feasible points lie on the boundary of the cone (we say the problem has no interior). That problem is not very nicely posed either: the point $(x_1,x_2,x_3)=(0.5c_0^2{\epsilon }^{-1}+\epsilon ,0.5c_0^2{\epsilon }^{-1},c_0)\in {\mathcal{Q}}^3$ violates the inequality $x_2\ge x_1$ by an arbitrarily small $\epsilon$, so the problem is infeasible but limit-feasible (second alternative in Lemma 8.3).

8.5 Applications of conic duality

8.5.1 Linear regression and the normal equation

Least-squares linear regression is the problem of minimizing $\Vert Ax-b{\Vert }_2^2$ over $x\in {\mathbb{R}}^n$, where $A\in {\mathbb{R}}^{m\times n}$ and $b\in {\mathbb{R}}^m$ are fixed. This problem can be posed in conic form as

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& t\\ \text{subject to}& (t,Ax-b)\in {\mathcal{Q}}^{m+1},\end{array}\end{array}$$

and we can write the Lagrangian

$$L(t,x,u,v)=t-tu-v^T(Ax-b)=t(1-u)-x^T{A}^{T}v+b^{T}v$$

so the constraints in the dual problem are:

$$u=1,A^{T}v=0,(u,v)\in Q^{m+1}.$$

The problem exhibits strong duality with both the primal and dual values attained in the optimal solution. The primal solution clearly satisfies $t=\Vert Ax-b{\Vert }_2$, and so complementary slackness for the quadratic cone implies that the vectors $(u,-v)=(1,-v)$ and $(t,Ax-b)$ are parallel. As a consequence the constraint $A^{T}v=0$ becomes $A^T(Ax-b)=0$ or simply

$$A^{T}Ax=A^{T}b$$

so if $A^{T}A$ is invertible then $x=(A^{T}A{)}^{-1}{A}^{T}b$. This is the so-called normal equation for least-squares regression, which we now obtained as a consequence of strong duality.

8.5.2 Constraint attribution

Consider again a portfolio optimization problem with mean-variance utility function, vector of expected returns $\alpha$ and covariance matrix $\mathrm{\Sigma }=F^{T}F$:

(8.12)$$\begin{array}{r}\begin{array}{ll}\text{maximize}& {\alpha }^{T}x-\frac{1}{2}c{x}^T\mathrm{\Sigma }x\\ \text{subject to}& Ax\le b,\end{array}\end{array}$$

where the linear part represents any set of additional constraints: total budget, sector constraints, diversification constraints, individual relations between positions etc. In the absence of additional constraints the solution to the unconstrained maximization problem is easy to derive using basic calculus and equals

$$\hat{x}=c^{-1}{\mathrm{\Sigma }}^{-1}\alpha .$$

We would like to understand the difference $x^{\ast }-\hat{x}$, where $x^{\ast }$ is the solution of (8.12), and in particular to measure which of the linear constraints actually cause $x^{\ast }$ to deviate from $\hat{x}$ and to what degree. This can be quantified using the dual variables.

The conic version of problem (8.12) is

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& {\alpha }^{T}x-cr\\ \text{subject to}& Ax\le b,\\ & (1,r,Fx)\in {\mathcal{Q}}_{\mathit{r}}\end{array}\end{array}$$

with dual

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& b^{T}y+s\\ \text{subject to}& A^{T}y=\alpha +F^{T}u,\\ & (s,c,u)\in {\mathcal{Q}}_{\mathit{r}},\\ & y\ge 0.\end{array}\end{array}$$

Suppose we have a primal-dual optimal solution $(x^{\ast },r^{\ast },y^{\ast },s^{\ast },u^{\ast })$. Complementary slackness for the rotated quadratic cone implies

$$(s^{\ast },c,u^{\ast })=\beta (r^{\ast },1,-F{x}^{\ast })$$

which leads to $\beta =c$ and

$$A^T{y}^{\ast }=\alpha -c{F}^{T}F{x}^{\ast }$$

or equivalently

$$x^{\ast }=\hat{x}-c^{-1}{\mathrm{\Sigma }}^{-1}{A}^T{y}^{\ast }.$$

This equation splits the difference between the constrained and unconstrained solutions into contributions from individual constraints, where the weights are precisely the dual variables $y^{\ast }$. For example, if a constraint is not binding ($a_i^T{x}^{\ast }-b_i<0$) then by complementary slackness $y_i^{\ast }=0$ and, indeed, a non-binding constraint has no effect on the change in solution.

8.6 Semidefinite duality and LMIs

The general theory of conic duality applies in particular to problems with semidefinite variables so here we just state it in the language familiar to SDP practitioners. Consider for simplicity a primal semidefinite optimization problem with one matrix variable

(8.13)$$\begin{array}{r}\begin{array}{ll}\text{minimize}& ⟨C,X⟩\\ \text{subject to}& ⟨A_i,X⟩=b_i,i=1,\dots ,m,\\ & X\in {\mathcal{S}}_{+}^n.\end{array}\end{array}$$

We can quickly repeat the derivation of the dual problem in this notation. The Lagrangian is

$$\begin{array}{r}\begin{array}{ll}L(X,y,S)& =⟨C,X⟩-\sum _i{y}_i(⟨A_i,X⟩-b_i)-⟨S,X⟩\\ & =⟨C-\sum _i{y}_i{A}_i-S,X⟩+b^{T}y\end{array}\end{array}$$

and we get the dual problem

(8.14)$$\begin{array}{r}\begin{array}{ll}\text{maximize}& b^{T}y\\ \text{subject to}& C-\sum _{i=1}^m{y}_i{A}_i\in {\mathcal{S}}_{+}^n.\end{array}\end{array}$$

The dual contains an affine matrix-valued function with coefficients $C,A_i\in {\mathcal{S}}^n$ and variable $y\in {\mathbb{R}}^m$. Such a matrix-valued affine inequality is called a linear matrix inequality (LMI). In Sec. 6 (Semidefinite optimization) we formulated many problems as LMIs, that is in the form more naturally matching the dual.

From a modeling perspective it does not matter whether constraints are given as linear matrix inequalities or as an intersection of affine hyperplanes; one formulation is easily converted to other using auxiliary variables and constraints, and this transformation is often done transparently by optimization software. Nevertheless, it is instructive to study an explicit example of how to carry out this transformation. An linear matrix inequality

$$A_0+x_1{A}_1+\cdots +x_n{A}_n⪰0$$

where $A_i\in {\mathcal{S}}_{+}^m$ is converted to a set of linear equality constraints using a slack variable

$$A_0+x_1{A}_1+\cdots +x_n{A}_n=S,S⪰0.$$

Apart from introducing an explicit semidefinite variable $S\in {\mathcal{S}}_{+}^m$ we also added $m(m+1)/2$ equality constraints. On the other hand, a semidefinite variable $X\in {\mathcal{S}}_{+}^n$ can be rewritten as a linear matrix inequality with $n(n+1)/2$ scalar variables

$$X=\sum _{i=1}^n{e}_i{e}_i^T{x}_{ii}+\sum _{i=1}^n\sum _{j=i+1}^n(e_i{e}_j^T+e_j{e}_i^T)x_{ij}⪰0.$$

Obviously we should only use these transformations when necessary; if we have a problem that is more naturally interpreted in either primal or dual form, we should be careful to recognize that structure.

Example 8.7 Dualization and efficiency

Consider the problem:

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& e^{T}z\\ \text{subject to}& A+\mathbf{Diag}(z)=X,\\ & X⪰0.\end{array}\end{array}$$

with the variables $X\in {\mathcal{S}}_{+}^n$ and $z\in {\mathbb{R}}^n$. This is a problem in primal form with $n(n+1)/2$ equality constraints, but they are more naturally interpreted as a linear matrix inequality

$$A+\sum _i{e}_i{e}_i^T{z}_i⪰0.$$

The dual problem is

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& -⟨A,Z⟩\\ \text{subject to}& \mathbf{diag}(Z)=e,\\ & Z⪰0,\end{array}\end{array}$$

in the variable $Z\in {\mathcal{S}}_{+}^n$. The dual problem has only $n$ equality constraints, which is a vast improvement over the $n(n+1)/2$ constraints in the primal problem. See also Sec. 7.5 (Semidefinite variables).

Example 8.8 Sum of singular values revisited

In Sec. 6.2.4 (Singular value optimization), and specifically in (6.18), we expressed the problem of minimizing the sum of singular values of a nonsymmetric matrix $X$. Problem (6.18) can be written as an LMI:

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& \sum _{i,j}{X}_{ij}{z}_{ij}\\ \text{subject to}& I-\sum _{i,j}{z}_{ij}\left[\begin{array}{cc}0& e_j{e}_i^T\\ e_i{e}_j^T& 0\end{array}\right]⪰0.\end{array}\end{array}$$

Treating this as the dual and going back to the primal form we get:

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& \mathrm{Tr}(U)+\mathrm{Tr}(V)\\ \text{subject to}& S=-\frac{1}{2}X,\\ & \left[\begin{array}{cc}U& S^T\\ S& V\end{array}\right]⪰0,\end{array}\end{array}$$

which is equivalent to the claimed (6.19). The dual formulation has the advantage of being linear in $X$.