Global Optimization

Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs

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

    We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. … Read more

    Constrained global optimization of functions with low effective dimensionality using multiple random embeddings

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

    We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms … Read more

    Global Dynamic Optimization with Hammerstein-Wiener Models Embedded

  • D. Bongartz
  • Alexander Mitsos
  • Jaromił Najman
  • C. D. Kappatou
  • S. Sass
    • Categories Global Optimization Theory Tags , , , ,

    Hammerstein-Wiener models constitute a significant class of block-structured dynamic models, as they approximate process nonlinearities on the basis of input-output data without requiring identification of a full nonlinear process model. Optimization problems with Hammerstein-Wiener models embedded are nonconvex, and thus local optimization methods may obtain suboptimal solutions. In this work, we develop a deterministic global … Read more

    Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more

    A Modified Simplex Partition Algorithm to Test Copositivity

  • Mohammadreza Safi
  • Seyed Saeed Nabavi
  • Richard J. Caron
    • Categories Global Optimization Theory Tags , , , ,

    A real symmetric matrix $A$ is copositive if $x^\top Ax\geq 0$ for all $x\geq 0$. As $A$ is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015) … Read more

    Connecting optimization with spectral analysis of tri-diagonal matrices

  • Jean-Bernard Lasserre
    • Categories Global Optimization, Global Optimization Theory, Nonlinear Optimization Tags

    We show that the global minimum (resp. maximum) of a continuous func- tion on a compact set can be approximated from above (resp. from below) by computing the smallest (rest. largest) eigenvalue of a hierarchy of (r × r) tri-diagonal matrices of increasing size. Equivalently it reduces to computing the smallest (resp. largest) root of … Read more

    Complexity Aspects of Fundamental Questions in Polynomial Optimization

  • Jeffrey Zhang
    • Categories Game Theory, Global Optimization Theory, Nonlinear Optimization Tags , , , ,

    In this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) testing local minimality of a candidate point, and (iii) deciding attainment of the optimal value. Our results characterize the complexity of these three questions for all degrees of the … Read more

    Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees

  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
    • Categories Applications - OR and Management Sciences, Global Optimization, Robust Optimization Tags , , , ,

    The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is … Read more

    Complexity Aspects of Local Minima and Related Notions

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

    We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if … Read more

    Branch-and-Bound Solves Random Binary IPs in Polytime

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
    • Categories 0-1 Programming, Branch and Cut Algorithms, Global Optimization Theory Tags ,

    Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v + 1 in the other node. Even though modern MILP solvers are … Read more