12 Problem Formulation and Solutions

In this chapter we will discuss the following topics:

• The formal, mathematical formulations of the problem types that MOSEK can solve and their duals.

• The solution information produced by MOSEK.

• The infeasibility certificate produced by MOSEK if the problem is infeasible.

For the underlying mathematical concepts, derivations and proofs see the Modeling Cookbook or any book on convex optimization. This chapter explains how the related data is organized specifically within the MOSEK API.

• 12.1 Linear Optimization
• 12.2 Conic Optimization
• 12.3 Semidefinite Optimization
• 12.4 Quadratic and Quadratically Constrained Optimization

Below is an outline of the different problem types for quick reference.

Continuous problem formulations

• Linear optimization (LO)

  $$\begin{array}{r}\begin{array}{lccccl}\text{minimize}& & & c^{T}x+c^f& & \\ \text{subject to}& l^c& \le & Ax& \le & u^c,\\ & l^x& \le & x& \le & u^x.\end{array}\end{array}$$

• Conic optimization (CO)

  Conic optimization extends linear optimization with affine conic constraints (ACC):

  $$\begin{array}{r}\begin{array}{lccccl}\text{minimize}& & & c^{T}x+c^f& & \\ \text{subject to}& l^c& \le & Ax& \le & u^c,\\ & l^x& \le & x& \le & u^x,\\ & & & Fx+g& \in & \mathcal{D},\end{array}\end{array}$$

  where $\mathcal{D}$ is a product of domains from Sec. 15.11 (Supported domains).

• Semidefinite optimization (SDO)

  A conic optimization problem can be further extended with semidefinite variables:

  $$\begin{array}{r}\begin{array}{lccccl}\text{minimize}& & & c^{T}x+⟨\bar{C},\bar{X}⟩+c^f& & \\ \text{subject to}& l^c& \le & Ax+⟨\bar{A},\bar{X}⟩& \le & u^c,\\ & l^x& \le & x& \le & u^x,\\ & & & Fx+⟨\bar{F},\bar{X}⟩+g& \in & \mathcal{D},\\ & & & \bar{X}& \in & {\mathcal{S}}_{+},\end{array}\end{array}$$

  where $\mathcal{D}$ is a product of domains from Sec. 15.11 (Supported domains) and ${\mathcal{S}}_{+}$ is a product of PSD cones meaning that $\bar{X}$ is a sequence of PSD matrix variables.

• Quadratic and quadratically constrained optimization (QO, QCQO)

  A quadratic problem or quadratically constrained problem has the form

  $$\begin{array}{r}\begin{array}{lccccl}\text{minimize}& & & \frac{1}{2}{x}^T{Q}^{o}x+c^{T}x+c^f& & \\ \text{subject to}& l^c& \le & \frac{1}{2}{x}^T{Q}^{c}x+Ax& \le & u^c,\\ & l^x& \le & x& \le & u^x.\end{array}\end{array}$$

Mixed-integer extensions

Coninuous problems can be extended with constraints requiring the mixed-integer optimizer. We outline them briefly here. The continuous part of a mixed-integer problem is formulated according to one of the continuous types above, however only the primal information and solution fields are relevant, there are no dual values and no infeasibility certificates.

• Integer variables. Specifies that a subset of variables take integer values, that is

  $$x_I\in \mathbb{Z}$$

  for some index set $I$.

• Disjunctive constraints. Appends disjunctions of the form

  $$\underset{i=1}{\overset{t}{\bigvee }}\underset{j=1}{\overset{s_i}{\bigwedge }}(D_{ij}x+d_{ij}\in {\mathcal{D}}_{ij})$$

  ie. a disjunction of conjunctions of linear constraints, where each $D_{ij}x+d_{ij}$ is an affine expression of the optimization variables and each ${\mathcal{D}}_{ij}$ is an affine domain. Linear and conic problems can be extended with disjunctive constraints.