sparsity

Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices

  • Samuel Burer
    • Categories Semi-definite Programming Tags , ,

    We build upon the work of Fukuda et al.\ \cite{FuKoMuNa01} and Nakata et al.\ \cite{NaFuFuKoMu01}, in which the theory of partial positive semidefinite matrices has been applied to the semidefinite programming (SDP) problem as a technique for exploiting sparsity in the data. In contrast to their work, which improves an existing algorithm that is based … Read more

    Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Second-Order Cone Programming, Semi-definite Programming Tags , , ,

    We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S.~Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of objective quadratic functions and diagonal coefficient matrices … Read more