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

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

Continuous problem formulations

  • Conic optimization (CO)

    A conic optimization problem (CO) with affine conic constraints has the form:

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

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

    This general formulation subsumes also linear optimization (by using linear domains).

  • Linear/simplex optimization (LO)

    Using the linear/simplex part of the toolbox one can also specify linear problems in the more familiar standard form:

    \[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+c^f & & \\ \mbox{subject to} & & & A x & = & b, \\ & b_l & \leq & x & \leq & b_u. \end{array}\end{split}\]

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 \integral\]

    for some index set \(I\).

  • Disjunctive constraints. Appends disjunctions of 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. Linear and conic problems can be extended with disjunctive constraints.