Conference Agenda

It is only half the battle to find a good solution in mathematical optimization, as one needs to verify its quality by specifying a dual bound. When it comes to (mixed-integer) nonlinear programming ((MI)NLP), strong prerequisites such as constraint qualifications appear suitable for this, but may be difficult to verify computationally. In practice, solvers apply local refinement (e.g., piecewise linear approximations, spatial branching) or convexification strategies (e.g., alpha-Branch-and-Bound) 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 ((MI)QCP) and propose a global approximation of constraint functions by paraboloids, i.e., univariate quadratic terms. In particular, for each nonlinear constraint function, a binary search is applied to determine small numbers of paraboloids approximating it from either side if necessary. This leads to a relaxation of the original problem, namely to a quadratically constrained one. A solution of the latter then leads to a dual bound whose tightness depends on the approximation guarantee of the paraboloids. In summary, this motivates to solve (MI)NLP problems with solvers explicitly tailored to (MI)QCP problems.

We present decomposition-based methods for generating reformuations of complex optimization and control problems that can be solved easier than the original problem. The methods are implemented in the open-source frameworks Decogo and Decolearn. Numerical results for nonconvex MINLPs and machine learning problems are presented.