Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

DOI10.1287/MOOR.1090.0408MaRDI QIDQ3169071zbMATH OpenOpenAlexFDO

Authors Robert M. Freund, Jorge R. Vera

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/55961

zbMATH Keywords

computational complexityconvex optimizationellipsoid algorithm

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Inequalities and extremum problems involving convexity in convex geometry (52A40) Convex functions and convex programs in convex geometry (52A41) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Oracle complexity separation in convex optimization
• Oracle complexities for computional geometry of semi-algebraic sets and voronoi diagrams
• Complexity analysis for certain convex programming problems
• Some results of convex programming complexity
• On the complexity of polyhedral separability
• On convex complexity measures
• Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems
• The complexity of cover inequality separation
• scientific article; zbMATH DE number 5302815
• scientific article; zbMATH DE number 1985308

Cited in

(3)

• On the complexity of the separation problem for rounded capacity inequalities
• Randomized interior point methods for sampling and optimization
• Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization

This page was built for publication: Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169071)