Augmented Lagrangian Approaches for Solving Doubly Nonnegative Programs
Nell'ambito della procedura di valutazione di un Ricercatore a Tempo
Determinato tipologia B ai fini della chiamata nel ruolo di Professore di II fascia ai sensi
dell’art. 24, comma 5, legge 240/2010, SSD MAT/09 – SC 01/A6
Marianna De Santis terrà un seminario pubblico venerdì 20 Settembre
2019, ore 11.00, aula A5 (DIAG, Via Ariosto 25)
TITLE: Augmented Lagrangian Approaches for Solving Doubly Nonnegative Programs*
ABSTRACT
It is well known that semidefinite programming problems (SDPs) are solvable in polynomial time by interior point methods.
However, if the number of constraints m in an SDP is of order O(n^2), when the unknown positive semidefinite
matrix is n × n, interior point methods become impractical both in terms of the time and the amount
of memory required at each iteration. As a matter of fact, in order to compute the search direction,
Interior point methods need to form the m × m positive definite Schur complement matrix
M and find its Cholesky factorization.
On the other hand, first-order methods typically require much less computation effort per iteration,
as they do not form or factorize these large dense matrices. Furthermore, some first-order methods are
able to take advantage of problem structure such as sparsity. Hence, they are often more suitable,
and sometimes the only practical choice for solving large-scale SDPs.
Most existing first-order methods for SDP are based on the augmented Lagrangian method.
In this talk, we focus on doubly nonnegative problems (DNNs), namely semidefinite programming
problems where the elements of the matrix variable are constrained to be nonnegative.
Starting from two methods already proposed in the literature on conic programming,
we introduce Augmented Lagrangian methods with the possibility of employing a factorization
of the dual variable. We present numerical
results for instances of the DNN relaxation of the stable set problem,
including instances from the Second DIMACS Implementation Challenge.*