Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? All of the results that I can find are designed for the case where one has an oracle that can generate a single subgradient.



Convex optimization with full subdifferential information
The difficulty with non-differentiable convex functions in optimization stems from the fact that an arbitrary subgradient need not be a descent direction, and hence classical first-order methods cannot be guaranteed to work. (But see Lewis' and Overton's works on nonsmooth quasi-Newton methods, e.g., <http://people.orie.cornell.edu/aslewis/publications/13-nonsmooth.pdf>, where an appropriate line-search strategy is used to mitigate that difficulty.)


If you have access to the full subdifferential, you could try to compute (analytically or algorithmically) a minimum-norm subgradient
$$ p^k = \arg\min\_{\xi\in\partial f(x^k)}\|\xi\|,$$
which *is* a descent direction (and can be used to measure stationarity) and can be used in place of the standard gradient in any algorithm built on descent directions (e.g., gradient descent with Armijo line search). A proof (and a counterexample for arbitrary subgradients) can be found in Andrzej Ruszczyński's book *Nonlinear Optimization*.


A related approach is to compute (again, analytically or algorithmically) instead *proximal points*
$$ \mathrm{prox\_f(v)} = \arg\min\_{w} \frac12 \|v-w\|^2 + f(w) = (\mathrm{Id} + \partial f)^{-1}(v)$$
which can be used directly in place of gradient steps when applied to a suitable $v^k$ (think implicit vs. explicit Euler method for ODEs). Most current first-order methods for convex optimization are based on this approach, such as Nesterov's optimal first-order method which uses a specially chosen sequence of step sizes. A good introduction to these methods can be found in [Lieven Vandenberghe's lecture notes](http://www.seas.ucla.edu/~vandenbe/ee236c.html).


