# Convex optimization with full subdifferential information

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.

• If you have the full subdifferential and can extract a subgradient of minimal norm, you have a descent direction which can therefore be used in place of the usual gradient in first-order methods. You could also take a look at Lewis' and Overton's works on nonsmooth quasi-Newton methods. – Christian Clason Jun 27 '15 at 9:09
• @ChristianClason, that sure looks like an answer to me! – Tom Solberg Jun 27 '15 at 18:44

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.