Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
From MaRDI portal
Publication:5737726
DOI10.1137/14099379XzbMath1365.90185MaRDI QIDQ5737726
Javad Lavaei, Somayeh Sojoudi, Ghazal Fazelnia, Ramtin Madani
Publication date: 30 May 2017
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
semidefinite programminglinear matrix inequalitymatrix completiontree decompositionpolynomial optimizationoptimal power flowlow-rank optimization
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Convex programming (90C25) Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Quadratic programming (90C20) Convex functions and convex programs in convex geometry (52A41)
Related Items
Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem, A new global algorithm for max-cut problem with chordal sparsity, Convexification of generalized network flow problem, Penalized semidefinite programming for quadratically-constrained quadratic optimization, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Unnamed Item, Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the Grothendieck constant of some graph classes
- Treewidth computations. II. Lower bounds
- The minimum semidefinite rank of the complement of partial \(k\)-trees
- Null space conditions and thresholds for rank minimization
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Positive definite completions of partial Hermitian matrices
- Linearly independent vertices and minimum semidefinite rank
- Treewidth computations. I: Upper bounds
- Zero forcing parameters and minimum rank problems
- The minimum rank of symmetric matrices described by a graph: a survey
- Lower bounds in minimum rank problems
- A remark on the convexity and positive definiteness concerning Hermitian matrices
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- A remark on the rank of positive semidefinite matrices subject to affine constraints
- On convex relaxations for quadratically constrained quadratic programming
- A new graph parameter related to bounded rank positive semidefinite matrix completions
- Exact matrix completion via convex optimization
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Convex Relaxation for Optimal Distributed Control Problems
- On the Low Rank Solutions for Linear Matrix Inequalities
- Grothendieck inequalities for semidefinite programs with rank constraint
- Algorithms finding tree-decompositions of graphs
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
- Complexity of Finding Embeddings in a k-Tree
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Primal--Dual Path-Following Algorithms for Semidefinite Programming
- Graphs whose minimal rank is two
- Semidefinite Programming
- Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
- Solving Large-Scale Hybrid Circuit-Antenna Problems
- Exactness of Semidefinite Relaxations for Nonlinear Optimization Problems with Underlying Graph Structure
- Matrix Completion From a Few Entries
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- A Generalization of the Schur Complement by Means of the Moore–Penrose Inverse
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Quadratic forms on graphs