Ernest K. Ryu

Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods

  • Shuvomoy Das Gupta
  • Bart Paul Gerard Van Parys
  • Ernest K. Ryu
    • Categories Branch and Cut Algorithms, Nonlinear Optimization, Quadratic Programming Tags , ,

    We present the Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing optimal first-order methods for convex and nonconvex optimization. BnB-PEP poses the problem of finding the optimal optimization method as a nonconvex but practically tractable quadratically constrained quadratic optimization problem and solves it to certifiable global optimality using a customized branch-and-bound algorithm. By … Read more

    Uniqueness of DRS as the 2 Operator Resolvent-Splitting and Impossibility of 3 Operator Resolvent-Splitting

  • Ernest K. Ryu
    • Categories Convex Optimization

    Given the success of Douglas-Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there are other 2 operator splittings? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 … Read more

    Douglas-Rachford Splitting for Pathological Convex Optimization

  • Yanli Liu
  • Ernest K. Ryu
  • Wotao Yin
    • Categories Convex Optimization Tags , , , , , , ,

    Despite the vast literature on DRS, there has been very little work analyzing their behavior under pathologies. Most analyses assume a primal solution exists, a dual solution exists, and strong duality holds. When these assumptions are not met, i.e., under pathologies, the theory often breaks down and the empirical performance may degrade significantly. In this … Read more

    Proximal-Proximal-Gradient Method

  • Ernest K. Ryu
  • Wotao Yin
    • Categories Convex Optimization

    In this paper, we present the proximal-proximal-gradient method (PPG), a novel optimization method that is simple to implement and simple to parallelize. PPG generalizes the proximal-gradient method and ADMM and is applicable to minimization problems written as a sum of many differentiable and many non-differentiable convex functions. The non-differentiable functions can be coupled. We furthermore … Read more

    A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs

  • Yanli Liu
  • Ernest K. Ryu
  • Wotao Yin
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , ,

    In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or equivalently ADMM. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas-Rachford splitting diverge.Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly … Read more