Range of the displacement operator of PDHG with applications to quadratic and conic programming

  • Tao Jiang
  • Walaa M. Moursi
  • Stephen A. Vavasis
    • Categories Generalized Convexity/Monoticity, Quadratic Programming, Second-Order Cone Programming Tags , , , , , Short URL: https://optimization-online.org/?p=24311

    Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed
    the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions. Their analysis
    hinges on the notion of the infimal displacement vector in the closure of the range of the displacement mapping of the splitting operator that encodes the PDHG algorithm. In this paper,
    we develop a novel formula for this range using monotone operator theory. The analysis is then specialized to conic programming and further to quadratic programming (QP) and second-ordercone programming (SOCP). A consequence of our analysis is that PDHG is able to diagnose infeasible or unbounded instances of QP and of the ellipsoid-separation problem, a subclass of SOCP

     

    Citation

    https://arxiv.org/abs/2309.15009

    Article

    Download

    View Range of the displacement operator of PDHG with applications to quadratic and conic programming