How good are projection methods for convex feasibility problems?

We consider simple projection methods for solving convex feasibility problems. Both successive and sequential methods are considered, and heuristics to improve these are suggested. Unfortunately, particularly given the large literature which might make one think otherwise, numerical tests indicate that in general none of the variants considered are especially effective or competitive with more sophisticated alternatives. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This work was supported by the EPSRC grant GR/S42170.     

On the proximal point method for equilibrium problems in Hilbert spaces

We analyse a proximal point method for equilibrium problems in Hilbert spaces, improving upon previously known convergence results. We prove global weak convergence of the generated sequence to a solution of the problem, assuming existence of solutions and rather mild monotonicity properties of the bifunction which defines the equilibrium problem, and we establish existence of solutions of the proximal subproblems. We also present a new reformulation of equilibrium problems as variational inequalities ones.     

Extrapolated cyclic subgradient projection methods for the convex feasibility problems and their numerical behaviour

ABSTRACT

We present two versions of the extrapolated cyclic subgradient projections method for solving the convex feasibility problem. Moreover, we present the results of numerical tests, where we compare the methods with the classical cyclic subgradient projections method.     

A note on some analytic center cutting plane methods for convex feasibility and minimization problems

Recently Goffin, Luo and Ye have analyzed the complexity of an analytic center algorithm for convex feasibility problems defined by a separation oracle. The oracle is called at the (possibly approximate) analytic center of the set given by the linear inequalities which are the previous answers of the oracle. We discuss oracles for the problem of minimizing a convex (possibly nondifferentiable) function subject to box constraints, and give corresponding complexity estimates.The research of the first author is supported by the Polish Academy of Sciences; the research of the second author is supported by the State Committee for Scientific Research under Grant 8S50502206.     

Strong convergence of two algorithms for the split feasibility problem in Banach spaces

ABSTRACT

In this paper, we consider the split feasibility problem in Banach spaces. By converting it to an equivalent null-point problem, we propose two iterative algorithms, which are new even in Hilbert spaces. The parameter in one algorithm is chosen in such a way that no priori knowledge of the operator norms is required. It is shown that these two algorithms are strongly convergent provided that the involved Banach spaces are smooth and uniformly convex. Finally, we conduct numerical experiments to support the validity of the obtained results.     

A method of stochastic subgradients with complete feedback stepsize rule for convex stochastic approximation problems

A stochastic subgradient algorithm for solving convex stochastic approximation problems is considered. In the algorithm, the stepsize coefficients are controlled on-line on the basis of information gathered in the course of computations according to a new, complete feedback rule derived from the concept of regularized improvement function. Convergence with probability 1 of the method is established.This work was supported by Project No. CPBP/02.15.     

Incomplete projection algorithms for solving the convex feasibility problem

We present a general scheme for solving the convex feasibility problem and prove its convergence under mild conditions. Unlike previous schemes no exact projections are required. Moreover, we also introduce an acceleration factor, which we denote as the factor, that seems to play a fundamental role to improve the quality of convergence. Numerical tests on systems of linear inequalities randomly generated give impressive results in a multi-processing environment. The speedup is superlinear in some cases. New acceleration techniques are proposed, but no tests are reported here. As a by-product we obtain the rather surprising result that the relaxation factor, usually confined to the interval (0,2), gives better convergence results for values outside this interval.     

Iterative Averaging of Entropic Projections for Solving Stochastic Convex Feasibility Problems

The problem considered in this paper is that of finding a point which iscommon to almost all the members of a measurable family of closed convexsubsets of R₊₊ ⁿ , provided that such a point exists.The main results show that this problem can be solved by an iterative methodessentially based on averaging at each step the Bregman projections withrespect to f(x)=_i=1 ⁿx_i· ln x_i ofthe current iterate onto the given sets.     

A proximal-Newton method for unconstrained convex optimization in Hilbert spaces

We propose and study the iteration-complexity of a proximal-Newton method for finding approximate solutions of the problem of minimizing a twice continuously differentiable convex function on a (possibly infinite dimensional) Hilbert space. We prove global convergence rates for obtaining approximate solutions in terms of function/gradient values. Our main results follow from an iteration-complexity study of an (large-step) inexact proximal point method for solving convex minimization problems.     

Extragradient methods for split feasibility problems and generalized equilibrium problems in Banach spaces

The purpose of this paper is the presentation of a new extragradient algorithm in 2‐uniformly convex real Banach spaces. We prove that the sequences generated by this algorithm converge strongly to a point in the solution set of split feasibility problem, which is also a common element of the solution set of a generalized equilibrium problem and fixed points of of two relatively nonexpansive mappings. We give a numerical example to investigate the behavior of the sequences generated by our algorithm.     

Asymptotic confidence regions of stochastic approximation procedures in hilbert spaces

In the framework of stochastic approximation, in separable Hilbert spaces one can often establish weak convergence for a suitable normalized, sequence of random variables to a Gaussian distributed random varible. In connection with a sequence of empirical covariance operators and estimator of the unknown radius of a ball is described, for which the Gaussian limit distribution, takes a given value. Further a stopping rule is proposed leading to asymptotic confidence balls with a fixed radius.     

Block-iterative algorithms for solving convex feasibility problems in Hilbert and in Banach spaces

We establish convergence theorems for two different block-iterative methods for solving the problem of finding a point in the intersection of the fixed point sets of a finite number of nonexpansive mappings in Hilbert and in finite-dimensional Banach spaces, respectively.     

Accelerated Landweber iteration with convex penalty for linear inverse problems in Banach spaces

In recent years, Landweber iteration has been extended to solve linear inverse problems in Banach spaces by incorporating non-smooth convex penalty functionals to capture features of solutions. This method is known to be slowly convergent. However, because it is simple to implement, it still receives a lot of attention. By making use of the subspace optimization technique, we propose an accelerated version of Landweber iteration with non-smooth convex penalty which significantly speeds up the method. Numerical simulations are given to test the efficiency.     

Deformation in locally convex topological linear spaces

We are concerned with a deformation theory in locally convex topological linear spaces. A special "nice" partition of unity is given. This enables us to construct certain vector fields which are locally Lipschitz continuous with respect to the locally convex topology. The existence, uniqueness and continuous dependence of flows associated to the vector fields are established. Deformations related to strongly indefinite functionals are then obtained. Finally, as applications, we prove some abstract critical point theorems.     

凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.     

On the finite termination of the Douglas-Rachford method for the convex feasibility problem

In this paper we apply the Douglas–Rachford (DR) method to solve the problem of finding a point in the intersection of the interior of a closed convex cone and a closed convex set in an infinite-dimensional Hilbert space. For this purpose, we propose two variants of the DR method which can find a point in the intersection in a finite number of iterations. In order to analyse the finite termination of the methods, we use some properties of the metric projection and a result regarding the rate of convergence of fixed point iterations. As applications of the results, we propose the methods for solving the conic and semidefinite feasibility problems, which terminate at a solution in a finite number of iterations.     

Convex feasibility modeling and projection methods for sparse signal recovery

A computationally-efficient method for recovering sparse signals from a series of noisy observations, known as the problem of compressed sensing (CS), is presented. The theory of CS usually leads to a constrained convex minimization problem. In this work, an alternative outlook is proposed. Instead of solving the CS problem as an optimization problem, it is suggested to transform the optimization problem into a convex feasibility problem (CFP), and solve it using feasibility-seeking sequential and simultaneous subgradient projection methods, which are iterative, fast, robust and convergent schemes for solving CFPs. As opposed to some of the commonly-used CS algorithms, such as Bayesian CS and Gradient Projections for sparse reconstruction, which become inefficient as the problem dimension and sparseness degree increase, the proposed methods exhibit robustness with respect to these parameters. Moreover, it is shown that the CFP-based projection methods are superior to some of the state-of-the-art methods in recovering the signal’s support. Numerical experiments show that the CFP-based projection methods are viable for solving large-scale CS problems with compressible signals.