Closed during Christmas

 During the Christmas period 2024 the MOSEK office, support and sales are not available on

24-29 and 31 December, 1 January

The MOSEK team

Second Order Christmas Programming

Santa's life used to be much easier. He would split his funds for the year equally between all children and give each child some gifts from their wishlist amounting to roughly that value. 

But the corporate rules are creeping in also beyond the Polar Circle and the Customer Satisfaction Department decided that from this year on every child should simply get all the presents they asked for in their letter, and they will even give Santa a budget exactly sufficient for that. While this method is also very simple, Santa is fuming: it is unfair, unsustainable in the long run and most of all against the spirit of Christmas. So after long negotiations the corporation made some concessions for Santa, so that the new distribution rules should balance between two objectives:

•  each child should receive gifts of total value similar to what they wished for,
•  children living close to each other should receive gifts of similar value.

Santa has since calmed down but he still has to find the right tradeoff of the objectives to both convince the corporate and not betray his ideals (too much). You have been tasked with helping him. The children live on an $n\times m$ grid, each one requested gifts of total value normalized to the interval $[0,1]$ and your budget is the total value of the requests.

Suppose the children have wishes of value $w(i,j)$, $i=1,\ldots,n$, $j=1,\ldots,m$ and Santa will assign them gifts of value $g(i,j)$, to be optimized. Then Santa (who is a big fan of SOCP and only ever works with the $L_2$-norm) would like to try an optimization problem such as $$\begin{array}{ll}\textrm{minimize} & \gamma_{\mathrm{ful}}\cdot \|g-w\|_2 + \gamma_{\mathrm{fair}} \cdot \|(\ldots,g_{i+1,j}-g_{i,j},g_{i,j+1}-g_{i,j},\ldots)_{i,j}\|_2 \\ \textrm{subject to} & \mathrm{sum}(g)=\mathrm{sum}(w).\end{array}$$

The first objective term represents fulfilment, and measures the gap between the gifts and expectations while the second represents fairness, and measures the total variation between each child and its immediate neighbours in the grid in terms of gift value, taken over the whole grid. Santa wants to experiment with the choices of weights, where setting $(\gamma_{\mathrm{ful}}, \gamma_{\mathrm{fair}}) = (0,1)$ will result in his good old equitable division and $(\gamma_{\mathrm{ful}}, \gamma_{\mathrm{fair}}) = (1,0)$ solves for the corporate idea of perfect fulfilment.

Fortunately for Santa this is straightforward in the MOSEK Fusion API for Python:

Now he is ready to experiment with the datasets for various areas, which he represents as heat maps with more red shift meaning more valuable gifts and more blue shift meaning cheaper gifts.

First column: the wishlists. Remaining columns: gift distributions from more emphasis on fairness to more emphasis on fulfilment.

Equipped with this knowledge Santa will have to propose some weights $(\gamma_{\mathrm{ful}}, \gamma_{\mathrm{fair}})$ and we leave him here with these considerations. Remember, if you don't like the direction Santa's service is going you can always switch to one of the many independent vendors, and you will find a list here: List of Christmas gift-bearers (Wikipedia) .

The interior-point optimizer in Mosek

 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.

For instance, the power and exponential cones are not symmetric; hence, the primal-dual algorithm by Y. Nesterov and M. Todd cannot be used to solve conic optimization problems. However, based on an  idea by L.Tuncel, the interior-point optimizer in Mosek has been extended to handle the exponential and power cones. The details of the extension to the exponential cone are presented in the paper.

   

 

MOSEK 11 beta released!

We are pleased to announce the release of MOSEK 11.0 Beta.

You will find all the necessary information, installation instructions and documentation on the website of the new version. To try it out you must obtain a new license file, either by applying/reapplying for a trial/academic license on our website or contacting our sales if a customer.

The main features of MOSEK 11 are

• substantial efficiency improvements in the mixed-integer optimizer,
• a new API for MATLAB,

and in the near future you can expect a series of blogposts discussing these topics in more detail.

Enjoy MOSEK 11 and we are looking forward to your feedback.

The MOSEK team

Autumn is coming!

 Currently we are experiencing some lovely summer weather here in Copenhagen, but there is a feeling that the autumn is right around the corner. For MOSEK the arrival of autumn means the arrival of thousands of new persons eligible to use MOSEK for free.

This is because MOSEK, through our academic initiative, grants free licenses for research or educational purposes at degree-granting academic institutions.

Whether you are a new student or a seasoned academic why not use this opportunity to try MOSEK!

MOSEK is a proud sponsor ISMP 2024

Next week the 25th International Symposium on Mathematical Programming will take place in Montreal. MOSEK is a proud sponsor of this conference. We will also have a presence at the conference. 

If you have inquiries about MOSEK that you want to address in person, your best bet is to look out for our CEO Erling D. Andersen at the conference.

If your happy with having your inquiry answered through email you can always reach out to support@mosek.com.  

Mosek is proud to sponsor EUROPT 2024.

This week starting on Wednesday June 26 EUROPT 2024 will be held at Lund university, hosted by the Department of Automatic Control.  

Moseks industrial phd student Utkarsh, along with his academic supervisor Martin S. Andersen, will be hosting a track on developments on the interior point method.

So if you are attending the conference and want to know more about Mosek, and maybe get your hands on a hard copy of our  Modelling Cookbook, keep on eye out for Utkarsh!

If you're not attending the conference you can always find our cookbook online and reach us at support@mosek.com or sales@mosek.com if you have any inquires.