Journées de l'optimisation 2009 Optimizations days

The max-cut algorithm of Goemans and Williamson is 15 years old in 2009, and its impact in the area of semidefinite programming has been remarkable. In this talk, I will survey some of the main modelling and algorithmic developments since 1994 in the application of semidefinite programming to discrete optimization problems. I will also highlight promising directions for research in this area.

We describe a new technique of using an interior-point method for the solution of linear and semidefinite programming relaxations of discrete optimization problems. The approach combines an infeasible interior-point algorithm with a cutting-plane scheme that does not require to solve successive relaxations to optimality but adds and removes cuts already at intermediate iterates based on feasibility indicators of the cut violation and warm starts of the new variable slacks. Showing encouraging computational results for several max-cut instances and single-row facility-layout problems, we conclude that our method is robust and can find optimal solutions faster than traditional cutting-plane methods.

We investigate a smoothing technique to solve large-scale instances of a class of LPs that arise from machine learning context. When applied to our problem, Nesterov’s smoothing technique requires a parameter that bounds the optimal value from above. We design a scheme that dynamically updates the parameter to speed up the convergence.