DC decompositions and cutting-plane approximation: geometry and complexity
Abstract
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 accepted cuts. For an adaptive global DC method, this also bounds the number of subproblems solved exactly and globally. Under nondegeneracy, the exponent is sharp for uniform cutting-plane approximation of quadratic first components. A structured example reduces the certified exponent from n/2 to 1/2 and the global subproblem to one variable.
Related
- An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support
- A Hereditary Property of Cutting Plane Procedures
- A variational quantum eigensolver-based cutting plane framework for semidefinite programming problems
- Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
- Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors
BibTeX
@misc{pirani2026decompositions,
title = {{DC decompositions and cutting-plane approximation: geometry and complexity}},
author = {Fahaar M. Pirani},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28319},
eprint = {2609.28319},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28319},
}
RIS
TY - UNPB
TI - DC decompositions and cutting-plane approximation: geometry and complexity
AU - Fahaar M. Pirani
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2609.28319
UR - https://arxiv.org/abs/2609.28319
AB - 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 accepted cuts. For an adaptive global DC method, this also bounds the number of subproblems solved exactly and globally. Under nondegeneracy, the exponent is sharp for uniform cutting-plane approximation of quadratic first components. A structured example reduces the certified exponent from n/2 to 1/2 and the global subproblem to one variable.
ER -