Georgina Hall

DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure … Read more

    Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Approximation Algorithms, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    We devise a scheme for solving an iterative sequence of linear programs (LPs) or second order cone programs (SOCPs) to approximate the optimal value of any semidefinite program (SDP) or sum of squares (SOS) program. The first LP and SOCP-based bounds in the sequence come from the recent work of Ahmadi and Majumdar on diagonally … Read more