  We present the Trust Region Adversarial Functional Subdifferential (TRAFS)
algorithm for constrained optimization of nonsmooth convex Lipschitz functions.
Unlike previous methods that assume a subgradient oracle model, we work with
the functional subdifferential defined as a set of subgradients that
simultaneously captures sufficient local information for effective minimization
while being easy to compute for a wide range of functions. In each iteration,
TRAFS finds the best step vector in an $\ell_2$-bounded trust region by
considering the worst bound given by the functional subdifferential. TRAFS
finds an approximate solution with an absolute error up to $\epsilon$ in
$\mathcal{O}\left( \epsilon^{-1}\right)$ or $\mathcal{O}\left(\epsilon^{-0.5}
\right)$ iterations depending on whether the objective function is strongly
convex, compared to the previously best-known bounds of
$\mathcal{O}\left(\epsilon^{-2}\right)$ and
$\mathcal{O}\left(\epsilon^{-1}\right)$ in these settings. TRAFS makes faster
progress if the functional subdifferential satisfies a locally quadratic
property; as a corollary, TRAFS achieves linear convergence (i.e.,
$\mathcal{O}\left(\log \epsilon^{-1}\right)$) for strongly convex smooth
functions. In the numerical experiments, TRAFS is on average 39.1x faster and
solves twice as many problems compared to the second-best method.
