In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the special structure of the constraints and we use this function to define an efficient and globally convergent algorithm. Finally, we test our code on an extended set of instances of the maxcut problem and we report comparisons with other existing codes. © 2009 Springer and Mathematical Programming Society.

An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem / Grippo, Luigi; Palagi, Laura; Piccialli, Veronica. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 126:1(2011), pp. 119-146. [10.1007/s10107-009-0275-8]

An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem

GRIPPO, Luigi;PALAGI, Laura;PICCIALLI, Veronica
2011

Abstract

In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the special structure of the constraints and we use this function to define an efficient and globally convergent algorithm. Finally, we test our code on an extended set of instances of the maxcut problem and we report comparisons with other existing codes. © 2009 Springer and Mathematical Programming Society.
exact penalty functions; low-rank factorization; maxcut problem; nonlinear programming; semidefinite programming
01 Pubblicazione su rivista::01a Articolo in rivista
An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem / Grippo, Luigi; Palagi, Laura; Piccialli, Veronica. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 126:1(2011), pp. 119-146. [10.1007/s10107-009-0275-8]
File allegati a questo prodotto
File Dimensione Formato  
VE_2011_11573-44430.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 332.28 kB
Formato Adobe PDF
332.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/44430
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact