Solving semidefinite programs using preconditioned conjugate gradients

DOI10.1080/1055678042000193162zbMath1068.90088OpenAlexW1966581112MaRDI QIDQ5460654

Henry Wolkowicz

Publication date: 18 July 2005

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

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

zbMATH Keywords

semidefinite programminglarge sparse problemspreconditioned conjugate gradientscrossoverMax-cut probleminexact Gauss-Newton method

Mathematics Subject Classification ID

Semidefinite programming (90C22) Methods of quasi-Newton type (90C53) Methods of reduced gradient type (90C52)

Related Items

A stable primal-dual approach for linear programming under nondegeneracy assumptions, Solving Hankel matrix approximation problem using semidefinite programming, Generating and measuring instances of hard semidefinite programs, Approximate Toeplitz matrix problem using semidefinite programming, Preprocessing and Regularization for Degenerate Semidefinite Programs, A robust algorithm for semidefinite programming, Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming, A semidefinite optimization approach for the single-row layout problem with unequal dimensions

Uses Software

• COL
• KELLEY
• SPARSE-QR

Cites Work

• Unnamed Item
• Initialization in semidefinite programming via a self-dual skew-symmetric embedding
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Condition numbers and equilibration of matrices
• Convergence of a short-step primal-dual algorithm based on the Gauss-Newton direction
• A Scaled Gauss--Newton Primal-Dual Search Direction for Semidefinite Optimization
• A projected gradient algorithm for solving the maxcut SDP relaxation
• Sizing and Least-Change Secant Methods
• The Gauss-Newton direction in semidefinite programming
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Inexact Newton Methods
• Sparse QR factorization in MATLAB
• Strong Duality for Semidefinite Programming
• A study of search directions in primal-dual interior-point methods for semidefinite programming
• A Spectral Bundle Method for Semidefinite Programming
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate
• Geometry of cuts and metrics