An unconstrained approach for solving low rank SDP relaxations of {-1,1} quadratic problems

Luigi Grippo (), Laura Palagi, Mauro Piacentini () and Veronica Piccialli ()
Additional contact information
Luigi Grippo: Sapienza Universita' di Roma - Dipartimento di Informatica e Sistemistica, Roma, Italy.
Mauro Piacentini: Sapienza Universita' di Roma - Dipartimento di Informatica e Sistemistica, Roma, Italy.
Veronica Piccialli: Universita' di Tor Vergata - Dipartimento di Ingegneria dell'Impresa - via del Politecnico, 1-00133 Roma, Italy

No 2009-13, DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza"

Abstract: We consider low-rank semidefinite programming (LRSDP) relaxations of ±1 quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an effcient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes.

Keywords: semidefinite programming; low rank factorization; boolean quadratic problem; nonlinear programming (search for similar items in EconPapers)
Pages: 17 pages
Date: 2009-09
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/wpaper/2009-13.pdf First version, 2009 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:aeg:wpaper:2009-13

Access Statistics for this paper

More papers in DIS Technical Reports from Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza" Contact information at EDIRC.
Bibliographic data for series maintained by Antonietta Angelica Zucconi ( this e-mail address is bad, please contact ).