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 $\epsilon$ gives an $O({\epsilon }^{-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.