Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions

Wei Peng (), Hui Zhang (), Xiaoya Zhang () and Lizhi Cheng ()
Additional contact information
Wei Peng: Chinese Academy of Military Science
Hui Zhang: National University of Defense Technology
Xiaoya Zhang: Chinese Academy of Military Science
Lizhi Cheng: National University of Defense Technology

Journal of Global Optimization, 2020, vol. 78, issue 1, No 4, 69-89

Abstract: Abstract Successive quadratic approximations (SQA) are numerically efficient for minimizing the sum of a smooth function and a convex function. The iteration complexity of inexact SQA methods has been analyzed recently. In this paper, we present an algorithmic framework of inexact SQA methods with four types of line searches, and analyze its global complexity under milder assumptions. First, we show its well-definedness and some decreasing properties. Second, under the quadratic growth condition and a uniform positive lower bound condition on stepsizes, we show that the function value sequence and the iterate sequence are linearly convergent. Moreover, we obtain a o(1/k) complexity without the quadratic growth condition, improving existing $${\mathcal {O}}(1/k)$$ O ( 1 / k ) complexity results. At last, we show that a local gradient-Lipschitz-continuity condition could guarantee a uniform positive lower bound for the stepsizes.

Keywords: Inexactness; Line search; Successive quadratic approximation; Quadratic growth condition; Linear convergence (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00892-1 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:jglopt:v:78:y:2020:i:1:d:10.1007_s10898-020-00892-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00892-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

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