Computing proximal points of convex functions with inexact subgradients
From MaRDI portal
Publication:2413568
DOI10.1007/S11228-016-0394-3zbMath1401.49039arXiv1611.00724OpenAlexW2546659876MaRDI QIDQ2413568
Publication date: 14 September 2018
Published in: Set-Valued and Variational Analysis (Search for Journal in Brave)
Abstract: Locating proximal points is a component of numerous minimization algorithms. This work focuses on developing a method to find the proximal point of a convex function at a point, given an inexact oracle. Our method assumes that exact function values are at hand, but exact subgradients are either not available or not useful. We use approximate subgradients to build a model of the objective function, and prove that the method converges to the true prox-point within acceptable tolerance. The subgradient $g_k$ used at each step $k$ is such that the distance from $g_k$ to the true subdifferential of the objective function at the current iteration point is bounded by some fixed $varepsilon>0.$ The algorithm includes a novel tilt-correct step applied to the approximate subgradient.
Full work available at URL: https://arxiv.org/abs/1611.00724
Derivative-free methods and methods using generalized derivatives (90C56) Numerical optimization and variational techniques (65K10) Quadratic programming (90C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An inexact accelerated proximal gradient method and a dual Newton-CG method for the maximal entropy problem
- Composite proximal bundle method
- A derivative-free approximate gradient sampling algorithm for finite minimax problems
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Finite convergence of algorithms for nonlinear programs and variational inequalities
- A proximal bundle method with inexact data for convex nondifferentiable minimization
- Proximity control in bundle methods for convex nondifferentiable minimization
- Discrete gradient method: Derivative-free method for nonsmooth optimization
- Computing proximal points of nonconvex functions
- A bundle-filter method for nonsmooth convex constrained optimization
- Finite termination of the proximal point algorithm
- Convergence of some algorithms for convex minimization
- Variable metric bundle methods: From conceptual to implementable forms
- An approximate redistributed proximal bundle method with inexact data for minimizing nonsmooth nonconvex functions
- Approximations in proximal bundle methods and decomposition of convex programs
- A \(\mathcal{VU}\)-algorithm for convex minimization
- Proximal Splitting Methods in Signal Processing
- A Nonderivative Version of the Gradient Sampling Algorithm for Nonsmooth Nonconvex Optimization
- A Redistributed Proximal Bundle Method for Nonconvex Optimization
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Introduction to Derivative-Free Optimization
- Monotone Operators and the Proximal Point Algorithm
- Variational Analysis
- DYNAMICAL ADJUSTMENT OF THE PROX-PARAMETER IN BUNDLE METHODS
- Numerical Analysis of $\mathcal{V}\mathcal{U}$-Decomposition, $\mathcal{U}$-Gradient, and $\mathcal{U}$-Hessian Approximations
- A Globally and Superlinearly Convergent Algorithm for Convex Quadratic Programs with Simple Bbounds
- A Bundle Method for a Class of Bilevel Nonsmooth Convex Minimization Problems
- Proximité et dualité dans un espace hilbertien
- Convex analysis and monotone operator theory in Hilbert spaces
- Numerical optimization. Theoretical and practical aspects. Transl. from the French
- A proximal bundle method based on approximate subgradients
- A proximal bundle method for nonsmooth nonconvex functions with inexact information
Related Items (7)
Unnamed Item ⋮ Alternating forward-backward splitting for linearly constrained optimization problems ⋮ A derivative-free 𝒱𝒰-algorithm for convex finite-max problems ⋮ Conditions for the existence, identification and calculus rules of the threshold of prox-boundedness ⋮ The chain rule for VU-decompositions of nonsmooth functions ⋮ Linear convergence of the derivative-free proximal bundle method on convex nonsmooth functions, with application to the derivative-free \(\mathcal{VU}\)-algorithm ⋮ Proximal decomposition of convex optimization via an alternating linearization algorithm with inexact oracles
Uses Software
This page was built for publication: Computing proximal points of convex functions with inexact subgradients
