Accelerated hybrid and shrinking projection methods for variational inequality problems

ABSTRACT

In this paper, we introduce several new extragradient-like approximation methods for solving variational inequalities in Hilbert spaces. Our algorithms are based on Tseng's extragradient method, subgradient extragradient method, inertial method, hybrid projection method and shrinking projection method. Strong convergence theorems are established under appropriate conditions. Our results extend and improve some related results in the literature. In addition, the efficiency of our algorithms is shown through numerical examples which are defined by the hybrid projection methods.     

Hybrid Proximal-Type and Hybrid Shrinking Projection Algorithms for Equilibrium Problems,Maximal Monotone Operators,and Relatively Nonexpansive Mappings

In this article, we introduce two hybrid proximal-type algorithms and two hybrid shrinking projection algorithms by using the hybrid proximal-type method and the hybrid shrinking projection method, respectively, for finding a common element of the set of solutions of an equilibrium problem, the set of fixed points of a relatively nonexpansive mapping, and the set of solutions to the equation 0 ∈ Tx for a maximal monotone operator T defined on a uniformly smooth and uniformly convex Banach space. The strong convergence of the sequences generated by the proposed algorithms is established. Our results improve and generalize several known results in the literature.     

On extragradient-viscosity methods for solving equilibrium and fixed point problems in a Hilbert space

Abstract

In this paper, new numerical algorithms are introduced for finding the solution of a variational inequality problem whose constraint set is the common elements of the set of fixed points of a demicontractive mapping and the set of solutions of an equilibrium problem for a monotone mapping in a real Hilbert space. The strong convergence of the iterates generated by these algorithms is obtained by combining a viscosity approximation method with an extragradient method. First, this is done when the basic iteration comes directly from the extragradient method, under a Lipschitz-type condition on the equilibrium function. Then, it is shown that this rather strong condition can be omitted when an Armijo-backtracking linesearch is incorporated into the extragradient iteration. The particular case of variational inequality problems is also examined.     

Structured Markov Chain Monte Carlo

Abstract

This article introduces a general method for Bayesian computing in richly parameterized models, structured Markov chain Monte Carlo (SMCMC), that is based on a blocked hybrid of the Gibbs sampling and Metropolis—Hastings algorithms. SMCMC speeds algorithm convergence by using the structure that is present in the problem to suggest an appropriate Metropolis—Hastings candidate distribution. Although the approach is easiest to describe for hierarchical normal linear models, we show that its extension to both nonnormal and nonlinear cases is straightforward. After describing the method in detail we compare its performance (in terms of run time and autocorrelation in the samples) to other existing methods, including the single-site updating Gibbs sampler available in the popular BUGS software package. Our results suggest significant improvements in convergence for many problems using SMCMC, as well as broad applicability of the method, including previously intractable hierarchical nonlinear model settings.     

Making Augmented Lagrangian Methods Computer Amenable for Equilibrium Problems

ABSTRACT

We develop three algorithms to solve the subproblems generated by the augmented Lagrangian methods introduced by Iusem-Nasri (2010) for the equilibrium problem. The first algorithm that we propose incorporates the Newton method and the other two are instances of the subgradient projection method. One of our algorithms is also capable of solving nondifferentiable equilibrium problems. Using well-known test problems, all algorithms introduced here are implemented and numerical results are reported to compare their performances.     

Eigenvalues and switching algorithms for Quasi-Newton updates

Two switching algorithms QNSWl and QNSW2 are proposed in this paper. These algorithms are developed based on the eigenvalues of matrices which are inertial to the symmetric rank-one (SR1) updates and the BFGS updates. First, theoretical results on the eigenvalues and condition numbers of these matrices are presented. Second, switch-ing mechanisms are then developed based on theoretical results obtained so that each proposed algorithm has the capability of applying appropriate updating formulae at each iterative point during the whole minimization process. Third, the performance of

each of the proposed algorithms is evaluated over a wide range of test problems with variable dimensions. These results are then compared to the results obtained by some well-known minimization packages. Comparative results show that among the tested methods, the QNSW2 algorithm has the best overall performance for the problems examined. In some cases, the number of iterations and the number function/gradient calls required by certain existing methods are more than a four-fold increase over that required by the proposed switching algorithms     

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.     

Global optimization based on novel heuristics,low-discrepancy sequences and genetic algorithms

In this paper a new heuristic hybrid technique for bound-constrained global optimization is proposed. We developed iterative algorithm called GLP_τS that uses genetic algorithms, LP_τ low-discrepancy sequences of points and heuristic rules to find regions of attraction when searching a global minimum of an objective function. Subsequently Nelder–Mead Simplex local search technique is used to refine the solution. The combination of the three techniques (Genetic algorithms, LP_τO Low-discrepancy search and Simplex search) provides a powerful hybrid heuristic optimization method which is tested on a number of benchmark multimodal functions with 10–150 dimensions, and the method properties – applicability, convergence, consistency and stability are discussed in detail.     

Normal/Independent Distributions and Their Applications in Robust Regression

Abstract

Maximum likelihood estimation with nonnormal error distributions provides one method of robust regression. Certain families of normal/independent distributions are particularly attractive for adaptive, robust regression. This article reviews the properties of normal/independent distributions and presents several new results. A major virtue of these distributions is that they lend themselves to EM algorithms for maximum likelihood estimation. EM algorithms are discussed for least L_p regression and for adaptive, robust regression based on the t, slash, and contaminated normal families. Four concrete examples illustrate the performance of the different methods on real data.     

Inertial methods for fixed point problems and zero point problems of the sum of two monotone mappings

ABSTRACT

The purpose of this paper is to investigate the problem of finding a common element of the set of zero points of the sum of two operators and the fixed point set of a quasi-nonexpansive mapping. We introduce modified forward-backward splitting methods based on the so-called inertial forward-backward splitting algorithm, Mann algorithm and viscosity method. We establish weak and strong convergence theorems for iterative sequences generated by these methods. Our results extend and improve some related results in the literature.     

Almost minimizers of the one-phase free boundary problem

Abstract

We consider almost minimizers to the one-phase energy functional and we prove their optimal Lipschitz regularity and partial regularity of their free boundary. These results were recently obtained by David and Toro, and David, Engelstein, and Toro. Our proofs provide a different method based on a non-infinitesimal notion of viscosity solutions that we introduced.     

Numerical Solution to Hybrid Stochastic Differential Systems

Abstract

In this article numerical methods for solving hybrid stochastic differential systems of Itô-type are developed by piecewise application of numerical methods for SDEs. We prove a convergence result if the corresponding method for SDEs is numerically stable with uniform convergence in the mean square sense. The Euler and Runge–Kutta methods for hybrid stochastic differential equations are specifically described and the order of the error is given for the Euler method. A numerical example is given to illustrate the theory.     

Solving capacitated clustering problems

This paper presents two effective algorithms for clustering n entities into p mutually exclusive and exhaustive groups where the ‘size’ of each group is restricted. As its objective, the clustering model minimizes the sum of distance between each entity and a designated group median. Empirical results using both a primal heuristic and a hybrid heuristic-subgradient method for problems having n ? 100 (i.e. 10 100 binary variables) show that the algorithms locate close to optimal solutions without resorting to tree enumeration. The capacitated clustering model is applied to the problem of sales force territorial design.     

Improving the pressure accuracy in a projection scheme for incompressible fluids with variable viscosity

The incremental projection scheme and its enhanced version, the rotational projection scheme are powerful and commonly used approaches producing efficient numerical algorithms for solving the Navier–Stokes equations. However, the much improved rotational projection scheme cannot be used on models with non-homogeneous viscosity, imposing the use of the less accurate incremental projection. This paper presents a projection method for the Navier–Stokes equations for fluids having variable viscosity, giving a consistent pressure and increased accuracy in pressure when compared to the incremental projection. The accuracy of the method will be illustrated using a manufactured solution.     

The split common fixed point problem for generalized demimetric mappings in two Banach spaces

ABSTRACT

In this paper, we consider the split common fixed point problem for new demimetric mappings in two Banach spaces. Using the hybrid method, we prove a strong convergence theorem for finding a solution of the split common fixed point problem in two Banach spaces. Furthermore, using the shrinking projection method, we obtain another strong convergence theorem for finding a solution of the problem in two Banach spaces. Using these results, we obtain well-known and new strong convergence theorems in Hilbert spaces and Banach spaces.     

Convergence and certain control conditions for hybrid viscosity approximation methods

Very recently, Yao, Chen and Yao [20] proposed a hybrid viscosity approximation method, which combines the viscosity approximation method and the Mann iteration method. Under the convergence of one parameter sequence to zero, they derived a strong convergence theorem in a uniformly smooth Banach space. In this paper, under the convergence of no parameter sequence to zero, we prove the strong convergence of the sequence generated by their method to a fixed point of a nonexpansive mapping, which solves a variational inequality. An appropriate example such that all conditions of this result are satisfied and their condition β_n→0 is not satisfied is provided. Furthermore, we also give a weak convergence theorem for their method involving a nonexpansive mapping in a Hilbert space.     

Deciding finiteness for matrix groups over function fields

LetF be a field andt an indeterminate. In this paper we consider aspects of the problem of deciding if a finitely generated subgroup of GL(n,F(t)) is finite. WhenF is a number field, the analysis may be easily reduced to deciding finiteness for subgroups of GL(n,F), for which the results of [1] can be applied. WhenF is a finite field, the situation is more subtle. In this case our main results are a structure theorem generalizing a theorem of Weil and upper bounds on the size of a finite subgroup generated by a fixed number of generators with examples of constructions almost achieving the bounds. We use these results to then give exponential deterministic algorithms for deciding finiteness as well as some preliminary results towards more efficient randomized algorithms. Supported in part by NSF DMS Awards 9404275 and Presidential Faculty Fellowship.     

Viscosity Approximation Methods for Generalized Multi-Valued Nonexpansive Mappings with Applications

Abstract

In this article, we study viscosity approximation methods for generalized multi-valued nonexpansive mappings and we present some new results related to strong convergence, variational inequality, convex optimization, split and common split feasibility problems (SFPs). Some numerical computations are also presented to illustrate our results.     

An efficient iterative method for finding common fixed point and variational inequalities in Hilbert spaces

ABSTRACT

In this paper, we investigate the problem of finding a common solution to a fixed point problem involving demi-contractive operator and a variational inequality with monotone and Lipschitz continuous mapping in real Hilbert spaces. Inspired by the projection and contraction method and the hybrid descent approximation method, a new and efficient iterative method for solving the problem is introduced. Strong convergence theorem of the proposed method is established under standard and mild conditions. Our scheme generalizes and extends some of the existing results in the literature, and moreover, its computational effort is less per each iteration compared with related works.