Dual Values¶

Picos typically reformulates optimization problems as conic programs of the form

$\begin{center} $\begin{array}{cclc} \underset{\mathbf{x} \in \mathbb{R}^n}{\mbox{minimize}} & \mathbf{c}^T \mathbf{x} + \gamma & &\\ \mbox{subject to} & A_i(\mathbf{x}) & \succeq_{K_i} \mathbf{b}_i,\ \forall i \in I, \end{array}$ \end{center}$

where each $A_i$ is a linear map from $\mathbb{R}^n$ to a linear space containing the cone $K_i$ , and the generalized conic inequality $\mathbf{x} \succeq_K \mathbf{y}$ means $\mathbf{x}-\mathbf{y}\in K$ for a cone $K$ . For the sake of compactness, we allow generalized inequalities over the trivial cone $K_{eq} = \{\mathbf{0}\}$ , such that $A \mathbf{x} \succeq_{K_{eq}} \mathbf{b}$ represents an equality constraint $A \mathbf{x} = \mathbf{b}$ .

The dual conic problem can be written as follows:

$\begin{center} $\begin{array}{cll} \mbox{maximize} & \sum_{i\in I} \mathbf{b}_i^T \mathbf{y}_i + \gamma \\ \mbox{subject to} & \sum_{i\in I} A_i^*(\mathbf{y}_i) = \mathbf{c}, \\ & \mathbf{y}_i \succeq_{K_i^*} 0,\ \forall i \in I, \end{array}$ \end{center}$

where $A^*$ denotes the adjoint operator of $A$ and $K^*$ denotes the the dual cone of $K$ (see the note below for a list of cones that are supported in PICOS, together with their dual).

After an optimization problem has been solved, we can query the optimal dual variable $y_i \in K_i^*$ of a conic constraint con over the cone $K_i$ with its dual attribute, i.e., con.dual.

When an optimization problem P can be reformulated to a conic program C of the above form by PICOS, we can use its dual attribute to return a Problem object D=P.dual which contains the dual conic program of C. It is also possible to solve P via its dual by using the dualize option: This passes problem D to the solver, and the optimal primal and dual variables of P will be retrieved from the optimal solution of D.

Supported cones and their dual¶

PICOS can provide dual information for problems involving the following cones:

Trivial cone¶

The trivial cone $K_{eq} = \{\mathbf{0}\}\subset \mathbb{R}^n$ , whose dual cone is the entire space $K_{eq}^* = \mathbb{R}^n$ . This means that the dual variable $\mathbf{y}$ for an equality constraint is unconstrained.

Nonnegative Orthant¶

The nonnegative orthant $\mathbb{R}_+^n$ is self dual: $(\mathbb{R}_+^n)^* = \mathbb{R}_+^n$ . Therefore the dual variable for a set of linear inequalities is a vector $\mathbf{y}\geq\mathbf{0}$ .

Lorentz Cone¶

The Lorentz cone $\mathcal{Q}^n=$ $\{(t,\mathbf{x}) \in \mathbb{R}\times \mathbb{R}^{n-1}: \|\mathbf{x}\| \leq t \}$ , which is used to model second-order cone inequalities, is self-dual: $(\mathcal{Q}^n)^* = \mathcal{Q}^n$ . This means that the dual variable for a second order cone inequality of the form

$\| A \mathbf{x} - \mathbf{b} \| \leq \mathbf{h}^T \mathbf{x} - g \iff \left[ \begin{array}{c} \mathbf{h}^T\\ A \end{array} \right] \mathbf{x} \succeq_{\mathcal{Q}^n} \left[ \begin{array}{c} g\\ \mathbf{b} \end{array} \right]$

is a vector of the form $[\lambda, \mathbf{z}^T]^T$ such that $\|\mathbf{z}\| \leq \lambda$ .

Rotated Second-order Cone¶

The (widened or narrowed) rotated second order cone is

$\mathcal{R}_p^n =\{(u,v,\mathbf{x})\in\mathbb{R}\times\mathbb{R}\times\mathbb{R}^{n-2}: \|\mathbf{x}\|^2 \leq p\cdot u \cdot v,\ u,v\geq 0 \}$

for some $p>0$ , and its dual cone is $(\mathcal{R}_{p}^n)^* = \mathcal{R}_{4/p}^n$ . In particular, $\mathcal{R}_p^n$ is self-dual for $p=2$ . For example, the dual variable for the constraint $\| A \mathbf{x} - \mathbf{b} \|^2 \leq (\mathbf{h}^T \mathbf{x} - g)(\mathbf{e}^T \mathbf{x} - f)$ with $(\mathbf{h}^T \mathbf{x} - g)\geq 0$ and $(\mathbf{e}^T \mathbf{x} - f)\geq 0$ , i.e.,

$\left[ \begin{array}{c} \mathbf{h}^T\\ \mathbf{e}^T\\ A \end{array} \right] \mathbf{x} \succeq_{\mathcal{R}_1^n} \left[ \begin{array}{c} g\\ f\\ \mathbf{b} \end{array} \right]$

is a vector of the form $[\alpha, \beta, \mathbf{z}^T]^T$ such that $\|\mathbf{z}\|^2 \leq 4 \alpha \beta$ ;

Positive Semi-definite Cone¶

The positive semidefinite cone $\mathbb{S}_+^n$ is self dual: $(\mathbb{S}_+^n)^* = \mathbb{S}_+^n$ . This means that the dual variable for a linear matrix inequality $\sum_i x_i M_i \succeq M_0$ is a positive semidefinite matrix $Y \succeq 0$ ;

Exponential Cone¶

PICOS can also reformulate several constraints using the exponential cone ExponentialCone, as it is the case for example for KullbackLeiblerConstraint. PICOS provides dual values for ExpConeConstraint, as computed by the solver, but dualization of those constraints is not yet supported.