Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality

References

• Absil P.-A., Mahony R., Andrews B. Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. (2005) 16(2):531–547Crossref, Google Scholar
• Absil P.-A., Mahony R., Sepulchre R.Optimization Algorithms on Matrix Manifolds (2008) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Attouch H., Bolte J. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programming Ser. B (2009) 116(1–2):5–16Crossref, Google Scholar
• Attouch H., Soubeyran A. Inertia and reactivity in decision making as cognitive variational inequalities. J. Convex Anal. (2006) 13(2):207–224Google Scholar
• Attouch H., Redont P., Soubeyran A. A new class of alternating proximal minimization algorithms with costs to move. SIAM J. Optim. (2007) 18(3):1061–1081Crossref, Google Scholar
• Attouch H., Bolte J., Redont P., Soubeyran A. Alternating proximal algorithms for weakly coupled convex minimization problems. Applications to dynamical games and PDE's. J. Convex Anal. (2008) 15(3):485–506Google Scholar
• Aubin J.-P., Ekeland I.Applied Nonlinear Analysis (1984) (John Wiley & Sons, New York) Google Scholar
• Auslender A.Optimisation, Méthodes Numériques (1976) (Masson, Paris) Google Scholar
• Bauschke H. H., Borwein J. M. On projection algorithms for solving convex feasibility problems. SIAM Rev. (1996) 38(3):367–426Crossref, Google Scholar
• Bauschke H. H., Combettes P. L., Noll D. Joint minimization with alternating Bregman proximity operators. Pacific J. Optim. (2006) 2(3):401–424Google Scholar
• Benedetti R., Risler J.-J.Real Algebraic and Semialgebraic Sets (1990) (Hermann, Éditeur des Sciences et des Arts, Paris) Google Scholar
• Bertsekas D.Nonlinear Optimisation (1999) 2nd ed.(Athena, Belmont, MA) Google Scholar
• Bochnak J., Coste M., Roy M.-F.Real Algebraic Geometry. Ergebrisse der Mathematik und ihser Grenzgebiete (1998) 36(Springer, Berlin) Crossref, Google Scholar
• Bolte J., Daniilidis A., Lewis A. The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. (2006) 17(4):1205–1223Crossref, Google Scholar
• Bolte J., Daniilidis A., Lewis A. A nonsmooth Morse-Sard theorem for subanalytic functions. J. Math. Anal. Appl. (2006) 321(2):729–740Crossref, Google Scholar
• Bolte J., Daniilidis A., Lewis A., Shiota M. Clarke subgradients of stratifiable functions. SIAM J. Optim. (2007) 18(2):556–572Crossref, Google Scholar
• Bolte J., Daniilidis A., Ley O., Mazet L. Characterizations of Łojasiewicz inequalities and applications: Subgradient flows, talweg, convexity. Trans. Amer. Math. Soc. (2010) 362:3319–3363Crossref, Google Scholar
• Bruckstein A., Donoho D., Elad M. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. (2009) 51(1):34–81Crossref, Google Scholar
• Byrne C., Censor Y. Proximity function minimization using multiple Bregman projections, with applications to split feasibility and Kullback-Leibler distance minimization. Ann. Oper. Res. (2001) 105(1–4):77–98Crossref, Google Scholar
• Candès E., Wakin M., Boyd S. Enhancing sparsity by reweighting ℓ1 minimization. J. Fourier Anal. Appl. (2008) 14(5):877–905Crossref, Google Scholar
• Combettes P. L. Signal recovery by best feasible approximation. IEEE Trans. Image Processing (1993) 2(2):269–271Crossref, Google Scholar
• Combettes P. L., Pennanen T. Proximal methods for cohypomonotone operators. SIAM J. Control Optim. (2004) 43(2):731–742Crossref, Google Scholar
• Combettes P. L., Wajs V. Signal recovery by proximal forward-backward splitting. Multiscale Model. Simulation (2005) 4(4):1168–1200Crossref, Google Scholar
• Csiszár I., Tusnády G. Information geometry and alternating minimization procedures. Statist. Decisions (1984) Suppl. 1):205–237Google Scholar
• Denkowska Z., Stasica J.Ensembles Sous-Analytiques à la Polonaise, Travaux en Cours (2008) 69(Hermann, Paris) Google Scholar
• Donoho D. L. Compressed sensing. IEEE Trans. Inform. Theory (2006) 4:1289–1306Crossref, Google Scholar
• Edelman A., Arias A., Smith S. T. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. (1999) 20(2):303–353Crossref, Google Scholar
• Hare W., Sagastizábal C. Computing proximal points of nonconvex functions. Math. Program. Ser. B (2009) 116(1–2):221–258Crossref, Google Scholar
• Gabrielov A. Complements of subanalytic sets and existential formulas for analytic functions. Inventiones Math. (1996) 125(1):1–12Crossref, Google Scholar
• Grubisić I., Pietersz R. Efficient rank reduction of correlation matrices. Linear Algebra Its Appl. (2007) 422(2–3):629–653Crossref, Google Scholar
• Ioffe A. D. Metric regularity and subdifferential calculus. (Russian) Uspekhi Mat. Nauk (2000) 55(3) (333):103–162[Translation in 2000. Russian Math. Surveys 55 501–558]Crossref, Google Scholar
• Iusem A. N., Pennanen T., Svaiter B. F. Inexact variants of the proximal point algorithm without monotonicity. SIAM J. Optim. (2003) 13(4):1080–1097Crossref, Google Scholar
• Kurdyka K. On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier (1998) 48(3):769–783Crossref, Google Scholar
• Lewis A. S., Malick J. Alternating projection on manifolds. Math. Oper. Res. (2008) 33(1):216–234Link, Google Scholar
• Lewis A. S., Luke D. R., Malick J. Local linear convergence for alternating and averaged nonconvex projections. Foundations Computational Math. (2009) 9(4):485–513Crossref, Google Scholar
• Lions P. L., Chan T. F., Glowinski R., Périaux J., Widlund O. On the Schwarz alternating method. III. A variant for nonoverlapping subdomains. Third Internat. Sympos. Domain Decomposition Methods for Partial Differential Equations (1990) (SIAM, Philadelphia) 202–231Google Scholar
• Łojasiewicz S. Une propriété topologique des sous-ensembles analytiques réels. Les Équations aux Dérivées Partielles (1963) (Éditions du centre National de la Recherche Scientifique, Paris) 87–89Google Scholar
• Łojasiewicz S. Sur la géométrie semi- et sous-analytique. Ann. Inst. Fourier (1993) 43:1575–1595Crossref, Google Scholar
• Luke D. R. Finding best approximation pairs relative to a convex and prox-regular set in a Hilbert space. SIAM J. Optim.19(2):714–739Crossref, Google Scholar
• Mordukhovich B. Variational analysis and generalized differentiation. I. basic theory. Grundlehren der Mathematischen Wissenschaften (2006) 330(Springer-Verlag, Berlin) Google Scholar
• Nesterov Yu. Introductory lectures on convex optimization. A basic course. Applied Optimization (2004) 87(Kluwer Academic Publishers, Boston) Google Scholar
• Rockafellar R. T., Wets R. Variational analysis. Grundlehren der Mathematischen Wissenschaften (1998) 317(Springer, Berlin) Google Scholar
• Shiota M. Geometry of subanalytic and semialgebraic sets. Progress in Mathematics (1997) 150(Birkhäuser, Boston) Google Scholar
• Tseng P. Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. (2001) 109(3):475–494Crossref, Google Scholar
• van den Dries L. Tame topology and o-minimal structures. London Mathematical Society (1998) 248(Cambridge University Press, Cambridge, UK) Lecture Note SeriesCrossref, Google Scholar
• von Neumann J. Functional operators. Annals of Mathematics Studies (1950) 22(Princeton University Press, Princeton, NJ) Google Scholar
• Widrow B., Wallach E.Adaptive Inverse Control (1996) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Wilkie A. J. Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. J. Amer. Math. Soc. (1996) 9(4):1051–1094Crossref, Google Scholar