Inexact High-Order Proximal-Point Methods with Auxiliary Search Procedure
(2021) SIAM Journal on Optimization — Vol. 31, n° 4, p. 2807-2828 (2021)
Files
CORE_RP_3251.pdf
Open Access - Adobe PDF
- 1.02 MB
Details
- Authors
- Abstract
- In this paper, we complement the framework of bilevel unconstrained minimization (BLUM) [Y. Nesterov, Math. Program., to appear] by a new th-order proximal-point method convergent as , where 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 th derivative of the objective function, this can be done by one step of the th-order augmented tensor method. In this way, for , we get a new second-order method with the rate of convergence 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 , we consider the upper-level process convergent as . 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.
- Affiliations
Citations
Nesterov, Y. (2021). Inexact High-Order Proximal-Point Methods with Auxiliary Search Procedure. SIAM Journal on Optimization, 31(4), 2807-2828. https://doi.org/10.1137/20M134705X (Original work published 2021)