performance estimation problem

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

    On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions

  • Etienne de Klerk
  • François Glineur
  • Adrien B. Taylor
    • Categories Convex Optimization Tags , , ,

    We consider the gradient (or steepest) descent method with exact line search applied to a strongly convex function with Lipschitz continuous gradient. We establish the exact worst-case rate of convergence of this scheme, and show that this worst-case behavior is exhibited by a certain convex quadratic function. We also extend the result to a noisy … Read more