Semidefinite Programming refers to optimization problems where the vector variable is a symmetric matrix constrained to be positive semidefinite.
Interest on semidefinite programming has grown tremendously during the last two decades and this is partly due to the fact that many practical problems in operations research and combinatorial optimization can be modeled or approximated by semidefinite programs.
Furthermore, semidefinite programs can be solved in polynomial time by interior point methods. However, when the dimension of the problem and the number of constraints get large, interior point methods become impractical both in terms of computation time and memory requirements.
It is the purpose of the present project to focus on augmented Lagrangian methods, known to be an alternative to interior point methods for solving large-scale semidefinite programs.
In our project, we plan to devise, implement and test new augmented Lagrangian algorithms for solving large-scale semidefinite programs. We also plan to focus on structured semidefinite programs, obtained as continuous relaxation of specific combinatorial optimization problems.
The augmented Lagrangian methods developed will represent an efficient tool to compute valid bounds on the optimal solution of the combinatorial problems considered.
The challenging nature of large-scale semidefinite programming problems increasingly calls for the development of efficient solution methods.
From the methodological point of view, the research activity will be carried out along the following topics:
1) Large-scale SDPs and doubly nonnegative programs.
Starting from a standard SDP, the majority of first-order methods deal with the Augmented Lagrangian function for the dual problem (see e.g. [16]). The classic augmented Lagrangian methods iterates two steps: the approximate maximization of the augmented Lagrangian function and the update of the multiplier by a first-order rule, that depends on the penalty parameter (see Chapter 2 in [2] for further details).
In an alternating direction framework the augmented Lagrangian function is maximized with respect to the dual variables one after the other. This leads to an alternating direction method of multipliers (ADMM).In our project, we also plan to consider the Augmented Lagrangian function for the dual problem and devise alternating direction methods of multipliers for solving large-scale SDPs .
Thanks to the use of projections onto the semidefinite cone, ADMMs are able to estimate the rank of the optimal solution along the iterations. This ability, in our opinion, is not fully exploited: once the optimal rank is detected, it should be possible to compute the optimal solution to any desired accuracy.
We plan to study the use of projections in order to define ADMMs able to compute solutions with high accuracy. We also plan to study and adopt similar strategies as the one presented in [13], where a semismooth Newton-Conjugate Gradient method has been integrated in the maximization of the augmented Lagrangian.
2) Computation of Valid Bounds.
It is known that first order methods are not suitable to compute high precision optimal solutions. However, when dealing with the dual problem, an optimal solution of moderate precision often suffices to get high quality bounds on the primal optimal objective function value.
A central topic of the project will be the study of how to compute such valid bounds, ideally constructing a dual feasible solution from a dual approximate (non feasible in general) optimal solution. Our aim is to get valid (and good) bounds on the optimal solution of a combinatorial problem after applying few iterations of a first order method to the dual of an SDP relaxation.
A first work we will take into account in this direction is the one by Jansson and coauthors [6], where perturbation of the dual objective function are considered.
3) The stable set problem and its SDP relaxations.
The first use of semidefinite programming in combinatorial problems dates back to Lovász [8], who introduced a semidefinite relaxation of the stable set polytope, the so-called theta body.
Given a graph G, the Lovász theta function theta(G), defined as the optimal value of an SDP, gives an upperbound on the stability number of a graph. This bound can be streghtened solving a doubly nonnegative problem, namely introducing the nonnegativity constraint on the primal variable of the SDP [12]. Compared to theta(G), this leads to a stronger bound on the stability number of G, as the copositive cone is better approximated.
One of the aim of the project is the computation of valid and strong bounds on the stability number of graphs taken from the famous benchmark of the second DIMACS implementation challenge [7].
Our aim is being able to compute these bounds efficiently, beating available approaches in terms of quality and computational time required.
---
For the references: See "Descrizione delle attività e dei compiti dei partecipanti"