This chapter deals with the problem of minimizing a non-smooth convex function f over a “simple” feasible set \(X \subset \mathbb {R}^n\) . By “simple”, we mean that minimizing a linear or quadratic function over X can be efficiently performed by specialized algorithms. This is the case if X is a polyhedron, a ball, a semidefinite domain, or even, in some cases, a mixed-integer set. We start by laying the groundwork for the subsequent sections with some central concepts and definitions such as cutting-plane approximations and oracles (black-boxes). Next, we present implementable algorithms, such as Kelley’s cutting-plane method and a few enhanced versions of the latter. No further information on the objective function is necessary. For instance, f may only be assessed by a first-order oracle. This is a significant difference with the algorithms of Chap. 9 , which require full knowledge of f (e.g. its algebraic expression and thus potential “confidential” information).