global optimization

Strong Partitioning and a Machine Learning Approximation for Accelerating the Global Optimization of Nonconvex QCQPs

  • Rohit Kannan
  • Harsha Nagarajan
  • Deepjyoti Deka
    • Categories Global Optimization Tags , , , , , ,

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

    Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0

  • Ksenia Bestuzheva
  • Antonia Chmiela
  • Benjamin Müller
  • Felipe Serrano
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software and Modeling Systems Tags , , ,

    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

  • Julia Grübel
  • Richard Krug
  • Martin Schmidt
  • Winnifried Wollner
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Global Optimization Tags , , , ,

    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

  • Arvind U. Raghunathan
  • Carlos Cardonha
  • David Bergman
  • Carlos Nohra
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , ,

    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

  • Ching-pei Lee
  • Ling Liang
  • Tianyun Tang
  • Kim-Chuan Toh
    • Categories Global Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    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

  • Jan Pablo Burgard
  • Carina Moreira Costa
  • Christopher Hojny
  • Kleinert Thomas
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Data-Mining Tags , , ,

    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

  • Yasmine Beck
  • Martin Schmidt
  • Johannes Thürauf
  • Daniel Bienstock
    • Categories Global Optimization, Nonlinear Optimization Tags , , ,

    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

  • Enrico Bettiol
  • Christoph Buchheim
  • Marianna De Santis
  • Francesco Rinaldi
    • Categories Global Optimization, Robust Optimization Tags , ,

    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

    Global optimization using random embeddings

  • Coralia Cartis
  • Estelle Massart
  • Adilet Otemissov
    • Categories Global Optimization, Nonlinear Optimization Tags , , , ,

    We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high- dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate … Read more

    SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

  • Carlos Nohra
  • Arvind U. Raghunathan
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of … Read more