On the Non-Computability of Convex Optimization Problems
Holger Boche, Andrea Grigorescu, Technical University of Munich, Germany; Rafael F. Schaefer, Technische Universität Dresden, Germany; H. Vincent Poor, Princeton University, United States
Session:
Complexity and Computation Theory 1
Track:
21: Other topics
Location:
Lamda
Presentation Time:
Fri, 12 Jul, 10:05 - 10:25
Session Chair:
Shuki Bruck, California Institute of Technology
Abstract
This paper explores the computability of the optimal point in convex problems with inequality constraints. It is shown that feasible sets, defined by computable convex functions, can yield non-computable optimal points for strictly convex and computable objective functions. Additionally, the optimal point of the Lagrangian dual problem associated with such convex constraints is also proven to be non-computable. Despite converging sequences of computable numbers towards the Lagrangian's optimal point, algorithmic control of the approximation error is shown to be impossible.