A Method for Convex Black-Box Integer Global Optimization

Understand

We study the problem of minimizing a convex function on a nonempty, finite subset of the integer lattice when the function cannot be evaluated at noninteger points.

• We propose a new underestimator that does not require access to (sub)gradients of the objective but, rather, uses secant linear functions that interpolate the objective function at previously evaluated points.
• These linear mappings are shown to underestimate the objective in disconnected portions of the domain.
• Therefore, the union of these conditional cuts provides a nonconvex underestimator of the objective.