Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
From MaRDI portal
Publication:2039245
DOI10.1007/s10107-020-01516-yzbMath1470.90070arXiv1710.03475OpenAlexW3101014297MaRDI QIDQ2039245
Javad Lavaei, Richard Y. Zhang
Publication date: 2 July 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.03475
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Large-scale problems in mathematical programming (90C06) Interior-point methods (90C51)
Related Items (5)
Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization ⋮ A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem ⋮ Bregman primal-dual first-order method and application to sparse semidefinite programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- On the robustness and scalability of semidefinite relaxation for optimal power flow problems
- Positive definite completions of partial Hermitian matrices
- Exact algorithms and applications for tree-like Weighted Set Cover
- Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP
- Positive semidefinite matrices with a given sparsity pattern
- Partitioned variable metric updates for large structured optimization problems
- Positive semidefinite completions of partial Hermitian matrices
- Symmetric primal-dual path-following algorithms for semidefinite programming
- Complementarity and nondegeneracy in semidefinite programming
- On implementing a primal-dual interior-point method for conic quadratic optimization
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- An independent benchmarking of SDP and SOCP solvers
- Introductory lectures on convex optimization. A basic course.
- Product-form Cholesky factorization in interior point methods for second-order cone programming
- A new graph parameter related to bounded rank positive semidefinite matrix completions
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Global Optimization with Polynomials and the Problem of Moments
- Decomposition in Conic Optimization with Partially Separable Structure
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- The Use of Linear Graphs in Gauss Elimination
- A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
- The Role of Elimination Trees in Sparse Factorization
- Dualize it: software for automatic primal and dual conversions of conic programs
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Complexity of Finding Embeddings in a k-Tree
- The Evolution of the Minimum Degree Ordering Algorithm
- Generalized Nested Dissection
- The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Algorithmic Aspects of Vertex Elimination on Graphs
- On the Shannon capacity of a graph
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- On the Nesterov--Todd Direction in Semidefinite Programming
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
- Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- SDPLIB 1.2, a library of semidefinite programming test problems
- GMRES-Accelerated ADMM for Quadratic Objectives
- Distributed Semidefinite Programming With Application to Large-Scale System Analysis
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach
- Logarithmic barriers for sparse matrix cones
- Algorithm 837
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
- Linear programming. Foundations and extensions
- Handbook of semidefinite programming. Theory, algorithms, and applications
This page was built for publication: Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
