ill-conditioning

Degeneracy in Maximal Clique Decomposition for Semidefinite Programs

  • Andrew Knyazev
  • Arvind U. Raghunathan
    • Categories Convex and Nonsmooth Optimization, Semi-definite Programming Tags , , , ,

    Exploiting sparsity in Semidefinite Programs (SDP) is critical to solving large-scale problems. The chordal completion based maximal clique decomposition is the preferred approach for exploiting sparsity in SDPs. In this paper, we show that the maximal clique-based SDP decomposition is primal degenerate when the SDP has a low rank solution. We also derive conditions under … Read more

    On the behavior of the conjugate-gradient method on ill-conditioned problems

  • Anders Forsgren
    • Categories Quadratic Programming, Unconstrained Optimization Tags , ,

    We study the behavior of the conjugate-gradient method for solving a set of linear equations, where the matrix is symmetric and positive definite with one set of eigenvalues that are large and the remaining are small. We characterize the behavior of the residuals associated with the large eigenvalues throughout the iterations, and also characterize the … Read more