A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem

DOI10.1007/s10589-020-00261-4zbMath1465.05146OpenAlexW3125711631MaRDI QIDQ2028477

Hao Sun, Ting Kei Pong, Xinxin Li, Henry Wolkowicz

Publication date: 1 June 2021

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-020-00261-4

zbMATH Keywords

graph partitioningvertex separatorsemidefinite relaxationdoubly nonnegative relaxationfacial reductionmin-cutpeaceman-Rachford splitting method

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, A note on the SDP relaxation of the minimum cut problem, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Partitioning through projections: strong SDP bounds for large graph partition problems, A new stopping criterion for Eckstein and Bertsekas's generalized alternating direction method of multipliers

Uses Software

• Mosek
• SPGL1
• ADMM_QAP

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• ADMM_QAP
• An exact algorithm for solving the vertex separator problem
• The MIN-cut and vertex separator problem
• A multilevel bilinear programming algorithm for the vertex separator problem
• Semidefinite programming relaxations for the quadratic assignment problem
• An \(O(n)\) algorithm for projecting a vector on the intersection of a hyperplane and a box in \(\mathbb R^n\)
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• ADMM for the SDP relaxation of the QAP
• Semidefinite programming relaxations for the graph partitioning problem
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Bandwidth, Vertex Separators, and Eigenvalue Optimization
• A Semidefinite Programming Approach to Side Chain Positioning with New Rounding Strategies
• A Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming
• Convergence Study on the Symmetric Version of ADMM with Larger Step Sizes
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Regularity and Stability for Convex Multivalued Functions
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem