Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
From MaRDI portal
Publication:2706347
DOI10.1137/S1052623400366218zbMath1010.90053OpenAlexW2071143636MaRDI QIDQ2706347
Kazuhide Nakata, Kazuo Murota, Kojima, Masakazu, Mituhiro Fukuda
Publication date: 19 March 2001
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s1052623400366218
Semidefinite programming (90C22) Interior-point methods (90C51) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches, Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems, A successive constraint approach to solving parameter-dependent linear matrix inequalities, Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets, Matrix Relaxations in Combinatorial Optimization, A constraint-reduced algorithm for semidefinite optimization problems with superlinear convergence, Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints, Sparse noncommutative polynomial optimization, Logarithmic barriers for sparse matrix cones, Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems, Fast implementation for semidefinite programs with positive matrix completion, GMRES-Accelerated ADMM for Quadratic Objectives, A conversion of an SDP having free variables into the standard form SDP, Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables, Large-scale semidefinite programming via a saddle point mirror-prox algorithm, Solving large-scale semidefinite programs in parallel, Cutting Plane Generation through Sparse Principal Component Analysis, Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity, Exploiting sparsity for the min \(k\)-partition problem, Distributed consensus-based solver for semi-definite programming: an optimization viewpoint, A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables, Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, Restricted Robinson constraint qualification and optimality for cardinality-constrained cone programming, Exact Recovery with Symmetries for Procrustes Matching, Linear optimization over homogeneous matrix cones, Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, Discussion on: ``A decomposition algorithm for KYP-SDPs, A new global algorithm for max-cut problem with chordal sparsity, KKT-based primal-dual exactness conditions for the Shor relaxation, Cardinality-constrained distributionally robust portfolio optimization, Strong SOCP Relaxations for the Optimal Power Flow Problem, A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, Block-sparse recovery of semidefinite systems and generalized null space conditions, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization, Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization, A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization, An efficient algorithm for maximum entropy extension of block-circulant covariance matrices, $LDL^T$ Direction Interior Point Method for Semidefinite Programming, Sparse quasi-Newton updates with positive definite matrix completion, COSMO: a conic operator splitting method for convex conic problems, Analysis of sparse quasi-Newton updates with positive definite matrix completion, TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity, Decomposition of arrow type positive semidefinite matrices with application to topology optimization, Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem, Sums of Squares and Sparse Semidefinite Programming, Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, Semidefinite programming for discrete optimization and matrix completion problems, A Bregman extension of quasi-Newton updates I: an information geometrical framework, A parallel interior point decomposition algorithm for block angular semidefinite programs, On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems, A Localization Approach to Improve Iterative Proportional Scaling in Gaussian Graphical Models, Second order cone programming relaxation of nonconvex quadratic optimization problems, On listing, sampling, and counting the chordal graphs with edge constraints, An improved semidefinite programming relaxation for the satisfiability problem, Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, A survey on conic relaxations of optimal power flow problem, Positive polynomials on projective limits of real algebraic varieties, Euclidean Distance Matrices and Applications, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Algorithm 996, Learning chordal extensions, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Preprocessing sparse semidefinite programs via matrix completion, Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy, Perturbed sums-of-squares theorem for polynomial optimization and its applications, Bounds on heat transfer for Bénard–Marangoni convection at infinite Prandtl number, Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP, Bregman primal-dual first-order method and application to sparse semidefinite programming, An overview of semidefinite relaxations for optimal power flow problem, Bounds on heat transport for convection driven by internal heating, On the robustness and scalability of semidefinite relaxation for optimal power flow problems, Unnamed Item, Multiplicity adjustment for temporal and spatial scan statistics using Markov property, A semidefinite optimization approach for the single-row layout problem with unequal dimensions, Bounds for Deterministic and Stochastic Dynamical Systems using Sum-of-Squares Optimization, Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Uses Software
