Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0807.41019
Deutsch, Frank; Hundal, Hein
The rate of convergence of Dykstra's cyclic projections algorithm: The polyhedral case.
(English)
[J] Numer. Funct. Anal. Optimization 15, No.5-6, 537-565 (1994). ISSN 0163-0563; ISSN 1532-2467/e

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\sb n\}$ generated by Dykstra's cyclic projections algorithm satisfies the inequality $\Vert x\sb n- P\sb K(x)\Vert\le \rho c\sp n$ for all $n$, where $P\sb K(x)$ is the nearest point in $K$ to $x$, $\rho$ is a constant, and $0\le 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 $\Vert x\sb n- P\sb K(x)\Vert\le c\sp{n-1}\Vert x- P\sb K(x)\Vert$ 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 2000:
*41A65 Abstract approximation theory
47N10 Appl. of operator theory in optimization, math. programming, etc.
49M30 Methods of successive approximation, not based on necessary cond.

Keywords: isotone regression; convex regression; linear programming; Hildreth's algorithm; Dykstra's cyclic projections algorithm; quadratic programming

Highlights
Master Server