@inproceedings{a09a735aaeab4c4699c7d54ce6aeb3a3,
title = "On the Convexification of Non-Linear Optimization Problems under Performance Guarantees",
abstract = "The convexification operator is the mapping that determines for every given continuous function on the real axis its greatest convex minorant. It is needed to convexify non-convex optimization problems in order to apply powerful convex optimization techniques to solve them. This paper shows that the convexification operator cannot be implemented on a Turing machine. In particular, we show that there exist piecewise linear continuous functions with a unique global minimum such that their greatest convex minorant is not Turing computable. Furthermore, for these functions there do not even exist monotonically increasing, computable sequences of convex computable continuous functions that converge to the greatest convex minorant. The same results also hold for the least concave majorants of continuous functions.",
author = "Holger Boche and Volker Pohl and Poor, \{H. Vincent\}",
note = "Publisher Copyright: {\textcopyright} 2025 IEEE.; 64th IEEE Conference on Decision and Control, CDC 2025 ; Conference date: 09-12-2025 Through 12-12-2025",
year = "2025",
doi = "10.1109/CDC57313.2025.11312941",
language = "English (US)",
series = "Proceedings of the IEEE Conference on Decision and Control",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "8136--8142",
booktitle = "2025 IEEE 64th Conference on Decision and Control, CDC 2025",
address = "United States",
}