Exploring Nonlinear Kernels for Lipschitz Constant Estimation in Lower Bound Construction for Global Optimization

Bounds play a crucial role in guiding optimization algorithms, improving their speed and quality and providing optimality gaps. While Lipschitz constant-based lower bound construction is an effective technique, the quality of the linear bounds depends on the function’s topological properties. In this research, we improve upon this by incorporating nonlinear kernels and surrogate approximations to … Read more

Optimality-Based Discretization Methods for the Global Optimization of Nonconvex Semi-Infinite Programs

We use sensitivity analysis to design optimality-based discretization (cutting-plane) methods for the global optimization of nonconvex semi-infinite programs (SIPs). We begin by formulating the optimal discretization of SIPs as a max-min problem and propose variants that are more computationally tractable. We then use parametric sensitivity theory to design an efficient method for solving these max-min … Read more

Learning to Accelerate the Global Optimization of Quadratically-Constrained Quadratic Programs

We learn optimal instance-specific heuristics for the global minimization of nonconvex quadratically-constrained quadratic programs (QCQPs). Specifically, we consider partitioning-based mixed-integer programming relaxations for nonconvex QCQPs and propose the novel problem of strong partitioning to optimally partition variable domains without sacrificing global optimality. We design a local optimization method for solving this challenging max-min strong partitioning … Read more

Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0

For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that … Read more

A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities

We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate … Read more

Recursive McCormick Linearization of Multilinear Programs

Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more

Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition

This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the … Read more

Mixed-Integer Programming Techniques for the Minimum Sum-of-Squares Clustering Problem

The minimum sum-of-squares clustering problem is a very important problem in data mining and machine learning with very many applications in, e.g., medicine or social sciences. However, it is known to be NP-hard in all relevant cases and to be notoriously hard to be solved to global optimality in practice. In this paper, we develop … Read more

On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level

It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an arbitrarily … Read more

An oracle-based framework for robust combinatorial optimization

We propose a general solution approach for min-max-robust counterparts of combinatorial optimization problems with uncertain linear objectives. We focus on the discrete scenario case, but our approach can be extended to other types of uncertainty sets such as polytopes or ellipsoids. Concerning the underlying certain problem,the algorithm is entirely oracle-based, i.e., our approach only requires … Read more