global optimization

On tackling reverse convex constraints for non-overlapping of unequal circles

  • Chrysanthos E. Gounaris
  • Akang Wang
    • Categories Global Optimization, Global Optimization Applications Tags , , , , ,

    We study the unequal circle-circle non-overlapping constraints, a form of reverse convex constraints that often arise in optimization models for cutting and packing applications. The feasible region induced by the intersection of circle-circle non-overlapping constraints is highly non-convex, and standard approaches to construct convex relaxations for spatial branch-and-bound global optimization of such models typically yield … Read more

    On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming

  • Maxime Gasse
  • Ambros Gleixner
  • Andrea Lodi
  • Felipe Serrano
  • Benjamin Müller
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags ,

    The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens … Read more

    Visible points, the separation problem, and applications to MINLP

  • Felipe Serrano
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require … Read more

    A Method for Convex Black-Box Integer Global Optimization

  • Jeffrey Larson
  • Sven Leyffer
  • Prashant Palkar
  • Stefan M. Wild
    • Categories Convex Optimization Tags , , ,

    We study the problem of minimizing a convex function on the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective but, rather, uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings … Read more

    Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms

  • Ambros Gleixner
  • Felipe Serrano
  • Benjamin Müller
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , , ,

    One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over … Read more

    Escaping local minima with derivative-free methods: a numerical investigation

  • Coralia Cartis
  • Lindon Roberts
  • Oliver Sheridan-Methven
    • Categories Nonlinear Optimization Tags , ,

    We apply a state-of-the-art, local derivative-free solver, Py-BOBYQA, to global optimization problems, and propose an algorithmic improvement that is beneficial in this context. Our numerical findings are illustrated on a commonly-used test set of global optimization problems and associated noisy variants, and on hyperparameter tuning for a machine learning test set. As Py-BOBYQA is a … Read more

    On local non-global minimizers of quadratic optimization problem with a single quadratic constraint

  • Maziar Salahi
  • Akram Taati
    • Categories Global Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we consider the nonconvex quadratic optimization problem with a single quadratic constraint. First we give a theoretical characterization of the local non-global minimizers. Then we extend the recent characterization of the global minimizer via a generalized eigenvalue problem to the local non-global minimizers. Finally, we use these results to derive an efficient … Read more

    Global Solutions of Nonconvex Standard Quadratic Programs via Mixed Integer Linear Programming Reformulations

  • Jacek Gondzio
  • E. Alper Yildirim
    • Categories (Mixed) Integer Linear Programming, Quadratic Programming Tags , , ,

    A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative mixed integer linear programming formulations. Our first formulation is based on casting a standard quadratic program … Read more

    Efficient global unconstrained black box optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories Stochastic Approaches, Unconstrained Optimization Tags , , , ,

    For the unconstrained optimization of black box functions, this paper introduces a new randomized algorithm called VRBBO. In practice, VRBBO matches the quality of other state-of-the-art algorithms for finding, in small and large dimensions, a local minimizer with reasonable accuracy. Although our theory guarantees only local minimizers our heuristic techniques turn VRBBO into an efficient … Read more

    The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities

  • Martin Schmidt
  • Mathias Sirvent
  • Winnifried Wollner
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Global Optimization Tags , , ,

    It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit … Read more