- 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.

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:

- if possible recast the given problem in conic form
- transform the conic form in standard form
- derive the dual formulation
- 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