Mosek features
- a simplex optimizer,
- an interior-point optimizer
- and a mixed integer optimizer.
In this post, we review the history of the interior-point optimizer in Mosek and provide references to relevant publications for further information.
The interior-point optimizer implements a primal-dual interior-point algorithm invented in the decade after the groundbreaking 1984 publication of a polynomial algorithm for linear optimization by N. Karmarkar. Mosek employs the so-called homogeneous self-dual variant which has the following advantages:
- a starting point is readily available.
- reliable detection of a potential primal and dual infeasibility.
- robustness.
The note describes an elementary version of the algorithm for linear optimization problems. Furthermore, the paper provides some details about how the algorithm is actually implemented in Mosek.
In the early nineties, the primal-dual interior-point algorithm for linear optimization problems was generalized to conic optimization problems involving the so-called self-scaled cones by Y. Nesterov and M. Todd. Later a self-scaled cone was shown to be the same as a symmetric cone. Inspired by the work of the late J. Sturm on the software package SeDuMi the interior-point optimizer in Mosek was extended to handle the
- the quadratic cone,
- and the semi-definite cone.
The paper has a lot of details about the algorithm and its implementation in Mosek for the conic quadratic case.
By definition a symmetric cone is
- self-dual
- and homogeneous.
