Solver-o-matic
Decision Tree for Nonsmooth Optimization Software
Your first choice should be Limited Memory Bundle Method (LMBM). LMBM is specifically developed for large-scale nonsmooth optimization by N. Karmitsa. It works best for highly nonlinear functions. The Fortran 77 source code and the mex-driver (for MatLab users) are available.
Not satisfied?