Authors: Pierre Frankel Guillaume Garrigos Juan Peypouquet
Publish Date: 2014/09/16
Volume: 165, Issue: 3, Pages: 874-900
Abstract
We study the convergence of general descent methods applied to a lower semicontinuous and nonconvex function which satisfies the Kurdyka–Łojasiewicz inequality in a Hilbert space We prove that any precompact sequence converges to a critical point of the function and obtain new convergence rates both for the values and the iterates The analysis covers alternating versions of the forward–backward method with variable metric and relative errors As an example a nonsmooth and nonconvex version of the Levenberg–Marquardt algorithm is detailedThe authors thank H Attouch for useful remarks They would also like to thank the anonymous reviewer for his careful reading and constructive comments The second and third authors are partly supported by Conicyt Anillo Project ACT1106 ECOSConicyt Project C13E03 and Millenium Nucleus ICM/FIC P10024F The third author is also partly supported by FONDECYT Grant 1140829 and Basal Project CMM Universidad de ChileFor next results we introduce the following auxiliary property automatically fulfilled under the hypotheses of Theorems 31 and 32 which includes a stability of the sequence xk kin mathbb N with respect to the point x along with a sufficiently close initializationLet mathbf H 1 mathbf H 2 mathbf H 3 and mathbf Sxdelta rho hold Then xkin underlineGamma eta xrho for all k the sequence has finite length and converges to some overlinex Moreover liminf limits krightarrow infty Vert partial fxk Vert =0 and foverlinexle lim limits krightarrow infty fxk=fxCapture convergence and finite length follow from Lemma 72 and mathbf H 3 Next since b knotin ell 1 and sum k=1infty b k+1Vert partial fxk Vert le sum k=1infty Vert xk+1xkVert +sum k=1infty varepsilon k+1infty we obtain liminf krightarrow infty Vert partial fxk Vert =0 Finally observe that that lim krightarrow infty fxk exists because fxk is decreasing and bounded from below by fx and the lower semicontinuity of f implies foverlinexle lim krightarrow infty fxk If lim krightarrow infty fxk=beta fx the KŁ inequality and the fact that varphi is decreasing imply varphi beta fxVert partial fxk Vert ge varphi fxkfxVert partial fxk Vert ge 1 for all kin mathbb N which is impossible because liminf krightarrow infty Vert partial fxk Vert =0 whence beta = fx square Let xn krightarrow x with fxn krightarrow fx as krightarrow infty Since fxk is nonincreasing and admits a limit point we deduce that fxkdownarrow fx In particular we have fxle fxk for all kin mathbb N The function f satisfies the KŁ inequality on Gamma eta xdelta with desingularising function varphi Let K 0in mathbb N be sufficiently large so that fxKfxmin eta underlineadelta 2 and pick rho 0 such that fxKfxunderlineadelta rho 2Now we just need to check that the hypotheses mathbf H 3 are satisfied with our hypotheses on alpha k beta k and mu k Clearly mathbf H 3i holds since we have supposed that alpha k ge underlinealpha sigma fracsqrtpp +1 fracLrho Then mathbf H 3ii asks that b k notin ell 1 which is equivalent to frac1beta k +L notin ell 1 in our context This holds since we have supposed that frac1beta k notin ell 1 Hypothesis mathbf H 3iii is satisfied because fracbeta kalpha k+1 is supposed to be bounded Finally mathbf H 3iv asks the summability of fracbeta k mu kbeta k +L which is bounded by mu k in ell 1 square
Keywords: