XXIV Congresso da Associação Portuguesa de Investigação Operacional (IO2025)

A Novel Derivative-Free Method with Improved Complexity for Nonsmooth Convex and Strongly Convex Optimization

Not scheduled

15m

Room 3

Apresentação regular Session 5.3 - Hard optimization problems

Speaker

Rohollah Garmanjani (NOVA Math, NOVA FCT, NOVA University Lisbon)

Description

Derivative-free methods—also known as black-box or zero-order methods—are crucial when derivative information is unavailable or unreliable. We introduce a novel algorithm that, for nonsmooth convex objectives, achieves a worst-case complexity bound proportional to the inverse square of a specified accuracy tolerance—substantially improving over a previously developed method in the literature. For nonsmooth strongly convex objectives, our method further improves to a complexity bound that grows only logarithmically with the inverse of the accuracy tolerance. Importantly, in the general nonsmooth nonconvex setting, our algorithm matches the complexity bound of a closely related existing method.