Global Optimization

Optimization of Stochastic Problems with Probability Functions via Differential Evolution

  • Bayrammyrat Myradov
    • Categories Basic Sciences Applications, Stochastic Approaches, Stochastic Programming

    Chance constrained programming, quantile/Value-at-Risk (VaR) optimization and integral quantile / Conditional Value-at-Risk (CVaR) optimization problems as Stochastic Programming Problems with Probability Functions (SPP-PF) are one of the most widely studied optimization problems in recent years. As a rule real-life SPP-PF is nonsmooth nonconvex optimization problem with complex geometry of objective function. Moreover, often it cannot … Read more

    Global Optimisation of Multi-Plant Manganese Alloy Production

  • Henrik Andersson
  • Stein Wasbø
  • Martin Digernes
  • Brage Rugstad Knudsen
  • Lars Rudi
  • Magnus Stålhane
    • Categories Global Optimization Applications, Production and Logistics, Supply Chain Management

    This paper studies the problem of multi-plant manganese alloy production. The problem consists of finding the optimal furnace feed of ores, fluxes, coke, and slag that yields output products which meet customer specifications, and to optimally decide the volume, composition, and allocation of the slag. To solve the problem, a nonlinear pooling problem formulation is … Read more

    Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers

  • Yifan Chen
  • Wotao Yin
  • Yuejiao Sun
    • Categories Global Optimization Theory, Unconstrained Optimization Tags , , , ,

    Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an “inspect” phase to existing algorithms that helps escape from non-global stationary points. The inspection samples a set of points in a … Read more

    Computational Aspects of Bayesian Solution Estimators in Stochastic Optimization

  • Gérard Cornuéjols
  • Danial Davarnia
  • Burak Kocuk
    • Categories Statistics, Stochastic Approaches, Stochastic Programming Tags , , , ,

    We study a class of stochastic programs where some of the elements in the objective function are random, and their probability distribution has unknown parameters. The goal is to find a good estimate for the optimal solution of the stochastic program using data sampled from the distribution of the random elements. We investigate two common … Read more

    Tighter McCormick Relaxations through Subgradient Propagation

  • Alexander Mitsos
  • Jaromił Najman
    • Categories Global Optimization, Global Optimization Applications, Global Optimization Theory

    Tight convex and concave relaxations are of high importance in the field of deterministic global optimization. We present a heuristic to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation (Mitsos et al., SIAM J. Optim., 2009) to construct simple affine under- and overestimators of each factor of the original factorable … Read more

    BASBL: Branch-And-Sandwich BiLevel solver. II. Implementation and computational study with the BASBLib test set

  • Claire S. Adjiman
  • Polyxeni-Margarita Kleniati
  • Remigijus Paulavicius
    • Categories Global Optimization Applications, Optimization Software Benchmark Tags , , , , ,

    We describe BASBL, our implementation of the deterministic global optimization algorithm Branch-and-Sandwich for nonconvex/nonlinear bilevel problems, within the open-source MINOTAUR framework. The solver incorporates the original Branch-and-Sandwich algorithm and modifications proposed in the first part of this work. We also introduce BASBLib, an extensive online library of bilevel benchmark problems collected from the literature and … Read more

    BASBL: Branch-And-Sandwich BiLevel solver I. Theoretical advances and algorithmic improvements

  • Claire S. Adjiman
  • Remigijus Paulavicius
    • Categories Global Optimization Theory Tags , ,

    In this paper, we consider the global solution of bilevel programs involving nonconvex functions. We present algorithmic improvements and extensions to the recently proposed deterministic Branch-and-Sandwich algorithm (Kleniati and Adjiman, J. Glob. Opt. 60, 425–458, 2014), based on the theoretical results and heuristics. Choices in the way each step of the Branch-and-Sandwich algorithm is tackled, … Read more

    Global optimization of mixed-integer ODE constrained network problems using the example of stationary gas transport

  • Oliver Habeck
  • Marc E. Pfetsch
  • Stefan Ulbrich
    • Categories Global Optimization Tags , , ,

    In this paper we propose a new approach for finding global solutions of mixed-integer nonlinear optimization problems with ordinary differential equation constraints on networks. Instead of using a first discretize then optimize approach, we combine spatial and variable branching with appropriate discretizations of the differential equations to derive relaxations of the original problem. To construct … Read more

    Minotaur: A Mixed-Integer Nonlinear Optimization Toolkit

  • Sven Leyffer
  • Jeff Linderoth
  • James R. Luedtke
  • Ashutosh Mahajan
  • Todd S. Munson
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software and Modeling Systems Tags , ,

    We present a flexible framework for general mixed-integer nonlinear programming (MINLP), called Minotaur, that enables both algorithm exploration and structure exploitation without compromising computational efficiency. This paper documents the concepts and classes in our framework and shows that our implementations of standard MINLP techniques are efficient compared with other state-of-the-art solvers. We then describe structure-exploiting … Read more

    On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellens\”atze from the late 20th century (e.g., due to Stengle, Putinar, or Schm\”udgen) that certify positivity of a polynomial on an … Read more