Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]