12 Problem Formulation and Solutions

In this chapter we will discuss the following issues:

  • 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. Below is an outline of the various formats. For details see the corresponding subesctions.

12.1 Continuous problem formulations

  • Sec. 12.2.1 (Linear Optimization)

    A linear problem has the form

    \[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x. \end{array}\end{split}\]
  • Sec. 12.2.2 (Conic Optimization)

    Conic optimization extends linear optimization with affine conic constraints (ACC), so a conic problem has the form

    \[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \\ & & & Fx+g & \in & \D, \end{array}\end{split}\]

    where \(\D\) is a product of domains from Sec. 15.10 (Supported domains).

  • Sec. 12.2.3 (Semidefinite Optimization)

    A conic optimization problem can be further extended with semidefinite variables, leading to a semidefinite optimization problem of the form

    \[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+ \langle \barC,\barX\rangle + c^f & & \\ \mbox{subject to} & l^c & \leq & A x + \langle \barA,\barX\rangle & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \\ & & & Fx+\langle \barF,\barX\rangle +g & \in & \D, \\ & & & \barX & \in & \PSD, \end{array}\end{split}\]

    where \(\D\) is a product of domains from Sec. 15.10 (Supported domains) and \(\PSD\) is a product of PSD cones meaning that \(\barX\) is a sequence of PSD matrix variables.

  • Sec. 12.2.4 (Quadratic and Quadratically Constrained Optimization)

    A quadratic problem or quadratically constrained problem has the form

    \[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & \frac12 x^TQ^ox + c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & \frac12 x^TQ^cx+ A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x. \end{array}\end{split}\]

12.2 Mixed-integer problem formulations

  • Integer variables. A linear, conic or quadratic problem without semidefinite variables or domains can be extended with the specification of integer variables, that is

    \[x_I \in \integral\]

    for some index set \(I\). A problem with at least one integer variable is solved by the mixed-integer optimizer.

  • Disjunctive constraints. A linear or conic problem without semidefinite variables or domains can be extended with disjunctive constraints (DJC). A single disjunctive constraint has the form

    \[\bigvee_{i=1}^t \bigwedge_{j=1}^{s_i} \left(D_{ij}x+d_{ij} \in \mathcal{D}_{ij} \right)\]

    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 \(\D_{ij}\) is an affine domain. A problem with at least one disjunctive constraint is solved by the mixed-integer optimizer.