Local Linear Convergence for Alternating and Averaged Nonconvex Projections

The idea of a finite collection of closed sets having “linearly regular intersection” at a point is crucial in variational analysis. This central theoretical condition also has striking algorithmic consequences: in the case of two sets, one of which satisfies a further regularity condition (convexity or smoothness, for example), we prove that von Neumann’s method of “alternating projections” converges locally to a point in the intersection, at a linear rate associated with a modulus of regularity. As a consequence, in the case of several arbitrary closed sets having linearly regular intersection at some point, the method of “averaged projections” converges locally at a linear rate to a point in the intersection. Inexact versions of both algorithms also converge linearly. Research of A.S. Lewis supported in part by National Science Foundation Grant DMS-0504032. Research of D.R. Luke supported in part by National Science Foundation Grant DMS-0712796.     

Strong Convergence of Alternating Projections

Journal of Optimization Theory and Applications - In this paper, we provide a necessary and sufficient condition under which the method of alternating projections on Hadamard spaces converges...     

关于Schwarz交替法的收敛因子

§1.Schwarz交替法的收敛因子 我们就二阶自共轭椭圆型方程的Dirichlet问题来讨论.设Ω?R~2为一多边形区域, a(u,v)=(f,v),v∈H_0~1(Ω),f∈H~(-1)(Ω), u∈H_0~1(Ω)是定义在其上的边值问题的变分形式,双线性型时a(·,·)满足     

度量投影的收敛性（英文）

讨论了赋范空间中度量投影的收敛性．得到了在局部紧集控制下，Chebyshev凸集序列的度量投影的收敛性与K－M收敛，Wijsman收敛和Kuratowski收敛都等价．本文的结论完善了M．Tsukada在[1]和[2]结果．     

On the Local Convergence of a Penalty-Function-Free SQP Method

In this article, we propose a nonmonotone linesearch sequential quadratic programming method for general constrained optimization problems without a penalty function or a filter. The algorithm proposed here is a development of the algorithm in Xue et al. [17 W. Xue , C. Shen , and D. Pu ( 2009 ). A penalty-function-free line search SQP method for nonlinear programming . Journal of Computational and Applied Mathematics 228 ( 1 ): 313 – 325 .[Crossref], [Web of Science ®] , [Google Scholar]]. Compared with the former, the novelty of the method we propose is that the new algorithm will achieve the local convergence under weaker assumptions. In order to avoid the Maratos effect, we use the second-order correction in this method, which need not be computed at each iteration. In other words, after a certain number of iterations, there is no need to compute the second-order correction step any more. The global convergence and the locally superlinear convergence of our method are proved under some suitable conditions.     

Restricted Normal Cones and the Method of Alternating Projections: Theory

In this paper, we introduce and develop the theory of restricted normal cones which generalize the classical Mordukhovich normal cone. We thoroughly study these objects from the viewpoint of constraint qualifications and regularity. Numerous examples are provided to illustrate the theory. This work provides the theoretical underpinning for a subsequent article in which these tools are applied to obtain a convergence analysis of the method of alternating projections for nonconvex sets.     

Restricted Normal Cones and the Method of Alternating Projections: Applications

The method of alternating projections (MAP) is a common method for solving feasibility problems. While employed traditionally to subspaces or to convex sets, little was known about the behavior of the MAP in the nonconvex case until 2009, when Lewis, Luke, and Malick derived local linear convergence results provided that a condition involving normal cones holds and at least one of the sets is superregular (a property less restrictive than convexity). However, their results failed to capture very simple classical convex instances such as two lines in a three-dimensional space. In this paper, we extend and develop the Lewis-Luke-Malick framework so that not only any two linear subspaces but also any two closed convex sets whose relative interiors meet are covered. We also allow for sets that are more structured such as unions of convex sets. The key tool required is the restricted normal cone, which is a generalization of the classical Mordukhovich normal cone. Numerous examples are provided to illustrate the theory.     

Alternating Projections on Nontangential Manifolds

We consider sequences $(B_{k})_{k=0}^{\infty}$ of points obtained by projecting a given point B=B ₀ back and forth between two manifolds $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ , and give conditions guaranteeing that the sequence converges to a limit $B_{\infty}\in\mathcal{M}_{1}\cap\mathcal{M}_{2}$ . Our motivation is the study of algorithms based on finding the limit of such sequences, which have proved useful in a number of areas. The intersection is typically a set with desirable properties but for which there is no efficient method for finding the closest point B _opt in $\mathcal{M}_{1}\cap\mathcal{M}_{2}$ . Under appropriate conditions, we prove not only that the sequence of alternating projections converges, but that the limit point is fairly close to B _opt , in a manner relative to the distance ∥B ₀?B _opt ∥, thereby significantly improving earlier results in the field.     

On the Local Convergence of Modified Homeier-Like Method in Banach Spaces

The aim of this article is to investigate the local convergence analysis of the multi-step Homeier-like approach in order to approximate the solution of nonlinear equations in Banach spaces, which fulfilled the Lipschitz as well as Hölder continuity condition. The Hölder condition is more relax than Lipschitz condition. Also, the existence and uniqueness theorem has been derived and found their error bounds. Numerical examples are available to appear the importance of theoretical discussions.     

On the Convergence of Alternating Series Associated with Beatty Sequences

Mathematical Notes -     

Optimal Rates of Linear Convergence of Relaxed Alternating Projections and Generalized Douglas-Rachford Methods for Two Subspaces

We systematically study the optimal linear convergence rates for several relaxed alternating projection methods and the generalized Douglas-Rachford splitting methods for finding the projection on the intersection of two subspaces. Our analysis is based on a study on the linear convergence rates of the powers of matrices. We show that the optimal linear convergence rate of powers of matrices is attained if and only if all subdominant eigenvalues of the matrix are semisimple. For the convenience of computation, a nonlinear approach to the partially relaxed alternating projection method with at least the same optimal convergence rate is also provided. Numerical experiments validate our convergence analysis     

Finite Convergence of a Subgradient Projections Method with Expanding Controls

We study finite convergence of the modified cyclic subgradient projections (MCSP) algorithm for the convex feasibility problem (CFP) in the Euclidean space. Expanding control sequences allow the indices of the sets of the CFP to re-appear and be used again by the algorithm within windows of iteration indices whose lengths are not constant but may increase without bound. Motivated by another development in finitely convergent sequential algorithms that has a significant real-world application in the field of radiation therapy treatment planning, we show that the MCSP algorithm retains its finite convergence when used with an expanding control that is repetitive and fulfills an additional condition.     

Local Stability and Local Convergence of the Basic Trust-Region Method

It is proved that the iterative sequence constructed by the Basic Trust-Region Algorithm (see Conn et al. in Trust-region methods, MPS-SIAM series on optimization, Philadelphia, 2000), which uses the Cauchy point method, is locally stable and linearly convergent in a neighborhood of a nonsingular local minimizer.     

On the Local Convergence Analysis of the Gradient Sampling Method for Finite Max-Functions

The gradient sampling method is a recently developed tool for solving unconstrained nonsmooth optimization problems. Using just first-order information about the objective function, it generalizes the steepest descent method, one of the most classical methods for minimizing a smooth function. This study aims at determining under which circumstances one can expect the same local convergence result of the Cauchy method for the gradient sampling algorithm under the assumption that the problem is stated by a finite max-function around the optimal point. Additionally, at the end, we show how to practically accomplish the required hypotheses during the execution of the algorithm.     

三种变形调和级数的收敛性

给出了三种变形调和级数,证明了相应的收敛性,并给出了其收敛值的计算方法.     

交错级数收敛性判别法

研究交错级数收敛性判别法.通过计算级数通项的极限和单调性得到三个判据,并对其中两个结论给出形式简化的推论,最后举例说明所提判别法的应用.     

Convergence of an Alternating Method to Solve the Cauchy Problem for Poisson's Equation

This work concerns the development of iterative algorithms for the solution of the Cauchy problem for the Poisson equation. We accelerate the process proposed by Kozlov et al. [V.A. Kozlov, V.G. Maz'ya and A.V. Fomin (1991). An iterative method for solving the Cauchy problem for elliptic equations. Comput. Maths. Phys. , 31 (1), 45-52.] by making use of a relaxation of the Dirichlet data. We provide theoretical justification of the convergence of the new algorithm, and present some results of numerical experiments with the method.     

交错级数敛散性判别法

给出交错级数的几个判别法,它们可直接用以判别交错级数是绝对收敛,条件收敛还是发散.