## 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.*