Month: May 2016

Intrinsic Representation of Tangent Vectors and Vector transport on Matrix Manifolds

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
  • Wen Huang
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    In Riemannian optimization problems, commonly encountered manifolds are $d$-dimensional matrix manifolds whose tangent spaces can be represented by $d$-dimensional linear subspaces of a $w$-dimensional Euclidean space, where $w > d$. Therefore, representing tangent vectors by $w$-dimensional vectors has been commonly used in practice. However, using $w$-dimensional vectors may be the most natural but may not … Read more

    Solving PhaseLift by low-rank Riemannian optimization methods for complex semidefinite constraints

  • Kyle A. Gallivan
  • Wen Huang
  • Xiangxiong Zhang
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming

    A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers … Read more

    Chebyshev Inequalities for Products of Random Variables

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Wolfram Wiesemann
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, … Read more

    Intersection Cuts for Single Row Corner Relaxations

  • Ricardo Fukasawa
  • Laurent Poirrier
  • Alinson S. Xavier
    • Categories Cutting Plane Approaches Tags ,

    We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer … Read more

    Virtuous smoothing for global optimization

  • Jon Lee
  • Daphne Skipper
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ($w^p$ with $0

    Disjunctive Programming for Multiobjective Discrete Optimisation

  • Tolga Bektas
    • Categories Integer Programming, Multi-Criteria Optimization

    In this paper, I view and present the multiobjective discrete optimisation problem as a particular case of disjunctive programming where one seeks to identify efficient solutions from within a disjunction formed by a set of systems. The proposed approach lends itself to a simple yet effective iterative algorithm that is able to yield the set … Read more

    Exact Algorithms for the Chance-Constrained Vehicle Routing Problem

  • Thai Dinh
  • Ricardo Fukasawa
  • James R. Luedtke
    • Categories 0-1 Programming, Stochastic Programming, Transportation Tags , ,

    We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for … Read more

    Numerically safe lower bounds for the Capacitated Vehicle Routing Problem

  • Ricardo Fukasawa
  • Laurent Poirrier
    • Categories 0-1 Programming Tags , ,

    The resolution of integer programming problems is typically performed via branch-and-bound. Nodes of the branch-and-bound tree are pruned whenever the corresponding subproblem is proven not to contain a solution better than the best solution found so far. This is a key ingredient for achieving reasonable solution times. However, since subproblems are solved in floating-point arithmetic, … Read more

    Matrices with high completely positive semidefinite rank

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Linear, Cone and Semidefinite Programming

    A real symmetric matrix M is completely positive semidefinite if it admits a Gram representation by positive semidefinite matrices (of any size d). The smallest such d is called the completely positive semidefinite rank of M, and it is an open question whether there exists an upper bound on this number as a function of … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more