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

• 成果类型: Article
• 署名作者: Grippo, Luigi; Palagi, Laura; Piccialli, Veronica
• 署名单位: University of Rome Tor Vergata; Sapienza University Rome
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0275-8
• 发表日期: 2011
• 页码: 119-146
• 关键词: semidefinite programs; Combinatorial Optimization; Approximation algorithms; maximum cut; eigenvalues; performance

摘要

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.