The Hybrid Steepest Descent Method for the Variational Inequality Problem Over the Intersection of Fixed Point Sets of Nonexpansive Mappings

https://doi.org/10.1016/S1570-579X(01)80028-8Get rights and content

Section snippets

INTRODUCTION

The Variational Inequality Problem 6., 52., 118., 119. has been and will continue to be one of the central problems in nonlinear analysis and is defined as follows: given monotone operator : and closed convex set C  ℋ, where ℋ is a real Hilbert space with inner product 〈·,·〉 and induced norm ∥ · ∥, find x* ∈ C such that 〈x  x*, ℱ(x*)〉  0 for all xC. This condition is the optimality condition of the convex optimization problem: min Θ over C when ℱ = Θ ′. The simplest iterative procedure for the

Fixed points, Nonexpansive mappings, and Convex projections

A fixed point of a mapping T :   ℋ is a point x  ℋ such that T(x) = x. Fix(T) := {x   | T(x) = x} denotes the set of all fixed points of T. A mapping T :   ℋ is called κ-Lipschitzian (or κ-Lipschitz continuous) over S  ℋ if there exists κ > 0 such thatTxTyκxyforallx,yS.

In particular, a mapping T :   ℋ is called (i) strictly contractive if ‖T(x)  T(y)‖  κx  y‖ for some κ ∈ (0,1) and all x, y  ℋ [ The Banach-Picard fixed point theorem guarantees the unique existence of the fixed point, say x* ∈ Fix(T), of T and

HYBRID STEEPEST DESCENT METHOD

The hybrid steepest descent method for minimization of certain convex functions over the set of fixed points of nonexpansive mappings 108., 109., 47., 111., 112., 80. has been developed by generalizing the results for approximation of the fixed point of nonexpansive mappings. To demonstrate simply the underlying ideas of the hybrid steepest descent method, we present it as algorithmic solutions to the variational inequality problem (VIP) defined over the fixed point set of nonexpansive

Projection algorithms for best approximation and convex feasibility problems

The best approximation problem of finding the projection of a given point in a Hilbert space onto the (nonempty) intersection C=i=1mCi of a finite number of closed convex sets Ci (i = 1,2 …, m) arises in many branches of applied mathematics, the physical and computer sciences, and engineering. One frequently employed approach to solving this problem is algorithmic. The idea of this approach is to generate a sequence of points which converges to the solution of the problem by using projections

CONCLUDING REMARKS

In this paper, we have presented in a simple way the underlying ideas of the hybrid steepest descent method as an algorithmic solution to a VIP defined over the fixed point set of a nonexpansive mapping in a real Hilbert space. As seen from the discussion in section 4, the proposed hybrid steepest descent method plays notable roles in various inverse problems. Some straightforward applications of the hybrid steepest descent method to certain signal estimation or design problems have been shown

Acknowledgments

It is my great honor to thank Frank Deutsch, Patrick L. Combettes, Heinz H. Bauschke, Jonathan M. Borwein, Boris T. Polyak, Charles L. Byrne, Paul Tseng, M. Zuhair Nashed, K. Tanabe and U. M. Garcia-Palomares for their encouraging advice at the Haifa workshop (March 2000). I also wish to thank Dan Butnariu, Yair Censor and Simeon Reich for giving me this great opportunity and their helpful comments.

First page preview

First page preview
Click to open first page preview

REFERENCES (119)

  • T.M. Apostol
  • J.-P. Aubin
  • C. Sánchez-Avila

    An adaptive regularized method for deconvolution of signal with edges by convex projections

    IEEE Trans. Signal Processing

    (1994)
  • J.-B. Baillon et al.

    On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces

    Houston J. Math.

    (1978)
  • V. Barbu et al.
  • H.H. Bauschke et al.

    On projection algorithms for solving convex feasibility problems

    SIAM Review

    (1996)
  • H.H. Bauschke et al.

    The method of cyclic projections for closed convex sets in Hilbert space

    Contemp. Math.

    (1997)
  • H.H. Bauschke et al.

    Dykstra's algorithm with Bregman projections: a convergence proof

    Optimization

    (2000)
  • J.P. Boyle et al.

    A method for finding projections onto the intersection of convex sets in Hilbert spaces

  • L.M. Bregman

    The method of successive projection for finding a common point of convex sets

    Soviet Math. Dokl.

    (1965)
  • L.M. Bregman et al.

    Dykstra's algorithm as the nonlinear extension of Bregman's optimization method

    J. Convex Analysis

    (1999)
  • F.E. Browder

    Nonexpansive nonlinear operators in Banach space

    Proc. Nat. Acad. Sci. USA

    (1965)
  • F.E. Browder

    Convergence of approximants to fixed points of nonexpansive nonlinear mappings in Banach spaces

    Arch. Rat. Mech. Anal.

    (1967)
  • D. Butnariu et al.

    On the behavior of a block-iterative projection method for solving convex feasibility problems

    International Journal of Computer Mathematics

    (1990)
  • D. Butnariu et al.

    Iterative averaging of entropic projections for solving stochastic convex feasibility

    Computational Optimization and Applications

    (1997)
  • D. Butnariu et al.

    Totally Convex Functions for fixed point computation and infinite dimensional optimization

    (2000)
  • R.E. Bruck et al.

    Nonexpansive projections and resolvents of accretive operators in Banach spaces

    Houston J. Math.

    (1977)
  • C.L. Byrne

    Iterative projection onto convex sets using multiple Bregman distances

    Inverse Problems

    (1999)
  • C.L. Byrne et al.

    Proximity function minimization for separable jointly convex Bregman distances, with applications

    Technical Report

    (1998)
  • C.L. Byrne et al.

    Proximity function minimization using multiple Bregman projections, with applications to split feasibility and Kullback-Leibler distance minimization

    Technical Report

    (2000)
  • Y. Censor

    Row-action methods for huge and sparse systems and their applications

    SIAM Review

    (1981)
  • Y. Censor et al.

    An iterative row-action method for interval convex programming

    Journal of Optimization Theory and Applications

    (1981)
  • Y. Censor

    Parallel application of block-iterative methods in medical imaging and radiation therapy

    Math. Programming

    (1988)
  • Y. Censor et al.

    A multiprojection algorithm using Bregman projections in a product space

    Numerical Algorithms

    (1994)
  • Y. Censor et al.

    The Dykstra algorithm with Bregman projections

    Communications in Applied Analysis

    (1998)
  • Y. Censor et al.
  • Y. Censor et al.

    An interior point method with Bregman functions for the variational inequality problem with paramonotone operators

    Math. Programming

    (1998)
  • W. Cheney et al.

    Proximity maps for convex sets

    Proc. Amer. Math. Soc.

    (1959)
  • C.K. Chui et al.

    Constrained best approximation in Hilbert space

    Constr. Approx.

    (1990)
  • C.K. Chui et al.

    Constrained best approximation in Hilbert space II

    J. Approx. Theory

    (1992)
  • P.L. Combettes

    Inconsistent signal feasibility problems: least squares solutions in a product space

    IEEE Trans. on Signal Processing

    (1994)
  • P.L.Combettes

    Construction d'un point fixe commun à une famille de contractions fermes

    C.R. Acad. Sci. Paris Sèr. I Math.

    (1995)
  • P.L. Combettes

    Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections

    IEEE Trans. Image Processing

    (1997)
  • P.L. Combettes et al.

    Hard-constrained inconsistent signal feasibility problem

    IEEE Trans. Signal Processing

    (1999)
  • P.L. Combettes

    A parallel constraint disintegration and approximation scheme for quadratic signal recovery

  • P.L. Combettes

    Strong convergence of block-iterative outer approximation methods for convex optimization

    SIAM J. Control Optim.

    (2000)
  • G. Crombez

    Finding projections onto the intersection of convex sets in Hilbert spaces

    Numer. Funct. Anal. Optim.

    (1996)
  • F. Deutsch et al.

    The rate of convergence of Dykstra's cyclic projections algorithms: the polyhedral case

    Numer. Funct. Anal. Optim.

    (1994)
  • F. Deutsch et al.

    The rate of convergence for the method of alternating projections II

    J. Math. Anal. Appl.

    (1997)
  • F. Deutsch et al.

    Minimizing certain convex functions over the intersection of the fixed point sets of nonexpansive mappings

    Numer. Funct. Anal. Optim.

    (1998)
  • Cited by (629)

    View all citing articles on Scopus
    View full text