On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
From MaRDI portal
Publication:2757537
DOI10.1287/MOOR.23.2.339zbMath0977.90051OpenAlexW2005102197MaRDI QIDQ2757537
Publication date: 26 November 2001
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/fd220b2e331ec732c76e8f14794c68eeb2e24532
nonsmooth optimizationsemidefinite programmingsum of eigenvaluesmaximum eigenvalueeigenvalue-optimization
Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Nonlinear programming (90C30)
Related Items (84)
Exploiting low-rank structure in semidefinite programming by approximate operator splitting ⋮ Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems ⋮ Bounding duality gap for separable problems with linear constraints ⋮ The bundle scheme for solving arbitrary eigenvalue optimizations ⋮ Using the eigenvalue relaxation for binary least-squares estimation problems ⋮ Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems ⋮ On bounds of the Pythagoras number of the sum of square magnitudes of Laurent polynomials ⋮ Computable representations for convex hulls of low-dimensional quadratic forms ⋮ A Second-Order Bundle Method Based on -Decomposition Strategy for a Special Class of Eigenvalue Optimizations ⋮ Optimal Information Blending with Measurements in the L2 Sphere ⋮ Initialization in semidefinite programming via a self-dual skew-symmetric embedding ⋮ Stable Camera Motion Estimation Using Convex Programming ⋮ A SemiSmooth Newton Method for Semidefinite Programs and its Applications in Electronic Structure Calculations ⋮ The spectral bundle method with second-order information ⋮ Quadratic programs with hollows ⋮ Interplay of non-convex quadratically constrained problems with adjustable robust optimization ⋮ Clustering and feature selection using sparse principal component analysis ⋮ A space decomposition scheme for maximum eigenvalue functions and its applications ⋮ A survey of hidden convex optimization ⋮ Input design for discrimination between classes of LTI models ⋮ Exact computable representation of some second-order cone constrained quadratic programming problems ⋮ SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances ⋮ The Pythagoras number of real sum of squares polynomials and sum of square magnitudes of polynomials ⋮ A strengthened Barvinok-Pataki bound on SDP rank ⋮ Optimality conditions for nonlinear semidefinite programming via squared slack variables ⋮ Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis ⋮ An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem ⋮ A new perspective on low-rank optimization ⋮ Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs ⋮ A penalty decomposition algorithm with greedy improvement for mean‐reverting portfolios with sparsity and volatility constraints ⋮ The space decomposition method for the sum of nonlinear convex maximum eigenvalues and its applications ⋮ An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs ⋮ An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem ⋮ Revisiting degeneracy, strict feasibility, stability, in linear programming ⋮ A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming ⋮ Newsvendor games: convex optimization of centralized inventory operations ⋮ Solving graph equipartition SDPs on an algebraic variety ⋮ Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints ⋮ Using negative curvature in solving nonlinear programs ⋮ Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization ⋮ Low-Rank Univariate Sum of Squares Has No Spurious Local Minima ⋮ Linear Programming on the Stiefel Manifold ⋮ Clustering subgaussian mixtures by semidefinite programming ⋮ Moment inequalities for sums of random matrices and their applications in optimization ⋮ The generalized trust region subproblem ⋮ A brief introduction to manifold optimization ⋮ Extreme point inequalities and geometry of the rank sparsity ball ⋮ Duality and robust duality for special nonconvex homogeneous quadratic programming under certainty and uncertainty environment ⋮ Memory-Efficient Structured Convex Optimization via Extreme Point Sampling ⋮ Cone-LP's and semidefinite programs: Geometry and a simplex-type method ⋮ How to convexify the intersection of a second order cone and a nonconvex quadratic ⋮ A feasible dual affine scaling steepest descent method for the linear semidefinite programming problem ⋮ On the Simplicity and Conditioning of Low Rank Semidefinite Programs ⋮ An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity ⋮ Tightness of the maximum likelihood semidefinite relaxation for angular synchronization ⋮ New results on Hermitian matrix rank-one decomposition ⋮ Local minima and convergence in low-rank semidefinite programming ⋮ Noisy Euclidean distance matrix completion with a single missing node ⋮ A class of semidefinite programs with rank-one solutions ⋮ A survey on conic relaxations of optimal power flow problem ⋮ Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ Semidefinite spectral clustering ⋮ The analysis of multivariate data using semi-definite programming ⋮ Computational Approaches to Max-Cut ⋮ The trust region subproblem with non-intersecting linear constraints ⋮ Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems ⋮ A unifying framework for several cutting plane methods for semidefinite programming ⋮ On the Burer-Monteiro method for general semidefinite programs ⋮ Positive semidefinite rank ⋮ Rank Optimality for the Burer--Monteiro Factorization ⋮ Computational enhancements in low-rank semidefinite programming ⋮ Selection Consistency of Generalized Information Criterion for Sparse Logistic Model ⋮ Generalized Conditional Gradient for Sparse Estimation ⋮ On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models ⋮ Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming ⋮ Orthogonal Trace-Sum Maximization: Applications, Local Algorithms, and Global Optimality ⋮ Scalable Semidefinite Programming ⋮ Convex Hulls of Quadratically Parameterized Sets With Quadratic Constraints ⋮ Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs ⋮ Sequences with minimal time-frequency uncertainty ⋮ Semidefinite programming ⋮ Does optimality imply ill-posedness? some remarks about certain min-max optimization problems ⋮ Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
This page was built for publication: On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues