Global Optimization

An extension of the Reformulation-Linearization Technique to nonlinear optimization

  • Danique de Moor
  • Dick den Hertog
  • Jianzhe Zhen
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , ,

    We introduce a novel Reformulation-Perspectification Technique (RPT) to obtain convex approximations of nonconvex continuous optimization problems. RPT consists of two steps, those are, a reformulation step and a perspectification step. The reformulation step generates redundant nonconvex constraints from pairwise multiplication of the existing constraints. The perspectification step then convexifies the nonconvex components by using perspective … Read more

    SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

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

    We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of … Read more

    On obtaining the convex hull of quadratic inequalities via aggregations

  • Santanu S. Dey
  • Felipe Serrano
  • Gonzalo Muñoz
    • Categories Global Optimization Theory Tags , ,

    A classical approach for obtaining valid inequalities for a set involves weighted aggregations of the inequalities that describe such set. When the set is described by linear inequalities, thanks to the Farkas lemma, we know that every valid inequality can be obtained using aggregations. When the inequalities describing the set are two quadratics, Yildiran showed … Read more

    MatQapNB User Guide: A branch-and-bound program for QAPs in Matlab with the Newton-Bracketing method

  • Koichi Fujii
  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Kim-Chuan Toh
  • Yuji Shinano
    • Categories Global Optimization Applications, Optimization Software Design Principles, Quadratic Programming Tags , , ,

    MatQapNB is a MATLAB toolbox that implements a parallel branch-and-bound method using NewtBracket (the Newton bracketing method [4]) for its lower bounding procedure. It can solve small to medium scale Quadratic Assignment Problem (QAP) instances with dimension up to 30. MatQapNB was used in the numerical experiments on QAPs in the recent article “Solving challenging … Read more

    Lifting convex inequalities for bipartite bilinear programs

  • Santanu S. Dey
  • Jean-Philippe P. Richard
  • Xiaoyi Gu
    • Categories Cutting Plane Approaches, Global Optimization Theory, Nonlinear Optimization Tags

    The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear constraint together with bounds, it is always possible to sequentially lift a seed inequality that is valid … Read more

    Maximal perimeter and maximal width of a convex small polygon

  • Christian Bingane
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ sides are unknown when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ with $s\ge 4$, and show that their perimeters and their widths are within … Read more

    Local Minimizers of the Crouzeix Ratio: A Nonsmooth Optimization Case Study

  • Michael L. Overton
    • Categories Global Optimization, Nonsmooth Optimization Tags , , ,

    Given a square matrix $A$ and a polynomial $p$, the Crouzeix ratio is the norm of the polynomial on the field of values of $A$ divided by the 2-norm of the matrix $p(A)$. Crouzeix’s conjecture states that the globally minimal value of the Crouzeix ratio is 0.5, regardless of the matrix order and polynomial degree, … Read more

    Tight bounds on the maximal perimeter of convex equilateral small polygons

  • Christian Bingane
  • Charles Audet
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , ,

    A small polygon is a polygon of unit diameter. The maximal perimeter of a convex equilateral small polygon with $n=2^s$ vertices is not known when $s \ge 4$. In this paper, we construct a family of convex equilateral small $n$-gons, $n=2^s$ and $s \ge 4$, and show that their perimeters are within $\pi^4/n^4 + O(1/n^5)$ … Read more

    A new perspective on low-rank optimization

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable convex relaxations. We invoke the matrix perspective function — the matrix analog of the perspective function — and characterize explicitly … Read more

    Radial Duality Part I: Foundations

  • Benjamin Grimmer
    • Categories Global Optimization Theory, Nonlinear Optimization

    (Renegar, 2016) introduced a novel approach to transforming generic conic optimization problems into unconstrained, uniformly Lipschitz continuous minimization. We introduce radial transformations generalizing these ideas, equipped with an entirely new motivation and development that avoids any reliance on convex cones or functions. Perhaps of greatest practical importance, this facilitates the development of new families of … Read more