A projected gradient algorithm for solving the maxcut SDP relaxation

DOI10.1080/10556780108805818zbMath1109.90341OpenAlexW2000602248MaRDI QIDQ2770188

Renato D. C. Monteiro, Samuel Burer

Publication date: 2001

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556780108805818

zbMATH Keywords

Semidefinite programmingApproximation algorithmSemidefinite relaxationMaxcutProjected gradient method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Methods of reduced gradient type (90C52)

Related Items

Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems, An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions, A continuation algorithm for max-cut problem, An effective iterated tabu search for the maximum bisection problem, Solving maximum-entropy sampling problems using factored masks, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, An entropy-regularized ADMM for binary quadratic programming, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, Drawing (complete) binary tanglegrams, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, A discrete filled function algorithm for approximate global solutions of max-cut problems, A multiple search operator heuristic for the max-k-cut problem, Preemptive and non-preemptive generalized min sum set cover, Canonical dual approach to solving the maximum cut problem, A discrete dynamic convexized method for the max-cut problem, Semidefinite programming for discrete optimization and matrix completion problems, Randomized heuristics for the Max-Cut problem, Polyhedral approximations of the semidefinite cone and their application, Block Coordinate Descent Methods for Semidefinite Programming, Solving semidefinite programs using preconditioned conjugate gradients, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, An interior method for nonconvex semidefinite programs

Uses Software

• SDPA
• COL

Cites Work

• Semidefinite programming relaxation for nonconvex quadratic programs
• An incomplete Cholesky factorization for dense symmetric positive definite matrices
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Solving Graph Bisection Problems with Semidefinite Programming
• A Spectral Bundle Method for Semidefinite Programming
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• An Interior-Point Method for Semidefinite Programming
• Unnamed Item