The Logical Anatomy of Optimization: Reverse Mathematics, Proof Mining, and the Price of Convergence
Source: hexagonmath.org/abs/2611.00217v1
Optimization theory proves three kinds of theorems: that optimal points exist, that algorithms converge to them, and that optimality can be certified by duality. We measure how much mathematics each kind needs, using reverse mathematics, Weihrauch complexity and proof mining, and assemble the answers, old and new, into one map stated in the language of optimization. Compactness makes existence cost weak Kőnig's lemma, but convexity (and, format by format, tameness) makes it cheap: we show that $\mathsf{RCA}_0$ proves that convex functions on $[0,1]$ attain their minima (and on $[0,1]^n$, for…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00217
curl -X POST /api/v1/records/hexagon/2611.00217/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00217/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'