Linear, Cone and Semidefinite Programming

A T-algebraic approach to primal-dual interior-point algorithms

  • Chek Beng Chua
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming

    Three primal-dual interior-point algorithms for homogeneous cone programming are presented. They are a short-step algorithm, a large-update algorithm, and a predictor-corrector algorithm. These algorithms are described and analyzed based on a characterization of homogeneous cone via T-algebra. The analysis show that the algorithms have polynomial iteration complexity. Citation Division of Mathematical Sciences, Nanyang Technological University, … Read more

    Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms

  • Vasile L. Basescu
  • John E. Mitchell
    • Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , ,

    It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly … Read more

    A Unified Theorem on SDP Rank Reduction

  • Anthony Man-Cho So
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Semi-definite Programming Tags ,

    We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X … Read more

    A new adaptive algorithm for linear multiobjective programming problems

  • M.O. Bibi
  • M.S Radjef
  • Sonia Radjef
    • Categories Linear, Cone and Semidefinite Programming, Multi-Criteria Optimization Tags , , , , , ,

    In this paper, we present a new adaptive algorithm for defining the solution set of a multiobjective linear programming problem, where the decision variables are upper and lower bounded, using the direct support method. The principle particularitie of this method is the fact that it handles the bounds of variables such are they are initially … Read more

    A Data-Driven Approach to Newsvendor Problems

  • Dimitris Bertsimas
  • Aurelie Thiele
    • Categories Linear Programming, Production and Logistics Tags ,

    We propose an approach to the classical newsvendor problem and its extensions subject to uncertain demand that: (a) works directly with data, i.e., combines historical data and optimization in a single framework, (b) yields robust solutions and incorporates risk preferences using one scalar parameter, rather than utility functions, (c) allows for tractable formulations, specifically, linear … Read more

    A Filter Algorithm for Nonlinear Semidefinite Programming

  • Walter Gómez
  • Héctor Ramírez
    • Categories Nonlinear Optimization, Semi-definite Programming

    This paper proposes a filter method for solving nonlinear semidefinite programming problems. Our method extends to this setting the filter SQP (sequential quadratic programming) algorithm, recently introduced for solving nonlinear programming problems, obtaining their respective global convergence results. Citation CMM-B-06/10 – 171 Centre for Mathematical Modelling, UMR 2071, Universidad de Chile-CNRS. Casilla 170-3 Santiago 3, … Read more

    Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps

  • Christine Bachoc
  • Frank Vallentin
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we apply the semidefinite programming approach developed by the authors to obtain new upper bounds for codes in spherical caps. We compute new upper bounds for the one-sided kissing number in several dimensions where we in particular get a new tight bound in dimension 8. Furthermore we show how to use the … Read more

    A Matrix-lifting Semidefinite Relaxation for the Quadratic Assignment Problem

  • Yichuan Ding
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Semi-definite Programming Tags ,

    The quadratic assignment problem (\QAP) is arguably one of the hardest of the NP-hard discrete optimization problems. Problems of dimension greater than 20 are considered to be large scale. Current successful solution techniques depend on branch and bound methods. However, it is difficult to get \emph{strong and inexpensive} bounds. In this paper we introduce a … Read more

    Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem

  • Janez Povh
  • Franz Rendl
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it … Read more

    On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs

  • Samuel Burer
    • Categories Global Optimization, Integer Programming, Linear, Cone and Semidefinite Programming

    We establish that any nonconvex quadratic program having a mix of binary and continuous variables over a bounded feasible set can be represented as a linear program over the dual of the cone of copositive matrices. This result can be viewed as an extension of earlier separate results, which have established the copositive representation of … Read more