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

DOI10.1007/s10107-009-0275-8zbMath1206.90114OpenAlexW2000661792MaRDI QIDQ623464

Laura Palagi, Veronica Piccialli, Luigi Grippo

Publication date: 14 February 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-009-0275-8

zbMATH Keywords

semidefinite programmingnonlinear programmingexact penalty functionsmaxcut problemlow-rank factorization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonlinear programming (90C30)

Related Items

Computing the nearest low-rank correlation matrix by a simplified SQP algorithm, Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, SDP-based branch-and-bound for non-convex quadratic integer optimization, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, A feasible method for optimization with orthogonality constraints, Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs, Computational Approaches to Max-Cut, DSDP5

Uses Software

• SDPA
• SDPLR
• COL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
• Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems
• Experiments in quadratic 0-1 programming
• Laplacian eigenvalues and the maximum cut problem
• Problems of distance geometry and convex properties of quadratic maps
• Semidefinite programming in combinatorial optimization
• Connection between semidefinite relaxations of the max-cut and stable set problems
• First- and second-order methods for semidefinite programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• The cut polytope and the Boolean quadric polytope
• Nonmonotone globalization techniques for the Barzilai-Borwein gradient method
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• Local minima and convergence in low-rank semidefinite programming
• Multiplier and gradient methods
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• A projected gradient algorithm for solving the maxcut SDP relaxation
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
• Algorithm 875
• Matrix Analysis
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Exact Penalty Functions in Constrained Optimization
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Benchmarking optimization software with performance profiles.