AN-SPS: adaptive sample size nonmonotone line search spectral projected subgradient method for convex constrained optimization problems

Abstract

We consider convex optimization problems with a possibly nonsmooth objective function in the form of a mathematical expectation. The proposed framework (AN-SPS) employs Sample Average Approximations (SAA) to approximate the objective function, which is either unavailable or too costly to compute. The sample size is chosen in an adaptive manner, which eventually pushes the SAA error to zero almost surely (a.s.). The search direction is based on a scaled subgradient and a spectral coefficient, both related to the SAA function. The step size is obtained via a nonmonotone line search over a predefined interval, which yields a theoretically sound and practically efficient algorithm. The method retains feasibility by projecting the resulting points onto a feasible set. The a.s. convergence of AN-SPS method is proved without the assumption of a bounded feasible set or bounded iterates. Preliminary numerical results on Hinge loss problems reveal the advantages of the proposed adaptive scheme. In addition, a study of different nonmonotone line search strategies in combination with different spectral coefficients within AN-SPS framework is also conducted, yielding some hints for future work.

Keywords:

• Nonsmooth optimization
• spectral projected gradient
• sample average approximation
• adaptive variable sample size strategies
• nonmonotone line search

Acknowledgments

We are grateful to the associate editor and two anonymous referees whose comments helped us improve the paper.

Data availability statement

The datasets analysed during the current study are available in the MNIST database of handwritten digits [27], LIBSVM Data: Classification (Binary Class) [28] and UCI Machine Learning Repository [29].

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 This part of the proof uses the elements of the analysis in [21], but it also brings new steps and thus we provide it in a complete form.

Additional information

Funding

The work of Nataša Krklec Jerinkić has been supported by Provincial Secretariat for Higher Education and Scientific Research of Vojvodina, grant no. 142-451-2593/2021-01/2. The work of Tijana Ostojić has been supported by the Ministry of Science, Technological Development and Innovation (Contract No. 451-03-65/2024-03/200156) and the Faculty of Technical Sciences, University of Novi Sad through project “Scientific and Artistic Research Work of Researchers in Teaching and Associate Positions at the Faculty of Technical Sciences, University of Novi Sad” (No. 01-3394/1).

Notes on contributors

Nataša Krklec Jerinkić

Nataša Krklec Jerinkić was born in Novi Sad in 1984. She obtained a diploma in mathematics in September 2007 and the Ph.D. degree in Numerical mathematics in January 2014, both at the Faculty of Sciences, University of Novi Sad, where she works as an Associate Professor since 2019. Her scientific field is Numerical optimization and her research interests include stochastic and distributed optimization. She participates in several national and international (H2020) projects.

Tijana Ostojić

Tijana Ostojić was born in Sombor in 1991. She is a teaching assistant at the Department of Fundamental Sciences at the Faculty of Technical Sciences at the University of Novi Sad. She obtained her PhD in Numerical Mathematics in 2023 under the supervision of Prof. Dr Nataša Krklec Jerinkić at the Faculty of Sciences of the University of Novi Sad, where she completed her Bachelor's degree in 2012 and her Master's degree in Applied Mathematics in 2014. Her research interests include several subfields of nonlinear optimization, including stochastic and non-smooth optimization.