Sparse solutions to random standard quadratic optimization problems

DOI10.1007/s10107-012-0519-xzbMath1305.90323OpenAlexW2160625469MaRDI QIDQ378104

Jiming Peng, Xin Chen, Shu-Zhong Zhang

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-012-0519-x

zbMATH Keywords

computational complexityorder statisticsrelaxationquadratic optimizationsemidefinite optimizationprobability analysis

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Foundations of probability theory (60A99)

Related Items

Representations as elements in affine composition algebras, New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions, Iterative positive thresholding algorithm for non-negative sparse optimization, General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, Some accelerated alternating proximal gradient algorithms for a class of nonconvex nonsmooth problems, Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems, On random quadratic forms: supports of potential local maxima, On sparsity of the solution to a random quadratic optimization problem, Fast algorithms for sparse portfolio selection considering industries and investment styles, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Building a completely positive factorization, The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem, An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems, Two-stage stochastic standard quadratic optimization

Uses Software

• SDPT3
• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• An LPCC approach to nonconvex quadratic programs
• A FPTAS for computing a symmetric leontief competitive economy equilibrium
• On the distribution of the roots of certain symmetric matrices
• The difference between \(5\times 5\) doubly nonnegative and completely positive matrices
• Active constraints, indefinite quadratic test problems, and complexity
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• A clique algorithm for standard quadratic programming
• Algorithms for determining the copositivity of a given symmetric matrix
• On standard quadratic optimization problems
• A test for copositive matrices
• Separable standard quadratic optimization problems
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Quadratic-programming criteria for copositive matrices
• Approximation of the Stability Number of a Graph via Copositive Programming
• On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Some NP-complete problems in quadratic and nonlinear programming
• Continuous Characterizations of the Maximum Clique Problem
• Order Statistics
• Nash equilibria in random games
• Compressed sensing
• Random knapsack in expected polynomial time
• On copositive programming and standard quadratic optimization problems