Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Foundations of Computational Mathematics
Erschienen in: Foundations of Computational Mathematics 6/2015

01.12.2015

Transversality and Alternating Projections for Nonconvex Sets

verfasst von: D. Drusvyatskiy, A. D. Ioffe, A. S. Lewis

Erschienen in: Foundations of Computational Mathematics | Ausgabe 6/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.
Vorheriger Artikel Propagation of 1D Waves in Regular Discrete Heterogeneous Media: A Wigner Measure Approach
Nächster Artikel On a Full Discretisation for Nonlinear Second-Order Evolution Equations with Monotone Damping: Construction, Convergence, and Error Estimates

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
[34, Remark 10] states that “intrinsic transversality [the property, weaker than transversality, that we actually use to guarantee linear convergence] amalgamates transversality and regularity aspects”. However, that statement concerns “regularity” aspects that involve both sets, like the idea of “linear regularity” in [3].
 
2
The proof of [33, Proposition 8] states: “Following entirely the argument in [14, p.6]...”.
 
Literatur
1.
F. Andersson and M. Carlsson. Alternating projections on nontangential manifolds. Constructive Approximation, 38:489–525, 2013.MATHMathSciNetCrossRef
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–457, 2010.MATHMathSciNetCrossRef
3.
H.H. Bauschke and J.M. Borwein. On the convergence of von Neumann’s alternating projection algorithm for two sets. Set-Valued Analysis, 1:185–212, 1993.MATHMathSciNetCrossRef
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–501, 2013.MATHMathSciNetCrossRef
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–473, 2013.MATHMathSciNetCrossRef
6.
J. Bochnak, M. Coste, and M.-F. Roy. Real Algebraic Geometry. Springer, Berlin, 1998.MATHCrossRef
7.
J. Bolte, A. Daniilidis, A.S. Lewis, and M. Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18:556–572, 2007.MATHMathSciNetCrossRef
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–692, 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.
15.
D. Drusvyatskiy, A.D. Ioffe, and A.S. Lewis. Curves of descent. SIAM Journal on Control and Optimization, 53:114–138, 2015.MathSciNetCrossRef
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–24, 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–2419, 2013.MATHMathSciNetCrossRef
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–162, 2000.MathSciNetCrossRef
20.
A.D. Ioffe. A Sard theorem for tame set-valued mappings. Journal of Mathematical Analysis and Applications, 335:882–901, 2007.MATHMathSciNetCrossRef
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–3119, 2008.MATHMathSciNetCrossRef
22.
23.
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–67, 2015.MATHMathSciNetCrossRef
25.
A.Y. Kruger and N.H. Thao. Regularity of collections of sets and convergence of inexact alternating projections. arXiv:​1501.​04191, 2015.
26.
K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier (Grenoble), 48:769–783, 1998.MATHMathSciNetCrossRef
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–895, 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–513, 2009.MATHMathSciNetCrossRef
29.
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.
33.
34.
35.
36.
J. von Neumann. Functional Operators. II. The Geometry of Orthogonal Spaces. Annals of Mathematics Studies, 22. Princeton University Press, Princeton, NJ, 1950.
Metadaten
Titel
Transversality and Alternating Projections for Nonconvex Sets
verfasst von
D. Drusvyatskiy
A. D. Ioffe
A. S. Lewis
Publikationsdatum
01.12.2015
Verlag
Springer US
Erschienen in
Foundations of Computational Mathematics / Ausgabe 6/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-015-9279-3

Weitere Artikel der Ausgabe 6/2015

Foundations of Computational Mathematics 6/2015 Zur Ausgabe

OriginalPaper

Besov regularity for operator equations on patchwise smooth manifolds

OriginalPaper

Metrics for Generalized Persistence Modules

OriginalPaper

Quadrature for Self-affine Distributions on

OriginalPaper

Optimal A Priori Discretization Error Bounds for Geodesic Finite Elements

OriginalPaper

Improvements to the Deformation Method for Counting Points on Smooth Projective Hypersurfaces

OriginalPaper

On a Full Discretisation for Nonlinear Second-Order Evolution Equations with Monotone Damping: Construction, Convergence, and Error Estimates

Premium Partner

    Bildnachweise