30. A derivative-free trust-region method based on finite differences for composite nonsmooth optimization
Invited abstract in session FD-6: Difference and decomposition methods, stream Methods for non-/monotone inclusions and their applications.
Friday, 14:10 - 15:50Room: M:H
Authors (first author is the speaker)
| 1. | Dânâ Davar
|
| Applied Mathematics, UCLouvain | |
| 2. | Geovani Grapiglia
|
| Applied Mathematics, Université catholique de Louvain |
Abstract
We present a derivative-free trust-region method based on finite-difference gradient approximations for minimizing composite functions. The outer function is supposed to be convex and Lipschitz, possibly nonsmooth, while its argument is a vector blackbox function with Lipschitz continuous Jacobian. The proposed method approximates the Jacobian of the blackbox function by forward finite differences with stepsizes depending on an estimate of its Lipschitz constant. Such estimate is also used in the definition of the trust-region radius, allowing natural update rules to enforce sufficient decrease of the objective function. We establish a worst-case complexity bound for the number of function evaluations that the method needs to find an approximate stationary point. Notably, the obtained bound depends linearly on the problem dimension, and quadratically on the inverse of the desired accuracy. In addition, if the components of the blackbox function are convex and the outer function is monotone, the previous worst-case evaluation complexity is improved to a linear dependence on the inverse of the desired accuracy. Numerical results are also reported, showing the relative efficiency of the new method with respect to state-of-the-art derivative-free solvers for composite nonsmooth optimization.
Keywords
- Derivative-free optimization
- Complexity and efficiency of optimization algorithms
- Convex and non-smooth optimization
Status: accepted
Back to the list of papers