  It is only half the job to find a good solution for a mathematical
optimization problem, as one needs to verify its quality by specifying a dual
bound. When it comes to mixed-integer nonlinear programming (MINLP), strong
prerequisites such as constraint qualifications appear suitable, but may be
difficult to verify computationally. In practice, solvers apply local
refinement or convexification strategies to retrieve tight dual bounds.
However, these concepts require appropriate big-M formulations, generate new
sub-problems, or struggle to represent non-convex characteristics in terms of
high accuracy, all of which can lead to long running times.
  As an alternative, we aim to leverage recent advances in mixed-integer
quadratically-constrained programming (MIQCP) and propose a global
approximation of constraint functions by paraboloids, \ie, univariate quadratic
terms. The approximation is retrieved as a solution to a mixed-integer linear
programming (MIP) problem. Further, for each nonlinear constraint function, we
solve such MIPs and determine small numbers of paraboloids approximating it
from either side. A replacement of the nonlinearities with the corresponding
quadratic functions leads to a quadratically-constrained relaxation of the
original problem. Solving the MIQCP relaxation then leads to a dual bound whose
tightness depends on the approximation guarantee of the paraboloids. In
summary, this approach enables solvers that are explicitly tailored for
quadratic constraints to solve MINLPs to global optimality.
