Sparse solutions to random standard quadratic optimization problems
From MaRDI portal
The authors refer to a standard quadratic optimization problem of minimizing a quadratic form over the standard simplex. The work is an initial attempt to establish the existence of sparse optimal globally solutions for a class of random matrices. Specially, when the upper triangular elements of the matrix, involved in the quadratic form, are identically independently distributed, with a uniform or exponential distribution. It has been proven that the probability that there exists a globally optimal solution with at least k nonzero elements decays exponentially (in \(k\)).
Recommendations
- New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions
- On standard quadratic optimization problems
- On sparsity of the solution to a random quadratic optimization problem
- The complexity of simple models -- a study of worst and typical hard cases for the standard quadratic optimization problem
- Separable standard quadratic optimization problems
Cites work
- A clique algorithm for standard quadratic programming
- A FPTAS for computing a symmetric leontief competitive economy equilibrium
- A test for copositive matrices
- Active constraints, indefinite quadratic test problems, and complexity
- Algorithms for determining the copositivity of a given symmetric matrix
- An LPCC approach to nonconvex quadratic programs
- Approximation of the stability number of a graph via copositive programming
- Compressed sensing
- Continuous Characterizations of the Maximum Clique Problem
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 734901 (Why is no real title available?)
- Nash equilibria in random games
- New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
- On copositive programming and standard quadratic optimization problems
- On standard quadratic optimization problems
- On the distribution of the roots of certain symmetric matrices
- On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
- Order Statistics
- Quadratic-programming criteria for copositive matrices
- Random knapsack in expected polynomial time
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Separable standard quadratic optimization problems
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Some NP-complete problems in quadratic and nonlinear programming
- The difference between \(5\times 5\) doubly nonnegative and completely positive matrices
Cited in
(18)- Separable standard quadratic optimization problems
- Building a completely positive factorization
- 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
- An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems
- Two-stage stochastic standard quadratic optimization
- On sparsity of the solution to a random quadratic optimization problem
- General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems
- Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
- New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions
- Representations as elements in affine composition algebras
- Iterative positive thresholding algorithm for non-negative sparse optimization
- On random quadratic forms: supports of potential local maxima
- The complexity of simple models -- a study of worst and typical hard cases for the standard quadratic optimization problem
- Some accelerated alternating proximal gradient algorithms for a class of nonconvex nonsmooth problems
- Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization
- General inertial alternating structure-adapted proximal gradient descent method for solving nonseparable nonconvex optimization problems
- On tractable convex relaxations of standard quadratic optimization problems under sparsity constraints
This page was built for publication: Sparse solutions to random standard quadratic optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378104)
