A derivative-free $\mathcal{VU}$-algorithm for convex finite-max problems

Understand

The $\mathcal{VU}$-algorithm is a superlinearly convergent method for minimizing nonsmooth, convex functions.

• At each iteration, the algorithm works with a certain $\mathcal{V}$-space and its orthogonal $\U$-space, such that the nonsmoothness of the objective function is concentrated on its projection onto the $\mathcal{V}$-space, and on the $\mathcal{U}$-space the projection is smooth.
• This structure allows for an alternation between a Newton-like step where the function is smooth, and a proximal-point step that is used to find iterates with promising $\mathcal{VU}$-decompositions.
• We establish a derivative-free variant of the $\mathcal{VU}$-algorithm for convex finite-max objective functions.