How to derive the dual of a conic programming problem, $\min_{x\in L}\{c^T x: \,\, Ax-b\in K\}$?

Question

I'm trying to get a better understanding of the derivation of the dual problem associated with a given conic problem.

From these notes (pdf alert), a conic problem is written (see page 5) as $$\min_x \{c^T x: \,\, Ax-b\in K\},\tag1$$ for some closed convex cone $K$.

To obtain the dual problem, the text then argues that, defining the Lagrangian as $L(x,\lambda)=c^T x -\lambda^T(Ax-b)$, we have must $$\min_x L(x,\lambda)\le \min_x\{c^T x: \,\,Ax-b\in K\}, \quad \forall \lambda\in K^*,\tag2$$ where $K^*$ is the dual cone of $K$ (the text doesn't explicitly write these equations, but this is how I understand what is being said around pages 6 and 7). The dual problem should then come, I think, from $$\max_\lambda\{ \min_x L(x,\lambda) : \,\, \lambda\in K^*\} = \max_\lambda\{ \min_x [(c-A^T\lambda)^Tx+ b^T\lambda] : \,\, \lambda\in K^*\}.\tag3$$ The dual problem is written, in the notes, as $$\max_\lambda\{b^T\lambda: \,\, A^T\lambda=c, \,\, \lambda\in K^*\}.\tag4$$

The domain of $x$ is not actually explicitly specified here (or at least I'm not seeing it), but I'm assuming it's either $x\ge0$, or $x\in L$ for some other closed convex cone $L$.

How do we get from (3) to (4)? I can sort of see it when $x\ge0$, but I'm unsure how to operate in the more general case of $x\in L$.

Answer 1

EDIT: Oops, didn't see that you had $x\in L$ in the question. I only answered for $L=\mathbb{R}^n$. Below, I give a Lagrangian approach for $L$ a closed, convex cone.

---

I will outline an approach of Lagrangian duality. Given the primal problem and its value $\nu(P)$, i.e., \begin{array}{lcl} \begin{align} \nu(P):= & \min_{x\in\mathbb{R}^n} & c^\top x & \\ & \text{s.t.} & Ax-b\in K \end{align} \end{array} we can write the Lagrangian \begin{align} L(x;\lambda):= c^\top x + \lambda^\top(b-Ax) \end{align} and observe that \begin{align} \nu(P) \overset{(i)}{=} \min_{x\in\mathbb{R}^n}\max_{\lambda\in K^*} L(x;\lambda) \overset{(ii)}{\geq} \max_{\lambda\in K^*}\min_{x\in\mathbb{R}^n} L(x;\lambda) \overset{(iii)}{=} \nu(D) \end{align} where $(i)$ follows since $K$ and $K^*$ are dual cones (moving the constraints into the Lagrangian), $(ii)$ follows from the max-min inequality, and $(iii)$ follows from defining the value of the dual problem to be \begin{array}{lcl} \begin{align} \nu(D):= & \min_{\lambda\in\mathbb{R}^m} & b^\top \lambda & \\ & \text{s.t.} & A^\top \lambda = c\\ &&\lambda\in K^* \end{align} \end{array} and rewriting/evaluating the Lagrangian to give a nontrivial lower bound \begin{align} L(x;\lambda)= b^\top\lambda + \langle c-A^\top\lambda, x\rangle \implies \min_{x\in\mathbb{R}^n} L(x;\lambda) = \begin{cases} -\infty,\quad &\text{if $A^\top \lambda \neq c$};\\ b^\top\lambda,\quad &\text{if $A^\top \lambda=c$}.\end{cases} \end{align}

So, the expressions for conic duals are very similar to LP duality, and the derivations are similar symbollically, but there are a few important differences, two of which are:

• In LP duality, exactly one of the following holds:
  • the primal is infeasible and dual is unbounded;
  • the dual is infeasible and primal is unbounded;
  • the dual is infeasible and primal is infeasible;
  • the dual is feasible and primal is feasible, and $(ii)$ is an EQUALITY (strong duality). That is, the optimal solutions are ATTAINED, so there actually exist feasible $x^*,\lambda^*$ that give $\nu(P)$ and $\nu(D)$ when plugged into the primal and dual objective functions, respectively.
• In conic duality, attainment of the solutions is not guaranteed without additional assumptions, UNLIKE linear programming. If we replaced $\max/\min$ with $\sup/\inf$, there are cases where both programs are feasible, and we could have strong duality of the values of the dual programs, but not necessarily attainment. In general, we need to be careful. For more, see here.

---

Consider the following problem where $L$ is a closed, convex cone \begin{array}{lcl} \begin{align} \nu(P):= & \min_{x\in\mathbb{R}^n} & c^\top x & \\ & \text{s.t.} & Ax-b\in K\\ && x\in L. \end{align} \end{array} Then \begin{align} L(x;\lambda,\mu) &= \langle c,x \rangle + \langle \lambda,b-Ax \rangle + \langle \mu,-x \rangle\\ &= \langle b,\lambda \rangle + \langle c-A^\top\lambda-\mu,x \rangle \end{align} so \begin{align} \nu(P) = \min_{x\in L}\max_{\lambda\in K^*,\mu\in L^*} L(x;\lambda,\mu) \geq \min_{x\in L}\max_{\lambda\in K^*,\mu\in L^*} L(x;\lambda,\mu) = \nu(D) \end{align} where \begin{array}{lcl} \begin{align} \nu(D):= & \max_{\lambda,\mu} & b^\top \lambda & \\ & \text{s.t.} & c-A^\top\lambda-\mu\in L^*\\ && \lambda\in K^*,\\ && \mu\in L^*. \end{align} \end{array}

Answer 2

We can make use of Fenchel's Duality scheme, defining:

$P(x)=c^{T}x$ and $Q(Ax)=0$ if $Ax\,\in\,K+b,\,\,$ $-\infty\,\,$ otherwise. So the function $Q(Ax)=-\delta_{K+b}(Ax)$ where $\delta$ is the indicator function, i.e. $\delta_{A}(x)=0$ if $x\in\,A$ and $+\infty$ otherwise.

We first calculate $P^{\star}(x^{\star})$=sup$ \left\{x^{\star}x-c^{T}x \right\}$ which is $0$ if $x^{\star}=c$, $+\infty$ otherwise.

Now the concave conjugate of $\delta_{K+b}\,\,$ is inf$\left\{x^{\star}x-(-\delta_{K+b}(Ax)) \right\}$ . This can be easily calculated using another Fenchel duality scheme

(defining a new variable $y$ and setting a constraint $y=Ax$) (see Rockafellar: Convex Analysis pages 332-335) and getting:

$ Q^{\star}=-\delta_{(K+b)^{\star}}(y^{\star})$ under

$A^{\star}y^{\star}=x^{\star}$ and since by $P^{\star}$ we have $x^{\star}=c$ and the dual problem is :

Maximize $-\delta_{(K+b)^{\star}}(y^{\star})$ under $A^{\star}y^{\star}=c$

where $(K+b)^{\star}$ is the negative polar of $K+b$

i.e. $\left\{z^{\star}:<z^{\star},x>\geq\,0 \,\,\,\forall x\in K+b \right\}$.

I have assumed that$\,\, L$ is the whole space and certainly the intersection of the relative interiors is nonempty,(this is certainly satisfied). If $L$ is NOT the whole space the problem gets a lot more complicated!

Edit: It seems that it is not much more complicated than before! Let $L$ be a closed convex cone.

Define $P(x)=c^{T}x+\delta_{L}(x)$ and

$Q(Ax)=-\delta_{K+b}(Ax)\,\,$ as before.

The convex cojugate of $P$ is $P^{\star}(x^{\star})$=sup$\left\{x^{\star }x-c^{T}x-\delta_{L}(x) \right\}$ which is $\delta_{L_{0}}(x^{\star}-c)$=$-\delta_L^{\star}(c-x^{\star})$.

So the dual problem takes the form:

Maximize $-\delta_{(K+b)^{\star}}(y^{\star})$+$\delta_{L^{\star}}(c-x^{\star})$, under $x^{\star}=A^{\star}y^{\star}$

which gives

Maximize $-\delta_{(K+b)^{\star}}(y^{\star})$+$\delta_{L^{\star}}(c-A^{\star}y^{\star})$