Skip to main content
placeholder image

Computing proximal points of convex functions with inexact subgradients

Journal Article


Download full-text (Open Access)

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 epsilon>0. The algorithm includes a novel tilt-correct step applied to the approximate subgradient.

Publication Date


  • 2016

Geographic Focus


Citation


  • Planiden, C. & Hare, W. (2016). Computing proximal points of convex functions with inexact subgradients. Set-Valued and Variational Analysis: an international journal devoted to the theory of multifunctions, Online First 1-24.

Scopus Eid


  • 2-s2.0-85051296385

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=2114&context=eispapers1

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers1/1112/

Number Of Pages


  • 23

Start Page


  • 1

End Page


  • 24

Volume


  • Online First

Place Of Publication


  • Netherlands

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 epsilon>0. The algorithm includes a novel tilt-correct step applied to the approximate subgradient.

Publication Date


  • 2016

Geographic Focus


Citation


  • Planiden, C. & Hare, W. (2016). Computing proximal points of convex functions with inexact subgradients. Set-Valued and Variational Analysis: an international journal devoted to the theory of multifunctions, Online First 1-24.

Scopus Eid


  • 2-s2.0-85051296385

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=2114&context=eispapers1

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers1/1112/

Number Of Pages


  • 23

Start Page


  • 1

End Page


  • 24

Volume


  • Online First

Place Of Publication


  • Netherlands