Norm-induced cuts: outer approximation for Lipschitzian constraint functions

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.