Global Optimization Theory

Branch-and-Lift Algorithm for Deterministic Global Optimization in Nonlinear Optimal Control

  • Benoit Chachuat
  • Boris Houska
    • Categories Global Optimization Theory, Systems governed by Differential Equations Optimization

    This paper presents a branch-and-lift algorithm for solving optimal control problems with smooth nonlinear dynamics and nonconvex objective and constraint functionals to guaranteed global optimality. This algorithm features a direct sequential method and builds upon a spatial branch-and-bound algorithm. A new operation, called lifting, is introduced which refines the control parameterization via a Gram-Schmidt orthogonalization … Read more

    On valid inequalities for quadratic programming with continuous variables and binary indicators

  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming Tags ,

    In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more

    Multi-Variate McCormick Relaxations

  • Alexander Mitsos
  • Angelos Tsoukalas
    • Categories Global Optimization Theory Tags , , , , , ,

    G. P. McCormick [Math Prog 1976] provides the framework for convex/concave relaxations of factorable functions, via rules for the product of functions and compositions of the form F(f(z)), where F is a univariate function. Herein, the composition theorem is generalized to allow multivariate outer functions F, and theory for the propagation of subgradients is presented. … Read more

    Pessimistic Bi-Level Optimisation

  • Polyxeni-Margarita Kleniati
  • Berc Rustem
  • Angelos Tsoukalas
  • Wolfram Wiesemann
    • Categories Global Optimization Theory

    Bi-level problems are optimisation problems in which some of the decision variables must optimise a subordinate (lower-level) problem. In general, the lower-level problem can possess multiple optimal solutions. One therefore distinguishes between optimistic formulations, which assume that the most favourable lower-level solution is implemented, and pessimistic formulations, in which the most adverse lower-level solution is … Read more

    On feasibility based bounds tightening

  • Pietro Belotti
  • Sonia Cafieri
  • Jon Lee
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , ,

    Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each Branch-and-Bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (Feasibility-Based Bounds Tightening): an … Read more

    Proximal Methods with Bregman Distances to Solve VIP on Hadamard manifolds

  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Global Optimization, Global Optimization Theory Tags , , , ,

    We present an extension of the proximal point method with Bregman distances to solve Variational Inequality Problems (VIP) on Hadamard manifolds (simply connected finite dimensional Riemannian manifold with nonpositive sectional curvature). Under some natural assumption, as for example, the existence of solutions of the (VIP) and the monotonicity of the multivalued vector field, we prove … Read more

    A Complete Characterization of the Gap between Convexity and SOS-Convexity

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials via the definition of convexity, its first order characterization, and its second order characterization are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming … Read more

    An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Global Optimization Theory Tags , ,

    We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of nonlinear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme … Read more

    Representing quadratically constrained quadratic programs as generalized copositive programs

  • Samuel Burer
  • Hongbo Dong
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    We show that any nonconvex quadratically constrained quadratic program(QCQP) can be represented as a generalized copositive program. In fact,we provide two representations. The first is based on the concept of completely positive (CP) matrices over second order cones, while the second is based on CP matrices over the positive semidefinte cone. Our analysis assumes that … Read more

    Unharnessing the power of Schrijver’s permanental inequality

  • Leonid Gurvits
    • Categories Combinatorial Optimization, Global Optimization Theory Tags ,

    Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality \begin{equation} \label{le} per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n \end{equation} We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\ For all … Read more