Abstract We propose an approach based on quadratic approximations for solving general Mixed-Integer Nonlinear Programming (MINLP) problems. Specifically, our approach entails the global approximation of the epigraphs of constraint functions by means of paraboloids, which are polynomials of degree two with univariate quadratic terms, and relies on a Lipschitz property only. These approximations are then integrated into the original problem. To this end, we introduce a novel approach to compute globally valid epigraph approximations by paraboloids via a Mixed-Integer Linear Programming (MIP) model. We emphasize the possibility of performing such approximations a-priori and providing them in form of a lookup table, and then present several ways of leveraging the approximations to tackle the original problem. We provide the necessary theoretical background and conduct computational experiments on instances of the MINLPLib. As a result, this approach significantly accelerates the solution process of MINLP problems, particularly those involving many trigonometric or few exponential functions. In general, we highlight that the proposed technique is able to exploit advances in Mixed-Integer Quadratically-Constrained Programming (MIQCP) to solve MINLP problems.

Abstract In this paper, we consider a finite-dimensional optimization problem minimizing a continuous objective on a compact domain subject to a multi-dimensional constraint function. For the latter, we assume the availability of a global Lipschitz constant. In recent literature, methods based on non-convex outer approximation are proposed for tackling one-dimensional equality constraints that are Lipschitz with respect to the maximum norm. To the best of our knowledge, however, there does not exist a non-convex outer approximation method for a general problem class. We introduce a meta-level solution framework to solve such problems and tackle the underlying theoretical foundations. Considering the feasible domain without the constraint function as manageable, our method relaxes the multidimensional constraint and iteratively refines the feasible region by means of norm-induced cuts, relying on an oracle for the resulting subproblems. We show the method’s correctness and investigate the problem complexity. In order to account for discussions about functionality, limits, and extensions, we present computational examples including illustrations.