Back to Search
Start Over
INEXACT HIGH-ORDER PROXIMAL-POINT METHODS WITH AUXILIARY SEARCH PROCEDURE.
- Source :
-
SIAM Journal on Optimization . 2021, Vol. 31 Issue 4, p2807-2828. 22p. - Publication Year :
- 2021
-
Abstract
- In this paper, we complement the framework of bilevel unconstrained minimization (BLUM) [Y. Nesterov, Math. Program., to appear] by a new pth-order proximal-point method convergent as O(k-(3p+1)/2), where k is the iteration counter. As compared with [Y. Nesterov, Math. Program., to appear], we replace the auxiliary line search by a segment search. This allows us to bound its complexity by a logarithm of the desired accuracy. Each step in this search needs an approximate computation of a high-order proximal-point operator. Under the assumption on boundedness of (p+1)th derivative of the objective function, this can be done by one step of the pthorder augmented tensor method. In this way, for p = 2, we get a new second-order method with the rate of convergence O(k-7/2) and logarithmic complexity of the auxiliary search at each iteration. Another possibility is to compute the proximal-point operator by lower-order minimization methods. As an example, for p = 3, we consider the upper-level process convergent as O(k-5). Assuming the boundedness of fourth derivative, an appropriate approximation of the proximal-point operator can be computed by a second-order method in logarithmic number of iterations. This combination gives a second-order scheme with much better complexity than the existing theoretical limits. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LOGARITHMS
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 31
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 154526509
- Full Text :
- https://doi.org/10.1137/20M134705X