Semi-definite Programming

NCSOSTOOLS: A COMPUTER ALGEBRA SYSTEM FOR SYMBOLIC AND NUMERICAL COMPUTATION WITH NONCOMMUTATIVE POLYNOMIALS

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , , ,

    Abstract. NCSOStools is a Matlab toolbox for – symbolic computation with polynomials in noncommuting variables; – constructing and solving sum of hermitian squares (with commutators) programs for polynomials in noncommuting variables. It can be used in combination with semidefi nite programming software, such as SeDuMi, SDPA or SDPT3 to solve these constructed programs. This paper provides … Read more

    Semidefinite code bounds based on quadruple distances

  • Dion C. Gijswijt
  • Hans D Mittelmann
  • Alexander Schrijver
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    Let A(n, d) be the maximum number of 0, 1 words of length n, any two having Hamming distance at least d. We prove A(20, 8) = 256, which implies that the quadruply shortened Golay code is optimal. Moreover, we show A(18, 6) ≤ 673, A(19, 6) ≤ 1237, A(20, 6) ≤ 2279, A(23, 6) … Read more

    Truss topology design with integer variables made easy

  • Michal Kočvara
    • Categories (Mixed) Integer Nonlinear Programming, Mechanical Engineering, Semi-definite Programming Tags , ,

    We propose a new look at the problem of truss topology optimization with integer or binary variables. We show that the problem can be equivalently formulated as an integer \emph{linear} semidefinite optimization problem. This makes its numerical solution much easier, compared to existing approaches. We demonstrate that one can use an off-the-shelf solver with default … Read more

    Convex approximations in stochastic programming by semidefinite programming

  • István Deák
  • Imre Pólik
  • Tamás Terlaky
  • András Prékopa
    • Categories Semi-definite Programming, Stochastic Programming Tags , , ,

    The following question arises in stochastic programming: how can one approximate a noisy convex function with a convex quadratic function that is optimal in some sense. Using several approaches for constructing convex approximations we present some optimization models yielding convex quadratic regressions that are optimal approximations in $L_1$, $L_\infty$ and $L_2$ norm. Extensive numerical experiments … Read more

    The tracial moment problem and trace-optimization of polynomials

  • Sabine Burgdorf
  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Global Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , , ,

    The main topic addressed in this paper is trace-optimization of polynomials in noncommuting (nc) variables: given an nc polynomial f, what is the smallest trace f(A) can attain for a tuple of matrices A? A relaxation using semidefinite programming (SDP) based on sums of hermitian squares and commutators is proposed. While this relaxation is not … Read more

    The matricial relaxation of a linear matrix inequality

  • J. William Helton
  • Igor Klep
  • Scott McCullough
    • Categories Semi-definite Programming Tags , , , , , ,

    Given linear matrix inequalities (LMIs) L_1 and L_2, it is natural to ask: (Q1) when does one dominate the other, that is, does L_1(X) PsD imply L_2(X) PsD? (Q2) when do they have the same solution set? Such questions can be NP-hard. This paper describes a natural relaxation of an LMI, based on substituting matrices … Read more

    An inexact interior point method for L1-regularized sparse covariance selection

  • Lu Li
  • Kim-Chuan Toh
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , , ,

    Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal-dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal-dual … Read more

    On Computation of Performance Bounds of Optimal Index Assignment

  • Hans D Mittelmann
  • Xiaolin Wu
  • J. Wang
  • X. Wang
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , , ,

    Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a … Read more

    On the complexity of computing the handicap of a sufficient matrix

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
    • Categories Complementarity and Variational Inequalities, Semi-definite Programming Tags , ,

    The class of sufficient matrices is important in the study of the linear complementarity problem(LCP) – some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap. In this paper we show that the handicap of a sufficient matrix may be exponential … Read more

    A high-performance software package for semidefinite programs: SDPA 7

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
  • Kazushige Goto
  • Kazuhiro Kobayashi
  • Maho Nakata
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , ,

    The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely … Read more