Linear, Cone and Semidefinite Programming

Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization

  • Mohammadhossein Mohammadisiahroudi
  • Ramin Fakhimi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , ,

    Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have … Read more

    Exact SDP relaxations for quadratic programs with bipartite graph structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , ,

    For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. … 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

    Tight Probability Bounds with Pairwise Independence

  • Arjun Ramachandra
  • Karthik Natarajan
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Linear Programming Tags , , , , , , , ,

    \(\) While useful probability bounds for \(n\) pairwise independent Bernoulli random variables adding up to at least an integer \(k\) have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. Firstly, when \(k = 1\), the tightest upper bound on the … Read more

    Distributed Projections onto a Simplex

  • Yongzheng Dai
  • Chen Chen
    • Categories Linear, Cone and Semidefinite Programming, Parallel Algorithms Tags , , ,

    Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, all but one of these algorithms are serial. We address this gap by developing a method that preprocesses the input vector by decomposing and distributing it … Read more

    Riemannian Interior Point Methods for Constrained Optimization on Manifolds

  • Zhijian Lai
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    We extend the classical primal-dual interior point method from the Euclidean setting to the Riemannian one. Our method, named the Riemannian interior point method (RIPM), is for solving Riemannian  constrained optimization problems. We establish its local superlinear and quadratic convergence  under the standard assumptions. Moreover, we show its global convergence when it is combined with … Read more

    On the Sparsity of Optimal Linear Decision Rules in Robust Optimization

  • Haihao Lu
  • Bradley Sturt
    • Categories Linear Programming, Robust Optimization Tags , ,

    We consider the widely-studied class of production-inventory problems with box uncertainty sets from the seminal work of Ben-Tal et al. (2004) on linear decision rules in robust optimization. We prove that there always exists an optimal linear decision rule for this class of problems in which the number of nonzero parameters in the linear decision … 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

    Revisiting Degeneracy, Strict Feasibility, Stability, in Linear Programming

  • Haesol Im
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , , , , , ,

    Currently, the simplex method and the interior point method are indisputably the most popular algorithms for solving linear programs, LPs. Unlike general conic programs, LPs with a finite optimal value do not require strict feasibility in order to establish strong duality. Hence strict feasibility is seldom a concern, even though strict feasibility is equivalent to … Read more

    Discrete Optimal Transport with Independent Marginals is #P-Hard

  • Bahar Tașkesen
  • Soroosh Shafieezadeh-Abadeh
  • Daniel Kuhn
  • Karthik Natarajan
    • Categories Dynamic Programming, Linear Programming, Stochastic Programming

    We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector … Read more