DC decompositions and cutting-plane approximation: geometry and complexity
We study how Difference of Convex (DC) decomposition affects cutting-plane approximation in global optimization. For a smooth decomposition $f = g-h$, let $d$ be the dimension of the span of all Hessian ranges of $g$ over the convex hull of a compact feasible set. The smallest attainable dimension equals the minimum rank of a constant positive semidefinite matrix majorizing the Hessians of $f$ on that convex hull, and is attained by a quadratic first component. Retaining earlier gradient cuts and accepting new cuts only when the model error exceeds $ε$ gives an $O(ε^{-d/2})$ bound on…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.28319
curl -X POST /api/v1/records/arxiv/2609.28319/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28319/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'