Semi-definite Programming

SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

  • Luigi Grippo
  • Veronica Piccialli
  • Laura Palagi
  • Mauro Piacentini
  • Giovanni Rinaldi
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

    We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more

    Portfolio Selection under Model Uncertainty: A Penalized Moment-Based Optimization Approach

  • Roy H. Kwon
  • Jonathan Y. Li
    • Categories Finance and Economics, Robust Optimization, Semi-definite Programming Tags ,

    We present a new approach for portfolio selection when the underlying distribution of asset returns is uncertain or ambiguous to investors. In particular, we consider the case that an investor can formulate some reference financial models based on his/her prior beliefs or information, but is concerned about misspecification of the reference models and the associated … Read more

    Comparing SOS and SDP relaxations of sensor network localization

  • João Gouveia
  • Ting Kei Pong
    • Categories Semi-definite Programming Tags , , ,

    We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye’s SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie’s sparse-SOS relaxation is stronger than the edge-based … Read more

    Burer’s Key Assumption for Semidefinite and Doubly Nonnegative Relaxations

  • Florian Jarre
    • Categories Approximation Algorithms, Quadratic Programming, Semi-definite Programming Tags , ,

    Burer has shown that completely positive relaxations of nonconvex quadratic programs with nonnegative and binary variables are exact when the binary variables satisfy a so-called key assumption. Here we show that introducing binary variables to obtain an equivalent problem that satisfies the key assumption will not improve the semidefinite relaxation, and only marginally improve the … Read more

    Parallel solver for semidefinite programming problem having sparse Schur complement matrix

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

    SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed … Read more

    Interior Point Methods for Computing Optimal Designs

  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , , , , ,

    In this paper we study interior point (IP) methods for solving optimal design problems. In particular, we propose a primal IP method for solving the problems with general convex optimality criteria and establish its global convergence. In addition, we reformulate the problems with A-, D- and E-criterion into linear or log-determinant semidefinite programs (SDPs) and … Read more

    On Doubly Positive Semidefinite Programming Relaxations

  • Dongdong Ge
  • Yinyu Ye
    • Categories Quadratic Programming, Semi-definite Programming Tags ,

    Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the … Read more

    The Approach of Moments for Polynomial Equations

  • Monique Laurent
  • Philipp Rostalski
    • Categories Semi-definite Programming Tags , , ,

    In this article we present the moment based approach for computing all real solutions of a given system of polynomial equations. This approach builds upon a lifting method for constructing semidefinite relaxations of several nonconvex optimization problems, using sums of squares of polynomials and the dual theory of moments. A crucial ingredient is a semidefinite … Read more

    Elementary optimality conditions for nonlinear SDPs

  • Florian Jarre
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags ,

    The goal of this paper is an easy and self-contained presentation of optimality conditions for nonlinear semidefinite programs concentrating on the differences between nonlinear semidefinite programs and nonlinear programs. Citation Technical Report, Department of Mathematics, Universit\”at D\”usseldorf. Article Download View Elementary optimality conditions for nonlinear SDPs

    On convex relaxations for quadratically constrained quadratic programming

  • Kurt M. Anstreicher
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let F denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on F is dominated by an alternative … Read more