This paper by Yu. Nesterov analyzes several new methods for solving optimization problems where the objective function is a sum of two terms: one is smooth and given by a black-box oracle, and the other is a simple, general convex function with known structure. Despite the lack of good properties in the sum, these problems can be solved efficiently, particularly for convex problems. The paper considers primal and dual variants of the gradient method with a convergence rate of \(O(\frac{1}{k})\), an accelerated multistep version with a rate of \(O(\frac{1}{k^2})\), and proves convergence to a point with no descent direction for nonconvex problems. It also highlights that for general nonsmooth, nonconvex problems, determining the existence of a descent direction from a point is NP-hard. Efficient "line search" procedures are suggested for all methods, and preliminary computational experiments confirm the superiority of the accelerated scheme. The paper is dedicated to Claude Lemaréchal on his 65th birthday and acknowledges support from the Office of Naval Research.This paper by Yu. Nesterov analyzes several new methods for solving optimization problems where the objective function is a sum of two terms: one is smooth and given by a black-box oracle, and the other is a simple, general convex function with known structure. Despite the lack of good properties in the sum, these problems can be solved efficiently, particularly for convex problems. The paper considers primal and dual variants of the gradient method with a convergence rate of \(O(\frac{1}{k})\), an accelerated multistep version with a rate of \(O(\frac{1}{k^2})\), and proves convergence to a point with no descent direction for nonconvex problems. It also highlights that for general nonsmooth, nonconvex problems, determining the existence of a descent direction from a point is NP-hard. Efficient "line search" procedures are suggested for all methods, and preliminary computational experiments confirm the superiority of the accelerated scheme. The paper is dedicated to Claude Lemaréchal on his 65th birthday and acknowledges support from the Office of Naval Research.