An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
From MaRDI portal
Publication:623464
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
semidefinite programmingnonlinear programmingexact penalty functionsmaxcut problemlow-rank factorization
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
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.
