Global Optimization Theory

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

    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

    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

    Proximity in Concave Integer Quadratic Programming

  • Alberto Del Pia
  • Mingchen Ma
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming

    A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n∆ on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, n is the number of variables and ∆ denotes the maximum of the absolute values of the subdeterminants of the … Read more

    Convex Hull Representations for Bounded Products of Variables

  • Kurt M. Anstreicher
  • Samuel Burer
  • Kyungchan Park
    • Categories Convex Optimization, Global Optimization Theory, Second-Order Cone Programming Tags , , ,

    It is well known that the convex hull of {(x,y,xy)}, where (x,y) is constrained to lie in a box, is given by the Reformulation-Linearization Technique (RLT) constraints. Belotti et al. (2010) and Miller et al. (2011) showed that if there are additional upper and/or lower bounds on the product z=xy, then the convex hull can … Read more

    A numerical study of transformed mixed-integer optimal control problems

  • Sebastian Sager
  • Manuel Tetschke
  • Clemens Zeile
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Systems governed by Differential Equations Optimization Tags , , , ,

    Time transformation is a ubiquitous tool in theoretical sciences, especially in physics. It can also be used to transform switched optimal con trol problems into control problems with a fixed switching order and purely continuous decisions. This approach is known either as enhanced time transformation, time-scaling, or switching time optimization (STO) for mixed-integer optimal control. … Read more

    Testing Copositivity via Mixed-Integer Linear Programming

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory Tags , ,

    We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. Citation Dept. of Business … Read more