semidefinite programming

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

    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

    Distributionally Robust Joint Chance Constraints with Second-Order Moment Information

  • Daniel Kuhn
  • Berc Rustem
  • Steve Zymler
    • Categories Robust Optimization Tags , ,

    We develop tractable semidefinite programming (SDP) based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove … Read more

    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

    Semidefinite Relaxations of Ordering Problems

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Combinatorial Optimization Tags , , , , , , ,

    Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on … Read more

    Solving Infinite-dimensional Optimization Problems by Polynomial Approximation

  • Olivier Devolder
  • François Glineur
  • Yurii Nesterov
    • Categories Convex Optimization, Infinite Dimensional Optimization Tags , , , , , ,

    We solve a class of convex infinite-dimensional optimization problems using a numerical approximation method that does not rely on discretization. Instead, we restrict the decision variable to a sequence of finite-dimensional linear subspaces of the original infinite-dimensional space and solve the corresponding finite-dimensional problems in a efficient way using structured convex optimization techniques. We prove … Read more

    The state-of-the-art in conic optimization software

  • Hans D Mittelmann
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , ,

    This work gives an overview over the major codes available for the solution of linear semidefinite (SDP) and second-order cone (SOCP) programs. Some developments since the 7th DIMACS Challenge [9, 17] are pointed out as well as some currently under way. Instead of presenting per- formance tables, reference is made to the ongoing benchmark [19] … Read more

    On semidefinite programming relaxations of maximum k-section

  • Etienne de Klerk
  • Cristian Dobre
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is least as strong as the well-known bound by Frieze and Jerrum [A. Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1): 67-81, 1997]. For k > 2 … Read more

    Relaxations of combinatorial problems via association schemes

  • Etienne de Klerk
  • Fernando Mário de Oliveira Filho
  • Dmitrii V. Pasechnik
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    In this chapter we study a class of semidefinite programming relaxations of combinatorial problems. These relaxations are derived using the theory of coherent configurations in algebraic combinatorics. Citation Draft version of a chapter for “Handbook on SDP II” (M. Anjos and J. Lasserre, eds.), Springer. Article Download View Relaxations of combinatorial problems via association schemes