Global Optimization Theory

Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Sean Lo
  • Jean Pauphilet
    • Categories Data-Mining, Global Optimization Theory, Semi-definite Programming

    Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye. We reformulate … Read more

    Nonexpansive Markov Operators and Random Function Iterations for Stochastic Fixed Point Problems

  • Russell Luke
    • Categories Global Optimization Theory, Stochastic Approaches, Stochastic Programming Tags , ,

    We study the convergence of random function iterations for finding an invariant measure of the corresponding Markov operator. We call the problem of finding such an invariant mea- sure the stochastic fixed point problem. This generalizes earlier work studying the stochastic feasibility problem, namely, to find points that are, with probability 1, fixed points of … Read more

    A Radial Basis Function Method for Noisy Global Optimisation

  • Dirk Banholzer
  • Jörg Fliege
  • Ralf Werner
    • Categories Global Optimization, Global Optimization Theory

    We present a novel response surface method for global optimisation of an expensive and noisy (black-box) objective function, where error bounds on the deviation of the observed noisy function values from their true counterparts are available. The method is based on the well-established RBF method by Gutmann (2001a,c) for minimising an expensive and deterministic objective … Read more

    A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints

  • Samuel Burer
    • Categories Cone Programming, Global Optimization Theory, Quadratic Programming

    \(\) Globally optimizing a nonconvex quadratic over the intersection of $m$ balls in $\mathbb{R}^n$ is known to be polynomial-time solvable for fixed $m$. Moreover, when $m=1$, the standard semidefinite relaxation is exact. When $m=2$, it has been shown recently that an exact relaxation can be constructed using a disjunctive semidefinite formulation based essentially on two … Read more

    Approximation hierarchies for copositive cone over symmetric cone and their comparison

  • Mitsuhiro Nishijima
  • Kazuhide Nakata
    • Categories Cone Programming, Convex Optimization, Global Optimization Theory Tags , , , ,

    We first provide an inner-approximation hierarchy described by a sum-of-squares (SOS) constraint for the copositive (COP) cone over a general symmetric cone. The hierarchy is a generalization of that proposed by Parrilo (2000) for the usual COP cone (over a nonnegative orthant). We also discuss its dual. Second, we characterize the COP cone over a … Read more

    Explicit convex hull description of bivariate quadratic sets with indicator variables

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Integer Programming Tags , , , , ,

    \(\) We consider the nonconvex set \(S_n = \{(x,X,z): X = x x^T, \; x (1-z) =0,\; x \geq 0,\; z \in \{0,1\}^n\}\), which is closely related to the feasible region of several difficult nonconvex optimization problems such as the best subset selection and constrained portfolio optimization. Utilizing ideas from convex analysis and disjunctive programming, … Read more

    Recursive McCormick Linearization of Multilinear Programs

  • Arvind U. Raghunathan
  • Carlos Cardonha
  • David Bergman
  • Carlos Nohra
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , ,

    Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more

    Generalizations of doubly nonnegative cones and their comparison

  • Mitsuhiro Nishijima
  • Kazuhide Nakata
    • Categories Convex Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , ,

    In this study, we examine the various extensions of the doubly nonnegative (DNN) cone, frequently used in completely positive programming (CPP) to achieve a tighter relaxation than the positive semidefinite cone. To provide tighter relaxation for generalized CPP (GCPP) than the positive semidefinite cone, inner-approximation hierarchies of the generalized copositive cone are exploited to obtain … Read more

    An SDP Relaxation for the Sparse Integer Least Square Problem

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    In this paper, we study the polynomial approximability or solvability of sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and introduce a randomized algorithm for SILS based on the SDP relaxation. In … Read more