On variable-step relaxed projection algorithm for variational inequalities

Projection algorithms are practically useful for solving variational inequalities (VI). However some among them require the knowledge related to VI in advance, such as Lipschitz constant. Usually it is impossible in practice. This paper studies the variable-step basic projection algorithm and its relaxed version under weakly co-coercive condition. The algorithms discussed need not know constant/function associated with the co-coercivity or weak co-coercivity and the step-size is varied from one iteration to the next. Under certain conditions the convergence of the variable-step basic projection algorithm is established. For the practical consideration, we also give the relaxed version of this algorithm, in which the projection onto a closed convex set is replaced by another projection at each iteration and latter is easy to calculate. The convergence of relaxed scheme is also obtained under certain assumptions. Finally we apply these two algorithms to the Split Feasibility Problem (SFP).     

Weak convergence theorems of the modified relaxed projection algorithms for the split feasibility problem in Hilbert spaces

In this paper, we introduce a modified relaxed projection algorithm and a modified variable-step relaxed projection algorithm for the split feasibility problem in infinite-dimensional Hilbert spaces. The weak convergence theorems under suitable conditions are proved. Finally, some numerical results are presented, which show the advantage of the proposed algorithms.     

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

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

Relaxed two points projection method for solving the multiple-sets split equality problem

The multiple-sets split equality problem, a generalization and extension of the split feasibility problem, has a variety of specific applications in real world, such as medical care, image reconstruction, and signal processing. It can be a model for many inverse problems where constraints are imposed on the solutions in the domains of two linear operators as well as in the operators’ ranges simultaneously. Although, for the split equality problem, there exist many algorithms, there are but few algorithms for the multiple-sets split equality problem. Hence, in this paper, we present a relaxed two points projection method to solve the problem; under some suitable conditions, we show the weak convergence and give a remark for the strong convergence method in the Hilbert space. The interest of our algorithm is that we transfer the problem to an optimization problem, then, based on the model, we present a modified gradient projection algorithm by selecting two different initial points in different sets for the problem (we call the algorithm as two points algorithm). During the process of iteration, we employ subgradient projections, not use the orthogonal projection, which makes the method implementable. Numerical experiments manifest the algorithm is efficient.     

Convergence of a generalized Newton and an inexact generalized Newton algorithms for solving nonlinear equations with nondifferentiable terms

In this paper, we consider two versions of the Newton-type method for solving a nonlinear equations with nondifferentiable terms, which uses as iteration matrices, any matrix from B-differential of semismooth terms. Local and global convergence theorems for the generalized Newton and inexact generalized Newton method are proved. Linear convergence of the algorithms is obtained under very mild assumptions. The superlinear convergence holds under some conditions imposed on both terms of equation. Some numerical results indicate that both algorithms works quite well in practice.      

Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

Generalized Mann iterates for constructing fixed points in Hilbert spaces

The mean iteration scheme originally proposed by Mann is extended to a broad class of relaxed, inexact fixed point algorithms in Hilbert spaces. Weak and strong convergence results are established under general conditions on the underlying averaging process and the type of operators involved. This analysis significantly widens the range of applications of mean iteration methods. Several examples are given.     

An Accelerated Inexact Proximal Point Algorithm for Convex Minimization

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/k ²) is proposed.     

A perturbed version of an inexact generalized Newton method for solving nonsmooth equations

In this paper, we present the combination of the inexact Newton method and the generalized Newton method for solving nonsmooth equations F(x)?=?0, characterizing the local convergence in terms of the perturbations and residuals. We assume that both iteration matrices taken from the B-differential and vectors F(x ^(k)) are perturbed at each step. Some results are motivated by the approach of C?tina? regarding to smooth equations. We study the conditions, which determine admissible magnitude of perturbations to preserve the convergence of method. Finally, the utility of these results is considered based on some variant of the perturbed inexact generalized Newton method for solving some general optimization problems.     

Modified basic projection methods for a class of equilibrium problems

Projection methods are a popular class of methods for solving equilibrium problems. In this paper, we propose approximate one projection methods for solving a class of equilibrium problems, where the cost bifunctions are paramonotone, the feasible sets are defined by a continuous convex function inequality and not necessarily differentiable in the Euclidean space \(\mathcal R^{s}\). At each main iteration step in our algorithms, the usual projections onto the feasible set are replaced by computing inexact subgradients and one projection onto the intersection of two halfspaces containing the solution set of the equilibrium problems. Then, by choosing suitable parameters, we prove convergence of the whole generated sequence to a solution of the problems, under only the assumptions of continuity and paramonotonicity of the bifunctions. Finally, we present some computational examples to illustrate the assumptions of the proposed algorithms.     

A new inertial-type hybrid projection-proximal algorithm for monotone inclusions

This paper investigates an enhanced proximal algorithm with interesting practical features and convergence properties for solving non-smooth convex minimization problems, or approximating zeroes of maximal monotone operators, in Hilbert spaces. The considered algorithm involves a recent inertial-type extrapolation technique, the use of enlargement of operators and also a recently proposed hybrid strategy, which combines inexact computation of the proximal iteration with a projection. Compared to other existing related methods, the resulting algorithm inherits the good convergence properties of the inertial-type extrapolation and the relaxed projection strategy. It also inherits the relative error tolerance of the hybrid proximal-projection method. As a special result, an update of inexact Newton-proximal method is derived and global convergence results are established.     

An inexact line search approach using modified nonmonotone strategy for unconstrained optimization

This paper concerns with a new nonmonotone strategy and its application to the line search approach for unconstrained optimization. It has been believed that nonmonotone techniques can improve the possibility of finding the global optimum and increase the convergence rate of the algorithms. We first introduce a new nonmonotone strategy which includes a convex combination of the maximum function value of some preceding successful iterates and the current function value. We then incorporate the proposed nonmonotone strategy into an inexact Armijo-type line search approach to construct a more relaxed line search procedure. The global convergence to first-order stationary points is subsequently proved and the R-linear convergence rate are established under suitable assumptions. Preliminary numerical results finally show the efficiency and the robustness of the proposed approach for solving unconstrained nonlinear optimization problems.     

Smoothing SQP algorithm for semismooth equations with box constraints

In this paper, in order to solve semismooth equations with box constraints, we present a class of smoothing SQP algorithms using the regularized-smooth techniques. The main difference of our algorithm from some related literature is that the correspondent objective function arising from the equation system is not required to be continuously differentiable. Under the appropriate conditions, we prove the global convergence theorem, in other words, any accumulation point of the iteration point sequence generated by the proposed algorithm is a KKT point of the corresponding optimization problem with box constraints. Particularly, if an accumulation point of the iteration sequence is a vertex of box constraints and additionally, its corresponding KKT multipliers satisfy strictly complementary conditions, the gradient projection of the iteration sequence finitely terminates at this vertex. Furthermore, under local error bound conditions which are weaker than BD-regular conditions, we show that the proposed algorithm converges superlinearly. Finally, the promising numerical results demonstrate that the proposed smoothing SQP algorithm is an effective method.     

A globally convergent non-interior point algorithm with full Newton step for second-order cone programming

A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of A to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.     

An inexact modified relaxed splitting preconditioner for the generalized saddle point problems from the incompressible Navier-Stokes equations

Based on the modified relaxed splitting (MRS) preconditioner proposed by Fan and Zhu (Appl. Math. Lett. 55, 18–26 2016), an inexact modified relaxed splitting (IMRS) preconditioner is proposed for the generalized saddle point problems arising from the incompressible Navier-Stokes equations. The eigenvalues and eigenvectors of the preconditioned matrix are analyzed, and the convergence property of the corresponding iteration method is also discussed. Numerical experiments are presented to show the effectiveness of the proposed preconditioner when it is used to accelerate the convergence rate of Krylov subspace methods such as GMRES.     

Generalized Krasnoselskii–Mann-type iterations for nonexpansive mappings in Hilbert spaces

The Krasnoselskii–Mann iteration plays an important role in the approximation of fixed points of nonexpansive operators; it is known to be weakly convergent in the infinite dimensional setting. In this present paper, we provide a new inexact Krasnoselskii–Mann iteration and prove weak convergence under certain accuracy criteria on the error resulting from the inexactness. We also show strong convergence for a modified inexact Krasnoselskii–Mann iteration under suitable assumptions. The convergence results generalize existing ones from the literature. Applications are given to the Douglas–Rachford splitting method, the Fermat–Weber location problem as well as the alternating projection method by John von Neumann.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.     

Alternative gradient algorithms with applications to nonnegative matrix factorizations

Three nonnegative matrix factorization (NMF) algorithms are discussed and employed to three real-world applications. Based on the alternative gradient algorithm with the iteration steps being determined columnwisely without projection, and columnwisely and elementwisely with projections, three algorithms are developed respectively. Also, the computational costs and the convergence properties of the new algorithms are given. The numerical examples show the advantage of our algorithms over the multiplicative update algorithm proposed by Lee and Seung [11].     

On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.