Friday, August 31, 2018

Conic modeling cheatsheet

As a supplement to the MOSEK Modeling Cookbook, here is s a quick reference guide to some useful conic models (click image for PDF):


Friday, August 17, 2018

Solving SDP with millions of matrix variables

Is it feasible in practice to solve semidefinite optimization problems with a huge number of matrix variables?

We recently received a problem from a structural engineering application with approximately the following  parameters:

  • 1 500 000 three-dimensional matrix variables,
  • 750 000 three-dimensional rotated quadratic cones,
  • $8\cdot 10^6$ scalar variables, $15\cdot 10^6$ linear constraints, $45\cdot 10^6$ nonzeros.

On a DELL PowerEdge R730 server with 2 Xeon E5-2687W v4 3.0GHZ the optimal solution is found in about 161 minutes on 24 threads using the latest MOSEK 8.1.0.59 with memory peaking at about 60GB.  Due to the nature of the problem we disabled the linear dependency check and otherwise used all standard parameter settings.

Friday, June 29, 2018

.NET Core support

From release 8.1.0.56 we initialize support for .NET Core, the cross-platform implementation of .NET.

MOSEK for .NET Core is distributed as a platform-independent NuGet package, which can be downloaded directly from our website. See the documentation for .NET APIs for installation instructions.

Friday, June 22, 2018

MOSEK at ISMP 2018

Here is a complete schedule of our talks at ISMP 2018 in chronological order:

SpeakerTitleSessionTimeRoom
Sven WieseThe Mixed-integer Conic Optimizer in MOSEKMixed-Integer Conic OptimizationMon, 5:00PMA. DURKHEIM, Bld. A
Henrik FribergProjection and presolve in MOSEK: exponential and power conesTheory and algorithms in conic linear programming 1Tue, 8:30AMS. LC5, Bld. L
Joachim DahlExtending MOSEK with exponential conesTheory and algorithms in conic linear programming 2Wed, 8:30AMS. 20, Bld. G
Erling AndersenMOSEK version 9Progress in Conic and MIP SolversWed, 3:15PMA. PITRES, Bld. O
MichaƂ AdamaszekExponential cone in MOSEK: overview and applicationsRelative Entropy Optimization IFri, 3:15PMS. LC5, Bld. L

Check the program for any last-minute changes.

The session on Mixed-Integer Conic Optimization (Mon, 5:00PM) is organized by Sven Wiese. The full program of that session is:

  • Lucas Letocart,  Exact methods based on SDP for the k-item quadratic knapsack problem
  • Tristan Gally, Knapsack Constraints over the Positive Semidefinite Cone
  • Sven Wiese, The Mixed-integer Conic Optimizer in MOSEK

Tuesday, June 12, 2018

Elementary intro to infeasibility certificates

We occasionally receive support questions asking about the meaning and practical use of infeasibility certificates, usually when the user expected the problem to be feasible. While an infeasibility certificate is a well-defined mathematical object based on Farkas' lemma, it is not intuitive for everyone how to use it to address the basic question of "What is wrong with my problem formulation?". We will try to explain this on a very simple example.

In this post we don't even consider optimization, but restrict to elementary linear algebra. Suppose we want to find a solution to a system of linear equations:

$$
\begin{array}{llllllllllll}
& 2x_1 & - & x_2 & + & x_3 & - & 3x_4 & + & x_5 & = & 1, \\
& & & x_2 & -& 2x_3 & & & +& x_5 & = & -1,\\
& 3x_1 &  & & - & x_3 & - & x_4 & & & = & 2, \\
& 2x_1 & + & x_2 & - & 3x_3 & - & 3x_4 & + & 3x_5 & = & -0.5.
\end{array}
$$

This system of linear equations is in fact infeasible (has no solution). One way to see it is to multiply the equations by coefficients given on the right-hand side and add them up:

$$
\begin{array}{lllllllllllll}
& 2x_1 & - & x_2 & + & x_3 & - & 3x_4 & + & x_5 & = & 1 & / \cdot (-1) \\
& & & x_2 & -& 2x_3 & & & +& x_5 & = & -1 & / \cdot (-2) \\
& 3x_1 &  & & - & x_3 & - & x_4 & & & = & 2 & / \cdot 0 \\
& 2x_1 & + & x_2 & - & 3x_3 & - & 3x_4 & + & 3x_5 & = & -0.5 & / \cdot 1 \\
\hline
&  &  &  &  &  &  &  &  & 0 & = & 0.5. &
\end{array}
$$

We get an obvious contradiction, which proves the system has no solution. The vector

$$ y = [-1, -2, 0, 1] $$

of weights used above is therefore a proof (certificate) of infeasibility. MOSEK produces such a certificate automatically. Here is a simple script in MATLAB that computes precisely that vector:


As output we get:


Here are a few comments:

  • General theory guarantees that the dual variable y is a convenient place that can store the certificate.
  • When a system of equations has no solution then an appropriate certificate is guaranteed to exist. This is a basic variant of Farkas' lemma, but it should be intuitively clear: your favorite method of solving linear systems (for instance Gaussian elimination) boils down to taking  successive linear combinations of equations, a process which ends up either with a solution or with an "obvious" contradiction of the form $0=1$.


Using the certificate to debug a model 


In the example above $y_3=0$ which means that the third equation does not matter: infeasibility is caused already by some combination of the 1st, 2nd and 4th equation. In many practical situations the infeasibility certificate $y$ will have very few nonzeros, and those nonzeros determine a subproblem (subset of equations) which alone cause infeasibility. The user can configure MOSEK to print an infeasibility report, which in our example will look like:



This report is nothing else than a listing of equations with nonzero entries in $y$, and $y$ is the difference between Dual lower and Dual upper. Analyzing this set (which hopefully is much smaller than the full problem) can help locate a possible modeling error which makes the problem infeasible.

To conclude, let us now phrase the above discussion in matrix notation. A linear equation system

$$ Ax=b $$

is infeasible if and only if there is a vector $y$ such that

$$ A^Ty = 0 \quad \mbox{and}\quad b^Ty \neq 0. $$

The situation is analogous for linear problems with inequality constraints. We will look at an example of that in another blog post.


Thursday, May 31, 2018

Perspective functions (and Luxemburg norms)

If $\varphi:\mathbb{R}_+\to\mathbb{R}$ is a convex function then its perspective function $\tilde{\varphi}:\mathbb{R}_+\times\mathbb{R}_+\to\mathbb{R}$ is defined as
$$\tilde{\varphi}(x,y) = y\varphi(\frac{x}{y}).$$
Moreover, under these conditions, the epigraph of the perspective function
$$\left\{(t,x,y)~:~t\geq y\varphi(\frac{x}{y})\right\}$$
(or, to be precise, its appropriate closure) is a convex cone. Here are some familiar examples:

  • $\varphi(x)=x^2$. Then $\tilde{\varphi}(x,y)=\frac{x^2}{y}$, familiar to some as quad-over-lin. The epigraph of $\tilde{\varphi}$, described by $ty\geq x^2$, is the Lorentz cone (rescaled rotated quadratic cone).
  • $\varphi(x)=x^p$. Then $\tilde{\varphi}(x,y)=\frac{x^p}{y^{p-1}}$ and the epigraph of $\tilde{\varphi}$, described equivalently by $t^{1/p}y^{1-1/p}\geq |x|$ is the 3-dimensional power cone (with parameter $p$).
  • $\varphi(x)=\exp(x)$. Then the epigraph $t\geq y\exp(x/y)$ is the exponential cone.
  • $\varphi(x)=x\log(x)$. Then the epigraph $t\geq x\log(x/y)$ is the relative entropy cone.

We bring this up in connection with a series of blogposts by Dirk Lorenz here and here. For a monotone increasing, convex, nonnegative $\varphi$ with  $\varphi(0)=0$ he defines a norm on $\mathbb{R}^n$ via
$$\|x\|_\varphi=\inf\left\{\lambda>0~:~\sum_i\varphi\left(\frac{|x_i|}{\lambda}\right)\leq 1\right\},$$
and we can ask when the norm bound $t\geq \|x\|_\varphi$ is conic representable. The answer is: if the epigraph of the perspective function $\tilde{\varphi}$ is representable, then so is the epigraph of $\|\cdot\|_\varphi$. The reason is that the inequality
$$\sum_i\varphi\left(\frac{|x_i|}{t}\right)\leq 1$$
is equivalent to
$$
\begin{array}{ll}
w_i\geq |x_i| & i=1,\ldots,n,\\
s_i\geq t\varphi\left(\frac{w_i}{t}\right) & i=1,\ldots,n,\\
t=\sum_i s_i. &
\end{array}
$$
That covers for example $\varphi(x)=x^2$, $\varphi(x)=x^p$ ($p>1$), $\varphi(x)=\exp(x)-1$, $\varphi(x)=x\log(1+x)$ and so on.
Figure: smallest $(\exp(x)-1)$-Luxemburg-norm disk containing a random set of points.

Wednesday, May 9, 2018

New Modeling Cookbook


We released a new, revised version of the MOSEK Modeling Cookbook



HTML     PDF (A4)     PDF (letter)

where you can find practical modeling examples and some theory behind:
  • linear optimization,
  • conic quadratic optimization,
  • the power cone,
  • the exponential cone (relative entropy cone),
  • semidefinite optimization,
  • duality in linear and conic optimization,
  • mixed-integer optimization,
  • quadraticaly constrained optimization,
  • and numerical issues.
The Modeling Cookbook is a general compendium of practical conic optimization. It is a generic mathematical publication without any code samples or references to the MOSEK API, although it covers areas of optimization that are supported by MOSEK 8 or the upcoming MOSEK 9.