×

zbMATH — the first resource for mathematics

The rate of convergence of Dykstra’s cyclic projections algorithm: The polyhedral case. (English) Zbl 0807.41019
Summary: Suppose \(K\) is the intersection of a finite number of closed half-spaces in a Hilbert space \(X\). Starting with any point \(x\in X\), it is shown that the sequence of iterates \(\{x_ n\}\) generated by Dykstra’s cyclic projections algorithm satisfies the inequality \(\| x_ n- P_ K(x)\|\leq \rho c^ n\) for all \(n\), where \(P_ K(x)\) is the nearest point in \(K\) to \(x\), \(\rho\) is a constant, and \(0\leq c< 1\). In the case when \(K\) is the intersection of just two closed half-spaces, a stronger result is established: the sequence of iterates is either finite or satisfies \(\| x_ n- P_ K(x)\|\leq c^{n-1}\| x- P_ K(x)\|\) for all \(n\), where \(c\) is the cosine of the angle between the two functionals which define the half-spaces. Moreover, the constant \(c\) is the best possible. Applications are made to isotone and convex regression, and linear and quadratic programming.

MSC:
41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics
49M30 Other numerical methods in calculus of variations (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1090/S0002-9947-1950-0051437-7 · doi:10.1090/S0002-9947-1950-0051437-7
[2] Bauschke H. H, J . Approx. Theory 68 (1950)
[3] DOI: 10.1007/BF01027691 · Zbl 0801.47042 · doi:10.1007/BF01027691
[4] Boyle J. P, Advances in Order Restricted Statistical Inference pp 28– (1985)
[5] Bregman L. M, Doklady 162 pp 688– (1965)
[6] DOI: 10.1007/BF01891408 · Zbl 0682.41034 · doi:10.1007/BF01891408
[7] Chui C. K, J. Approx. Theory 71 pp 21– (1992)
[8] Deutsch F., Some Applications of Functional Analysis to Approximation Theory (1965)
[9] Chui C. K, Approximation Theory 4 pp 427– (1983)
[10] Chui C. K, Parametric Optimization and Approximation 72 pp 96– (1984)
[11] Chui C. K, Approximation Theory, Spline Functions and Applications pp 105– (1992)
[12] DOI: 10.1137/1009072 · Zbl 0166.10501 · doi:10.1137/1009072
[13] DOI: 10.2307/2288193 · Zbl 0535.62063 · doi:10.2307/2288193
[14] Fan Ky, Linear Inequalities and Related Systems 38 pp 99– (1956)
[15] DOI: 10.1016/0022-247X(86)90085-5 · Zbl 0617.65049 · doi:10.1016/0022-247X(86)90085-5
[16] DOI: 10.1090/S0002-9947-1937-1501907-0 · JFM 63.0364.01 · doi:10.1090/S0002-9947-1937-1501907-0
[17] DOI: 10.1007/BF02614077 · Zbl 0676.90054 · doi:10.1007/BF02614077
[18] Halperin I., Acta Sci. Math. (Szeged) 23 pp 96– (1962)
[19] DOI: 10.1007/BF01580719 · Zbl 0685.90074 · doi:10.1007/BF01580719
[20] DOI: 10.1002/nav.3800040113 · doi:10.1002/nav.3800040113
[21] DOI: 10.1007/BF01580851 · Zbl 0712.90054 · doi:10.1007/BF01580851
[22] DOI: 10.1007/BF01582891 · Zbl 0744.90066 · doi:10.1007/BF01582891
[23] DOI: 10.1007/BF02551235 · Zbl 0673.65036 · doi:10.1007/BF02551235
[24] Mangasarian O. L, Math. Programming Study 22 pp 206– (1984) · Zbl 0588.90058 · doi:10.1007/BFb0121017
[25] von Neumann J., The Geometry of Orthogonal Spaces (1950) · Zbl 0039.11701
[26] DOI: 10.1090/S0002-9904-1977-14406-6 · Zbl 0521.65090 · doi:10.1090/S0002-9904-1977-14406-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.