How to write the dual problem in a nutshell

Duality in linear programming  is often mentioned and sometimes even used (see [2]). But in our experience, many practitioners unfortunately have a quite blurred idea  about the dual problem and the meaning of it. Things are even worse when considering conic programming, despite the fact that most of the theory remains unchanged. There are at least three good reasons to have a good understanding conic duality:

• The dual problem could be faster to solve (see our post), even if the complexity is the same.
• Sensitivity analysis uses dual information (see our post), just think about shadow prices.
• Infeasibility and unboundedness certificates are stated in terms of duality, using the Farkas' Lemma.

Duality theory for conic optimization is rich and well-established and deserves much more space than a blog post (see for instance [1]). As first step, we will show how to easily derive the dual formulation of a given conic optimization problem. For sake of clarity, we will not consider semidefinite optimization problems, even if the conic framework readily extends to them.

Let assume we are given an optimization problem, which we refer as the primal. If we are lucky, the primal can be reformulated as a conic optimization problem by means of some transformations (see [1],[3]). An hopefully small additional effort is usually needed to cast our conic problem in (primal) standard form. Let the primal variables be reordered and partitioned such that  $x=(x_1,x_2,\ldots,x_k)^T\in \mathbb{R}^n$ with $x_i\in \mathbb{R}^{n_i}$. Then the standard primal form is:

\begin{equation}
\begin{aligned}
  &\min \quad c^Tx &&\\
  & s.t. &&\\
  &&Ax - b = 0 &\\
  &&x_i \in \mathit{K_i^{n_i}} &\quad i=1,\ldots\,k
\end{aligned}
\end{equation}

Note how each block variable $x_i$ belongs to a cone $\mathit{K_i^{n_i}}$; moreover, we can  recover the standard LP formulation just setting $k=1$ and $n_1=n$. In short we may write $x\in \Pi_{i=1}^k K_i^{n_i}$. For our purpose, $\mathit{K_i^{n_i}}$ can be

- the positive orthant $\mathbb{R}^{n_i}$
- a Lorentz cone $L_i^{n_i}$ of dimension $n_i$
- a rotated Lorentz cone $R_i^{n_i}$ of dimension $n_i$

We introduce as many dual variables $y$ as cones in Problem (1) and obtain the dual problem as follows:

\begin{equation}
\begin{aligned}
  &\max \quad b^Ty \\
  & s.t. \\
  &&  A^T y -c \in\Pi_{i=1}^k \mathit{K}_i^*\\
\end{aligned}
\end{equation}

where $\mathit{K}_i^*$ is the dual cone of $\mathit{K}_i$. In practice, the cones we work with are all self-dual, i.e. they are all dual to themselves, and this means roughly speaking $\mathit{K}_i^*\equiv \mathit{K}_i$. Introducing slack variables Problem (2) reads:

\begin{equation}
\begin{aligned}
  &\max \quad b^Ty \\
  & s.t. \\
  && c- A^T y + s= 0\\
   &&s_i \in \mathit{K}^*_i  &\quad i=1,\ldots\,k
\end{aligned}
\end{equation}

which can be converted again in standard form by noticing that $\min x = - \max -x$ and transforming free variables in non negative ones (see for instance [2]).

Summarizing, we recommend to follow these steps:

1. if possible recast the given problem in conic form
2. transform the conic form in standard form
3. derive the dual formulation
4. simplify the dual if possible

In practice, step 1 requires the biggest effort, while the others follow quite directly. Indeed, the crucial point is to certified the given problem can be expressed in conic form, and we do this actually constructing such a representation. Once we get the conic formulation, most of the job is done. So, working in conic form has also the interesting side-effect of a much simpler access to dual formulation and information.

Check this post to see a practical example! Others will follow in the next days.

[1] Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications (Vol. 2). Siam.

[2] Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Courier Dover Publications.

[3] MOSEK modeling manual , 2013, Mosek ApS