Global Optimization Theory

Compact Disjunctive Approximations to Nonconvex Quadratically Constrained Programs

  • Hongbo Dong
  • Yunqi Luo
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming

    Decades of advances in mixed-integer linear programming (MILP) and recent development in mixed-integer second-order-cone programming (MISOCP) have translated very mildly to progresses in global solving nonconvex mixed-integer quadratically constrained programs (MIQCP). In this paper we propose a new approach, namely Compact Disjunctive Approximation (CDA), to approximate nonconvex MIQCP to arbitrary precision by convex MIQCPs, which … Read more

    Deterministic upper bounds in global minimization with nonlinear equality constraints

  • Christian Füllner
  • Peter Kirst
  • Oliver Stein
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory

    We address the problem of deterministically determining upper bounds in continuous non-convex global minimization of box-constrained problems with equality constraints. These upper bounds are important for the termination of spatial branch-and-bound algorithms. Our method is based on the theorem of Miranda which helps to ensure the existence of feasible points in certain boxes. Then, the … Read more

    Understanding the Acceleration Phenomenon via High-Resolution Differential Equations

  • Simon Du
  • Michael I. Jordan
  • Bin Shi
  • Weijie Su
    • Categories Convex Optimization, Global Optimization Theory, Unconstrained Optimization Tags ,

    Gradient-based optimization algorithms can be studied from the perspective of limiting or- dinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distin- guish between two fundamentally different algorithms—Nesterov’s accelerated gradient method for strongly convex functions (NAG-SC) and Polyak’s heavy-ball method—we study an alter- native limiting process that yields high-resolution ODEs. We … Read more

    Subset selection in sparse matrices

  • Alberto Del Pia
  • Santanu S. Dey
  • Robert Weismantel
    • Categories Global Optimization Theory, Nonlinear Systems and Least-Squares Tags , , ,

    In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow … Read more

    On the impact of running intersection inequalities for globally solving polynomial optimization problems

  • Alberto Del Pia
  • Aida Khajavirad
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory

    We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of a set of binary points satisfying a number of multilinear equations. Running intersection inequalities are a family of facet-defining inequalities for the … Read more

    On decomposability of the multilinear polytope and its implications in mixed-integer nonlinear optimization

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization Theory Tags , , ,

    In this article, we provide an overview of some of our recent results on the facial structure of the multilinear polytope with a special focus on its decomposability properties. Namely, we demonstrate that, in the context of mixed-integer nonlinear optimization, the decomposability of the multilinear polytope plays a key role from both theoretical and algorithmic … Read more

    The running intersection relaxation of the multilinear polytope

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Global Optimization Theory, Polyhedra

    The multilinear polytope MP_G of a hypergraph G is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running-intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of MP_G referred to as the running-intersection relaxation and … Read more

    Subdeterminants and Concave Integer Quadratic Programming

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , , ,

    We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of … Read more

    New SOCP relaxation and branching rule for bipartite bilinear programs

  • Santanu S. Dey
  • Asteroide Santana
  • Yang Wang
    • Categories Global Optimization Applications, Global Optimization Theory

    A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than … Read more

    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