Goldstein – Optimization Online

Goldstein Stationarity in Lipschitz Constrained Optimization

Published: 2023/10/05, Updated: 2023/10/12

Constrained Nonlinear Optimization, Nonlinear Optimization constraint qualifications, convergence rate, Goldstein, nonconvex nonsmooth optimization, subgradient method

We prove the first convergence guarantees for a subgradient method minimizing a generic Lipschitz function over generic Lipschitz inequality constraints. No smoothness or convexity (or weak convexity) assumptions are made. Instead, we utilize a sequence of recent advances in Lipschitz unconstrained minimization, which showed convergence rates of $O(1/\delta\epsilon^3)$ towards reaching a “Goldstein” stationary point, that … Read more

A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth

Published: 2022/04/29, Updated: 2022/05/04

Damek Davis

Liwei Jiang

Convex and Nonsmooth Optimization active manifold, decomposable, Goldstein, Kurdyka-Lojasiewicz, max-of-smooth, nonsmooth, parameter-free, quadratic growth, semialgebraic, subgradient method

Classical results show that gradient descent converges linearly to minimizers of smooth strongly convex functions. A natural question is whether there exists a locally nearly linearly convergent method for nonsmooth functions with quadratic growth. This work designs such a method for a wide class of nonsmooth and nonconvex locally Lipschitz functions, including max-of-smooth, Shapiro’s decomposable … Read more