Hybrid Moreau’s Proximal Algorithms and Convergence Theorems for Minimization Problems in Hilbert Spaces with Applications

Abstract

In this paper, motivated by Moreau’s proximal algorithm, we give several algorithms and related weak and strong convergence theorems for minimization problems under suitable conditions. These algorithms and convergence theorems are different from the results in the literatures. Besides, we also study algorithms and convergence theorems for the split feasibility problem in real Hilbert spaces. Finally, we give numerical results for our main results.     

A Class of Modified Broyden Algorithms

S1.IntroductionWeknowthatthevariablemetricalgorithms,suchastheBroydenalgorithms,areveryusefulandefficientmethodsforsolvingthenonlinearprogrammingproblem'min{f(x);xER"}-(1.1)Withexactlinearsearch,Powell(1971)provesthattherateofconvergenceofthesealgorithmsisone-stepsuperlinearfortheuniformlyconvexobjectivefunction,andifthepointsgivenbytheseaJgorithmsareconvergent,PuandYu(199o)provethattheyaregloballyconvergentforthecontinuousdifferentiablefunction.Withoutexactlinearsearchseveralresultshavebee…     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

A Class of Revised Broyden Algorithms Without Exact Line Search

In this paper, we discuss the convergence of the Broyden algorithms with revised search direction. Under some inexact line searches, we prove that the algorithms are globally convergent for continuously differentiable functions and the rate of local convergence of the algorithms is one-step superlinear and n-step second-order for uniformly convex objective functions.     

Super greedy type algorithms

We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy algorithms. We call such greedy algorithms super greedy type algorithms. The super greedy type algorithms are computationally simpler than their analogues from the standard greedy algorithms. In this article, we propose the Weak Super Greedy Algorithm (WSGA) and the Weak Orthogonal Super Greedy Algorithm with Thresholding (WOSGAT). Their performance (rate of convergence) are studied as well under M-coherent dictionaries.     

Convergence of the parallel chaotic waveform relaxation method for stiff systems

In this paper, we establish several algorithms for parallel chaotic waveform relaxation methods for solving linear ordinary differential systems based on some given models. Under some different assumptions on the coefficient matrix A and its multisplittings we obtain corresponding sufficient conditions of convergence of the algorithms. Also a discussion on convergence speed comparison of synchronous and asynchronous algorithms is given.     

THE CONVERGENCE OF BROYDEN ALGORITHMS FOR LC GRADIENT FUNCTION

1. IntroductionWe know that the variable metric algorithms, such as the Broyden algorithms, are veryefficient methods for solving the nonlinear programming problem:With exact line search, [11 proved that all the Broyden algorithms produce the same iterations for general functions. [21 proved that the rate of convergellce of these algorithms isone-step superlinear for the uniformly convex object function, and [3] proved that if thepoints given by these algorithms are convergent they are globall…     

一类带非精确线搜索的修改的Broyden算法

对于文（８）和（１４）中提出的修改的Ｂｒｏｙｄｅｎ算法，本文讨论它在线搜索非精确时的收敛性质，证明这类算法作用于梯度满足Ｌｉｐｓｃｈｉｔｚ条件的目标函数时是整体收敛的，当目标函数一致凸时，算法是Ｑ－超线性收敛和二阶收敛的。     

Convergence of FBP algorithm for tomography

Filter back-projection (FBP) algorithms are available and extensively used methods for tomography. In this paper, we prove the convergence of FBP algorithms at any continuous point of image function, in L ²-norm and L ¹-norm under the certain assumptions of image and window functions of FBP algorithms.     

Regret bounds for Narendra-Shapiro bandit algorithms

Narendra-Shapiro (NS) algorithms are bandit-type algorithms developed in the 1960s. NS-algorithms have been deeply studied in infinite horizon but little non-asymptotic results exist for this type of bandit algorithms. In this paper, we focus on a non-asymptotic study of the regret and address the following question: are Narendra-Shapiro bandit algorithms competitive from this point of view? In our main result, we obtain some uniform explicit bounds for the regret of (over)-penalized-NS algorithms. We also extend to the multi-armed case some convergence properties of penalized-NS algorithms towards a stationary Piecewise Deterministic Markov Process (PDMP). Finally, we establish some new sharp mixing bounds for these processes.     

Numerical experiments on dual matrix algorithms for function minimization

In Ref. 2, four algorithms of dual matrices for function minimization were introduced. These algorithms are characterized by the simultaneous use of two matrices and by the property that the one-dimensional search for the optimal stepsize is not needed for convergence. For a quadratic function, these algorithms lead to the solution in at mostn+1 iterations, wheren is the number of variables in the function. Since the one-dimensional search is not needed, the total number of gradient evaluations for convergence is at mostn+2. In this paper, the above-mentioned algorithms are tested numerically by using five nonquadratic functions. In order to investigate the effects of the stepsize on the performances of these algorithms, four schemes for the stepsize factor are employed, two corresponding to small-step processes and two corresponding to large-step processes. The numerical results show that, in spite of the wide range employed in the choice of the stepsize factor, all algorithms exhibit satisfactory convergence properties and compare favorably with the corresponding quadratically convergent algorithms using one-dimensional searches for optimal stepsizes.     

Weak and strong convergence theorems for variational inequality problems

In this paper, we study the weak and strong convergence of two algorithms for solving Lipschitz continuous and monotone variational inequalities. The algorithms are inspired by Tseng’s extragradient method and the viscosity method with Armijo-like step size rule. The main advantages of our algorithms are that the construction of solution approximations and the proof of convergence of the algorithms are performed without the prior knowledge of the Lipschitz constant of cost operators. Finally, we provide numerical experiments to show the efficiency and advantage of the proposed algorithms.     

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.      

On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form

In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way, the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity. First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k × k (already reduced) sub-block will have the Lanczos–Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior a special type of subspace iteration is performed on the lower right k × k submatrix, which contains these Ritz-values. Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.     

Golden ratio algorithms with new stepsize rules for variational inequalities

In this paper, we introduce two golden ratio algorithms with new stepsize rules for solving pseudomonotone and Lipschitz variational inequalities in finite dimensional Hilbert spaces. The presented stepsize rules allow the resulting algorithms to work without the prior knowledge of the Lipschitz constant of operator. The first algorithm uses a sequence of stepsizes that is previously chosen, diminishing, and nonsummable, while the stepsizes in the second one are updated at each iteration and by a simple computation. A special point is that the sequence of stepsizes generated by the second algorithm is separated from zero. The convergence and the convergence rate of the proposed algorithms are established under some standard conditions. Also, we give several numerical results to show the behavior of the algorithms in comparison with other algorithms.     

Variable metric quasi-Fejér monotonicity

The notion of quasi-Fejér monotonicity has proven to be an efficient tool to simplify and unify the convergence analysis of various algorithms arising in applied nonlinear analysis. In this paper, we extend this notion in the context of variable metric algorithms, whereby the underlying norm is allowed to vary at each iteration. Applications to convex optimization and inverse problems are demonstrated.     

Modified extragradient algorithms for solving equilibrium problems

ABSTRACT

In this paper, we introduce some new algorithms for solving the equilibrium problem in a Hilbert space which are constructed around the proximal-like mapping and inertial effect. Also, some convergence theorems of the algorithms are established under mild conditions. Finally, several experiments are performed to show the computational efficiency and the advantage of the proposed algorithm over other well-known algorithms.     

On a class of iterative projection and contraction methods for linear programming

In this paper, based on the idea of a projection and contraction method for a class of linear complementarity problems (Refs. 1 and 2), we develop a class of iterative algorithms for linear programming with linear speed of convergence. The algorithms are used to solve transportation and network problems with up to 10,000 variables. Our experiments indicate that the algorithms are simple, easy to parallelize, and more efficient for some large practical problems.This research was done while the author was visiting the Department of Mathematics at the University of Würzburg, Würzburg, Germany.     

Convergence of the multilevel Full Approximation Scheme including theV-cycle

Summary The multilevel Full Approximation Scheme (FAS ML) is a well-known solver for nonlinear boundary value problems. In this paper we prove local quantitative convergence statements for a class of FAS ML algorithms in a general Hilbertspace setting. This setting clearly exhibits the structure of FAS ML. We prove local convergence of a nested iteration for a rather concrete class of FAS ML algorithms in whichV-cycles and only one Jacobilike pre- and post-smoothing on each level are used.     

Algorithms for solving nonlinear dynamic decision models

In this paper we discuss two Newton-type algorithms for solving economic models. The models are preprocessed by reordering the equations in order to minimize the dimension of the simultaneous block. The solution algorithms are then applied to this block. The algorithms evaluate numerically, as required, selected columns of the Jacobian of the simultaneous part. Provisions also exist for similar systems to be solved, if possible, without actually reinitialising the Jacobian. One of the algorithms also uses the Broyden update to improve the Jacobian. Global convergence is maintained by an Armijo-type stepsize strategy.The global and local convergence of the quasi-Newton algorithm is discussed. A novel result is established for convergence under relaxed descent directions and relating the achievement of unit stepsizes to the accuracy of the Jacobian approximation. Furthermore, a simple derivation of the Dennis-Moré characterisation of the Q-superlinear convergence rate is given.The model equation reordering algorithm is also described. The model is reordered to define heart and loop variables. This is also applied recursively to the subgraph formed by the loop variables to reduce the total number of above diagonal elements in the Jacobian of the complete system. The extension of the solution algorithms to consistent expectations are discussed. The algorithms are compared with Gauss-Seidel SOR algorithms using the USA and Spanish models of the OECD Interlink system.