Accelerating Level-Value Adjustment for the Polyak Stepsize

Anbang Liu (), Mikhail A. Bragin (), Xi Chen () and Xiaohong Guan ()
Additional contact information
Anbang Liu: Tsinghua University
Mikhail A. Bragin: University of Connecticut
Xi Chen: Tsinghua University
Xiaohong Guan: Tsinghua University

Journal of Optimization Theory and Applications, 2025, vol. 206, issue 3, No 15, 36 pages

Abstract: Abstract The Polyak stepsize has been widely used in subgradient methods for non-smooth convex optimization. However, calculating the stepsize requires the optimal value, which is generally unknown. Therefore, dynamic estimations of the optimal value are usually needed. In this paper, to guarantee convergence, a series of level values is constructed to estimate the optimal value successively. This is achieved by developing a decision-guided procedure that involves solving a novel, easy-to-solve linear constraint satisfaction problem referred to as the “Polyak Stepsize Violation Detector” (PSVD). Once a violation is detected, the level value is recalculated. We rigorously establish the convergence for both the level values and the objective function values. Furthermore, with our level adjustment approach, calculating an approximate subgradient in each iteration is sufficient for convergence. A series of empirical tests of convex optimization problems with diverse characteristics demonstrates the practical advantages of our approach over existing methods.

Keywords: Convex optimization; Non-smooth optimization; Polyak stepsize; Subgradient method; Approximate subgradient method; 90C25 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02750-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:206:y:2025:i:3:d:10.1007_s10957-025-02750-0

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02750-0

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().