Transversality and Alternating Projections for Nonconvex Sets

详细信息    查看全文

• 作者：D. Drusvyatskiy ; A. D. Ioffe ; A. S. Lewis
• 关键词：Alternating projections ; Linear convergence ; Variational analysis ; Slope ; Transversality ; 49M20 ; 65K10 ; 90C30
• 刊名：Foundations of Computational Mathematics
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：15
• 期：6
• 页码：1637-1651
• 全文大小：583 KB
• 参考文献：1. F. Andersson and M. Carlsson. Alternating projections on nontangential manifolds. Constructive Approximation, 38:489鈥?25, 2013.MATH MathSciNet CrossRef
  2. H. Attouch, J. Bolte, P. Redont, and A. Soubeyran. Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-艁ojasiewicz inequality. Mathematics of Operations Research, 35:438鈥?57, 2010.MATH MathSciNet CrossRef
  3. H.H. Bauschke and J.M. Borwein. On the convergence of von Neumann鈥檚 alternating projection algorithm for two sets. Set-Valued Analysis, 1:185鈥?12, 1993.MATH MathSciNet CrossRef
  4. H.H. Bauschke, D.R. Luke, H.M. Phan, and X. Wang. Restricted normal cones and the method of alternating projections: Applications. Set-Valued and Variational Analysis, 21:475鈥?01, 2013.MATH MathSciNet CrossRef
  5. H.H. Bauschke, D.R. Luke, H.M. Phan, and X. Wang. Restricted normal cones and the method of alternating projections: Theory. Set-Valued and Variational Analysis, 21:431鈥?73, 2013.MATH MathSciNet CrossRef
  6. J. Bochnak, M. Coste, and M.-F. Roy. Real Algebraic Geometry. Springer, Berlin, 1998.MATH CrossRef
  7. J. Bolte, A. Daniilidis, A.S. Lewis, and M. Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18:556鈥?72, 2007.MATH MathSciNet CrossRef
  8. J.M. Borwein and Q.J. Zhu. Techniques of Variational Analysis. Springer, New York, 2005.MATH
  9. L.M. Bregman. The method of successive projection for finding a common point of convex sets. Soviet Mathematics Doklady, 6:688鈥?92, 1965.MATH
  10. F.H. Clarke, Yu. Ledyaev, R.I. Stern, and P.R. Wolenski. Nonsmooth Analysis and Control Theory. Springer, New York, 1998.MATH
  11.M. Coste. An Introduction to O-Minimal Geometry. RAAG Notes, 81 pages, Institut de Recherche Math茅matiques de Rennes, November 1999.
  12.M. Coste. An Introduction to Semialgebraic Geometry. RAAG Notes, 78 pages, Institut de Recherche Math茅matiques de Rennes, October 2002.
  13.D. Drusvyatskiy. Slope and Geometry in Variational Mathematics. PhD thesis, School of Operations Research and Information Engineering, Cornell University, August 2013.
  14.D. Drusvyatskiy, A.D. Ioffe, and A.S. Lewis. Alternating projections and coupling slope. arXiv:鈥?401.鈥?569v1 , January 2014.
  15. D. Drusvyatskiy, A.D. Ioffe, and A.S. Lewis. Curves of descent. SIAM Journal on Control and Optimization, 53:114鈥?38, 2015.MathSciNet CrossRef
  16. L.G. Gubin, Polyak B.T., and Raik E.V. The method of projections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics, 7:1鈥?4, 1967.CrossRef
  17. R. Hesse and D.R. Luke. Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM Journal on Optimization, 23:2397鈥?419, 2013.MATH MathSciNet CrossRef
  18. L. H枚rmander. The Analysis of Linear Partial Differential Operators, volume III. Springer, Berlin, 1985.
  19. A.D. Ioffe. Metric regularity and subdifferential calculus. Uspekhi Matematicheskikh Nauk, 55:103鈥?62, 2000.MathSciNet CrossRef
  20. A.D. Ioffe. A Sard theorem for tame set-valued mappings. Journal of Mathematical Analysis and Applications, 335:882鈥?01, 2007.MATH MathSciNet CrossRef
  21. A.D. Ioffe. Critical values of set-valued maps with stratifiable graphs. Extensions of Sard and Smale-Sard theorems. Proceedings of the American Mathematical Society, 136:3111鈥?119, 2008.MATH MathSciNet CrossRef
  22. A.D. Ioffe. An invitation to tame optimization. SIAM Journal on Optimization, 19:1894鈥?917, 2009.MATH MathSciNet CrossRef
  23.A.D. Ioffe. Metric regularity. theory and applications鈥攁 survey. arXiv:鈥?505.鈥?7920 , May 2015.
  24. A.Y. Kruger and N.H. Thao. Quantitative characterizations of regularity properties of collections of sets. Journal of Optimization Theory and Applications, 164:41鈥?7, 2015.MATH MathSciNet CrossRef
  25.A.Y. Kruger and N.H. Thao. Regularity of collections of sets and convergence of inexact alternating projections. arXiv:鈥?501.鈥?4191 , 2015.
  26. K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de l鈥檌nstitut Fourier (Grenoble), 48:769鈥?83, 1998.MATH MathSciNet CrossRef
  27.A.S. Lewis. Nonsmooth optimization: conditioning, convergence and semi-algebraic models. In S.Y. Jang, Y.R. Kim, D.-W. Lee, and I. Yie, editors, Proceedings of the International Congress of Mathematicians, Seoul, volume IV: Invited Lectures, pages 872鈥?95, Seoul, Korea, 2014. Kyung Moon Sa.
  28. A.S. Lewis, D.R. Luke, and J. Malick. Local linear convergence for alternating and averaged nonconvex projections. Foundations of Computational Mathematics, 9:485鈥?13, 2009.MATH MathSciNet CrossRef
  29. A.S. Lewis and J. Malick. Alternating projections on manifolds. Mathematics of Operations Research, 33:216鈥?34, 2008.MATH MathSciNet CrossRef
  30. B.S. Mordukhovich. Variational Analysis and Generalized Differentiation I: Basic Theory. Springer, Berlin, 2006.
  31. B.S. Mordukhovich. Variational Analysis and Generalized Differentiation II: Applications. Springer, Berlin, 2006.
  32.D. Noll and A. Rondepierre. On local convergence of the method of alternating projections. arXiv:鈥?312.鈥?681v1 , December 2013.
  33.D. Noll and A. Rondepierre. On local convergence of the method of alternating projections. arXiv:鈥?312.鈥?681v2 , September 2014.
  34.D. Noll and A. Rondepierre. On local convergence of the method of alternating projections. Foundations of Computational Mathematics, 2015. doi:10.鈥?007/鈥媠10208-015-9253-0 .
  35. R.T. Rockafellar and R.J-B. Wets. Variational Analysis. Springer, Berlin, 1998.MATH CrossRef
  36. J. von Neumann. Functional Operators. II. The Geometry of Orthogonal Spaces. Annals of Mathematics Studies, 22. Princeton University Press, Princeton, NJ, 1950.
  
• 作者单位：D. Drusvyatskiy (1)
  A. D. Ioffe (2)
  A. S. Lewis (3)
  
  1. Department of Mathematics, University of Washington, Seattle, WA, 98195, USA
  2. Mathematics Department, Technion-Israel Institute of Technology, 32000, Haifa, Israel
  3. ORIE, Cornell University, Ithaca, NY, 14853, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Computer Science, general
  Math Applications in Computer Science
  Linear and Multilinear Algebras and Matrix Theory
  Applications of Mathematics
  
• 出版者：Springer New York
• ISSN：1615-3383

文摘

We consider the method of alternating projections for finding a point in the intersection of two closed sets, possibly nonconvex. Assuming only the standard transversality condition (or a weaker version thereof), we prove local linear convergence. When the two sets are semi-algebraic and bounded, but not necessarily transversal, we nonetheless prove subsequence convergence. Keywords Alternating projections Linear convergence Variational analysis Slope Transversality