Global Optimization Theory

A Reformulation Technique to Solve Polynomial Optimization Problems with Separable Objective Functions of Bounded Integer Variables

  • Andrew C. Trapp
  • Pitchaya Wiratchotisatian
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Nonlinear Optimization Tags , , ,

    Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more

    Exactness in SDP relaxations of QCQPs: Theory and applications

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Semi-definite Programming

    Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in … 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

    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

    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

    Radial Duality Part II: Applications and Algorithms

  • Benjamin Grimmer
    • Categories Global Optimization Theory, Nonlinear Optimization, Nonsmooth Optimization

    The first part of this work established the foundations of a radial duality between nonnegative optimization problems, inspired by the work of (Renegar, 2016). Here we utilize our radial duality theory to design and analyze projection-free optimization algorithms that operate by solving a radially dual problem. In particular, we consider radial subgradient, smoothing, and accelerated … Read more

    Homogeneous polynomials and spurious local minima on the unit sphere

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

    We consider degree-d forms on the Euclidean unit sphere. We specialize to our setting a genericity result by Nie obtained in a more general framework. We exhibit an homogeneous polynomial Res in the coefficients of f, such that if Res(f) is not zero then all points that satisfy first- and second-order necessary optimality conditions are … Read more

    A Unifying Framework for Sparsity Constrained Optimization

  • Matteo Lapucci
  • Tommaso Levato
  • Francesco Rinaldi
  • Marco Sciandrone
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Statistics Tags , , , , ,

    In this paper, we consider the optimization problem of minimizing a continuously differentiable function subject to both convex constraints and sparsity constraints. By exploiting a mixed-integer reformulation from the literature, we define a necessary optimality condition based on a tailored neighborhood that allows to take into account potential changes of the support set. We then … Read more

    Limit sets in global multiobjective optimization

  • Gabriele Eichfelder
  • Oliver Stein
    • Categories Global Optimization Theory, Multi-Criteria Optimization Tags , , , , ,

    Inspired by the recently introduced branch-and-bound method for continuous multiobjective optimization problems from G. Eichfelder, P. Kirst, L. Meng, O. Stein, A general branch-and-bound framework for continuous global multiobjective optimization, Journal of Global Optimization, 80 (2021) 195-227, we study for a general class of branch-and-bound methods in which sense the generated terminal enclosure and the … Read more