Global Optimization

Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints

  • Hatim Djelassi
  • Alexander Mitsos
  • Moll Glass
    • Categories Global Optimization Applications, Global Optimization Theory, Semi-infinite Programming

    Discretization-based algorithms are proposed for the global solution of mixed-integer nonlinear generalized semi-infinite (GSIP) and bilevel (BLP) programs with lower-level equality constraints coupling the lower and upper level. The algorithms are extensions, respectively, of the algorithm proposed by Mitsos and Tsoukalas (J Glob Optim 61(1):1–17, 2015. https://doi.org/10.1007/s10898-014-0146-6) and by Mitsos (J Glob Optim 47(4):557–582, 2010. … Read more

    On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more

    MIQP-Based Algorithm for the Global Solution of Economic Dispatch Problems with Valve-Point Effects

  • Pierre-Antoine Absil
  • Benoît Sluysmans
  • Nicolas Stevens
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    Even in a static setting, the economic load dispatch problem (ELDP)—namely the cost-optimal distribution of power among generating units to meet a specific demand subject to system constraints—turns out to be a challenge owing to the consideration of valve-point effects (VPE), which make the cost function nonsmooth and nonconvex. We present a new method, termed … Read more

    Strong Convex Nonlinear Relaxations of the Pooling Problem

  • Claudia D'Ambrosio
  • Jeff Linderoth
  • James R. Luedtke
  • Jonas Schweiger
    • Categories Chemical Engineering, Cutting Plane Approaches, Global Optimization Tags , ,

    We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by … Read more

    A Branch-and-Bound based Algorithm for Nonconvex Multiobjective Optimization

  • Gabriele Eichfelder
  • Julia Niebling
    • Categories Global Optimization, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    A new branch-and-bound based algorithm for smooth nonconvex multiobjective optimization problems with convex constraints is presented. The algorithm computes an $(\varepsilon,\delta)$-approximation of all globally optimal solutions. We introduce the algorithm which uses selection rules, discarding and termination tests. The discarding tests are the most important aspect, as they examine in different ways whether a box … Read more

    An algorithm for computing Frechet means on the sphere

  • Gabriele Eichfelder
  • Thomas Hotz
  • Johannes Wieditz
    • Categories Global Optimization, Statistics Tags , ,

    For most optimisation methods an essential assumption is the vector space structure of the feasible set. This condition is not fulfilled if we consider optimisation problems over the sphere. We present an algorithm for solving a special global problem over the sphere, namely the determination of Frechet means, which are points minimising the mean distance … Read more

    Global Optimization of Multilevel Electricity Market Models Including Network Design and Graph Partitioning

  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

    We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in [25] that does not include a network design problem. The two classical discrete optimization … Read more

    Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs

  • Samuel Burer
  • Yinyu Ye
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , ,

    We study a class of quadratically constrained quadratic programs (QCQPs), called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$ for $j \ne k$, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature … Read more

    Extended formulations for convex hulls of some bilinear functions

  • Akshay Gupte
  • Thomas Kalinowski
  • Fabian Rigterink
  • Hamish Waterer
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , ,

    We consider the problem of characterizing the convex hull of the graph of a bilinear function $f$ on the $n$-dimensional unit cube $[0,1]^n$. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose the systematic study of properties of $f$ … Read more

    Deterministic Global Optimization with Artificial Neural Networks Embedded

  • Alexander Mitsos
  • Artur M Schweidtmann
    • Categories Chemical Engineering, Global Optimization, Nonlinear Optimization Tags , , , , , , ,

    Artificial neural networks (ANNs) are used in various applications for data-driven black-box modeling and subsequent optimization. Herein, we present an efficient method for deterministic global optimization of ANN embedded optimization problems. The proposed method is based on relaxations of algorithms using McCormick relaxations in a reduced-space [\textit{SIOPT}, 20 (2009), pp. 573-601] including the convex and … Read more