TY - INPR A1 - Göß, Adrian A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Sharma, Kartikey T1 - Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions N2 - Optimal control problems usually involve constraints which model physical states and their possible transitions. These are represented by ordinary or partial differential equations (ODEs/PDEs) which add a component of infinite dimension to the problem. In recent literature, one method to simulate such ODEs/PDEs are physics-informed neural networks. Typically, neural networks are highly non-linear which makes their addition to optimization problems challenging. Hence, we leverage their often available Lipschitz property on a compact domain. The respective Lipschitz constants have to be computed only once and are accessible thereafter. We present a method that, based on this property, iteratively adds cuts involving the violation of the constraints by the current incumbent and the Lipschitz constant. Hereby, the “shape” of a cut depends on the norm used. We prove the correctness of the method by showing that it either returns an optimal solution when terminating or creates a sequence with optimal accumulation points. This is complemented by a discussion about the termination in the infeasible case, as well as an analysis of the problem complexity. For the analysis, we show that the lower and upper iteration bound asymptotically coincide when the relative approximation error goes to zero. In the end, we visualize the method on a small example based on a two-dimensional non-convex optimization problem, as well as stress the necessity of having a globally optimal oracle for the sub-problems by another example. KW - Global Optimization KW - Lipschitz Optimization KW - Black-box Optimization KW - Derivative-free Optimization Y1 - ER - TY - INPR A1 - Göß, Adrian A1 - Burlacu, Robert A1 - Martin, Alexander T1 - Parabolic Approximation & Relaxation for MINLP N2 - 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. KW - mixed-integer nonlinear programming KW - mixed-integer linear programming KW - quadratic approximation KW - global optimization Y1 - 2025 ER - TY - INPR A1 - Hildebrand, Robert A1 - Göß, Adrian T1 - Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover N2 - We study the complexity of identifying the integer feasibility of reverse convex sets. We present various settings where the complexity can be either NP-Hard or efficiently solvable when the dimension is fixed. Of particular interest is the case of bounded reverse convex constraints with a polyhedral domain. We introduce a structure, Boundary Hyperplane Cover, that permits this problem to be solved in polynomial time in fixed dimension provided the number of nonlinear reverse convex sets is fixed. Y1 - ER -