Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems

DOI10.1080/10556780410001647203zbMath1072.65081OpenAlexW2017952273MaRDI QIDQ3156718

Xinhui Wang, San-Yang Liu, Hong-Wei Liu

Publication date: 11 January 2005

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

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

zbMATH Keywords

convergencesemidefinite programmingnumerical examplesmax-cut problemfeasible direction algorithmlow rank factorization1\}\) progammingquadratic \(\{-1

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20)

Related Items (4)

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions ⋮ A continuation algorithm for max-cut problem ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ A discrete dynamic convexized method for the max-cut problem

Cites Work

• Problems of distance geometry and convex properties of quadratic maps
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• 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
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Bundle Method for Semidefinite Programming
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• An Interior-Point Method for Semidefinite Programming
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization

This page was built for publication: Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems