On the complexity of detecting convexity over a box

DOI10.1007/s10107-019-01396-xzbMath1445.90078arXiv1806.06173OpenAlexW2963961403MaRDI QIDQ2191776

Georgina Hall, Amir Ali Ahmadi

Publication date: 26 June 2020

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

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

zbMATH Keywords

computational complexityconvex optimizationconvexity detectioninterval positive semidefiniteness

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On the complexity of finding a local minimizer of a quadratic function over a polytope

Uses Software

• BARON
• Gurobi
• CVX
• MProbe

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faithful variable screening for high-dimensional convex regression
• Open questions in complexity theory for numerical optimization
• Several NP-hard problems arising in robust stability analysis
• BARON: A general purpose global optimization software package
• NP-hardness of deciding convexity of quartic polynomials and related problems
• On Tractable Approximations of Uncertain Linear Matrix Inequalities Affected by Interval Uncertainty
• Consistency of Multidimensional Convex Regression
• Convexity and Concavity Detection in Computational Graphs: Tree Walks for Convexity Assessment
• Some NP-complete problems in quadratic and nonlinear programming
• NP-Hardness of Some Linear Control Design Problems
• Establishing Convexity of Polynomial Lyapunov Functions and Their Sublevel Sets
• Extended Matrix Cube Theorems with Applications to μ-Theory in Control
• Analyzing mathematical programs using MProbe

This page was built for publication: On the complexity of detecting convexity over a box