Complexity aspects of local minima and related notions

DOI10.1016/j.aim.2021.108119zbMath1485.90090arXiv2008.06148OpenAlexW3216451529MaRDI QIDQ2074805

Amir Ali Ahmadi, Jeffrey Zhang

Publication date: 11 February 2022

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.06148

zbMATH Keywords

computational complexitysemidefinite programminglocal minimapolynomial optimizationsum of squares polynomialscritical and second-order points

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Polynomial optimization (90C23)

Related Items (2)

Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph ⋮ On the complexity of finding a local minimizer of a quadratic function over a polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Open questions in complexity theory for numerical optimization
• Semidefinite representation of convex sets
• On semidefinite representations of non-closed sets
• On the complexity of semidefinite programs
• An exact duality theory for semidefinite programming and its complexity implications
• Some geometric results in semidefinite programming
• The hierarchy of local minimums in polynomial optimization
• A new decision method for elementary algebra
• Approximation of the Stability Number of a Graph via Copositive Programming
• WHAT IS...a Spectrahedron?
• Some NP-complete problems in quadratic and nonlinear programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Semidefinite Programming
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• Convex Analysis

This page was built for publication: Complexity aspects of local minima and related notions