Linear Convergence of the Derivative-Free Proximal Bundle Method on Convex Nonsmooth Functions, with Application to the Derivative-Free VU-Algorithm
Publication Name
Set-Valued and Variational Analysis
Abstract
Proximal bundle methods are a class of optimisation algorithms that leverage the proximal operator to address nonsmoothness in the objective function efficiently. This study focuses on a derivative-free (DFO) proximal bundle method and one of its applications called the DFO VU-algorithm. These algorithms incorporate approximate proximal points as subprocedures in order to optimise convex nonsmooth functions based on approximated subdifferential information. Interestingly, the classical VU-algorithm, which operates on true subgradient values, achieves superlinear convergence. At each iteration, the algorithm divides the whole space into two: the smooth U-space and the nonsmooth V-space. It takes a Newton-like step on the U-space and a proximal-point step on the V-space, enabling it to handle both smooth and nonsmooth parts effectively and converge faster. In this work, we reveal the worst possible convergence rate for the DFO VU-method by showing the linear convergence of the DFO proximal bundle method. This will be done by presenting a suitable framework and using the subdifferential-based error bound on the distance to critical points.
Open Access Status
This publication may be available as open access
Volume
32
Issue
2
Article Number
15