A proximal quasi-Newton trust-region method for nonsmooth regularized optimization

DOI10.1137/21M1409536MaRDI QIDQ5081096zbMATH OpenOpenAlexFDO

Authors Aleksandr Y. Aravkin, Robert Baraldi, D. Orban

Publication date 1 June 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.15993

zbMATH Keywords

composite optimizationnonconvex optimizationnonsmooth optimizationproximal gradient methodproximal quasi-Newton methodquasi-Newton methodstrust-region methods

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Methods of quasi-Newton type (90C53) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: We develop a trust-region method for minimizing the sum of a smooth term $f$ and a nonsmooth term $h$), both of which can be nonconvex. Each iteration of our method minimizes a possibly nonconvex model of $f+h$ in a trust region. The model coincides with $f+h$ in value and subdifferential at the center. We establish global convergence to a first-order stationary point when $f$ satisfies a smoothness condition that holds, in particular, when it has Lipschitz-continuous gradient, and $h$ is proper and lower semi-continuous. The model of $h$ is required to be proper, lower-semi-continuous and prox-bounded. Under these weak assumptions, we establish a worst-case $O(1/epsilo{n}^2)$ iteration complexity bound that matches the best known complexity bound of standard trust-region methods for smooth optimization. We detail a special instance, named TR-PG, in which we use a limited-memory quasi-Newton model of $f$ and compute a step with the proximal gradient method, resulting in a practical proximal quasi-Newton method. We establish similar convergence properties and complexity bound for a quadratic regularization variant, named R2, and provide an interpretation as a proximal gradient method with adaptive step size for nonconvex problems. R2 may also be used to compute steps inside the trust-region method, resulting in an implementation named TR-R2. We describe our Julia implementations and report numerical results on inverse problems from sparse optimization and signal processing. Both TR-PG and TR-R2 exhibit promising performance and compare favorably with two linesearch proximal quasi-Newton methods based on convex models.

Recommendations

• A proximal trust-region method for nonsmooth optimization with inexact function and gradient evaluations
• A trust region method for nonsmooth convex optimization
• A new trust region method for nonsmooth nonconvex optimization
• Gradient trust region algorithm with limited memory BFGS update for nonsmooth convex minimization
• Optimality conditions and a smoothing trust region Newton method for nonlipschitz optimization

Cites work

• A New Algorithm for Unconstrained Optimization
• A trust region algorithm for minimization of locally Lipschitzian functions
• A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
• A trust region method for minimization of nonsmooth functions with linear constraints
• A unified approach to global convergence of trust region methods for nonsmooth optimization
• An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions
• Basis Pursuit Denoise With Nonsmooth Constraints
• Compressed sensing
• Computing a Trust Region Step
• Computing proximal points of nonconvex functions
• Concise complexity analyses for trust region methods
• Conditions for convergence of trust region algorithms for nonsmooth optimization
• Convex analysis and monotone operator theory in Hilbert spaces
• First-order methods in optimization
• Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms
• scientific article; zbMATH DE number 1089159 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• Iterative hard thresholding for compressed sensing
• Julia: a fresh approach to numerical computing
• Modified Gauss–Newton scheme with worst case guarantees for global performance
• Nearly unbiased variable selection under minimax concave penalty
• Nonlinear stepsize control algorithms: complexity bounds for first- and second-order optimality
• On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
• Probing the Pareto frontier for basis pursuit solutions
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Proximal Newton-type methods for minimizing composite functions
• Proximal splitting methods in signal processing
• Relax-and-split method for nonconvex inverse problems
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
• Trimmed statistical estimation via variance reduction
• Trust Region Methods
• Two new unconstrained optimization algorithms which use function and gradient values
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Variational Analysis

Cited in

(19)

• scientific article; zbMATH DE number 4162674 (Why is no real title available?)
• scientific article; zbMATH DE number 7306909 (Why is no real title available?)
• Newton acceleration on manifolds identified by proximal gradient methods
• Proximal gradient algorithm with trust region scheme on Riemannian manifold
• A proximal trust-region method for nonsmooth optimization with inexact function and gradient evaluations
• Local convergence analysis of an inexact trust-region method for nonsmooth optimization
• An inexact regularized proximal Newton method for nonconvex and nonsmooth optimization
• A Levenberg-Marquardt method for nonsmooth regularized least squares
• An adaptive regularized proximal Newton-type methods for composite optimization over the Stiefel manifold
• Safe zeroth-order optimization using quadratic local approximations
• Accelerated-gradient-based generalized Levenberg-Marquardt method with oracle complexity bound and local quadratic convergence
• A multi-precision quadratic regularization method for unconstrained optimization with rounding error analysis
• The indefinite proximal gradient method
• A proximal modified quasi-Newton method for nonsmooth regularized optimization
• Nonsmooth exact penalty methods for equality-constrained optimization: complexity and implementation
• Incremental Gauss-Newton methods with superlinear convergence rates
• A second-order descent method with active-set prediction for group-sparse optimization
• Title not available (Why is no real title available?)
• Projected quasi-Newton algorithm with trust region for constrained optimization

Describes a project that uses

Uses Software

• GQTPAR
• UNLocBoX
• SPGL1
• S+WAVELETS
• Julia
• ForwardDiff
• DifferentialEquations.jl
• NeuralPDE.jl

This page was built for publication: A proximal quasi-Newton trust-region method for nonsmooth regularized optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081096)