A Douglas–Rachford splitting method for solving equilibrium problems

We propose a splitting method for solving equilibrium problems involving the sum of two bifunctions satisfying standard conditions. We prove that this problem is equivalent to find a zero of the sum of two appropriate maximally monotone operators under a suitable qualification condition. Our algorithm is a consequence of the Douglas–Rachford splitting applied to this auxiliary monotone inclusion. Connections between monotone inclusions and equilibrium problems are studied.     

A new shrinking gradient-like projection method for equilibrium problems

The paper proposes a new shrinking gradient-like projection method for solving equilibrium problems. The algorithm combines the generalized gradient-like projection method with the monotone hybrid method. Only one optimization program is solved onto the feasible set at each iteration in our algorithm without any extra-step dealing with the feasible set. The absence of an optimization problem in the algorithm is explained by constructing slightly different cutting-halfspace in the monotone hybrid method. Theorem of strong convergence is established under standard assumptions imposed on equilibrium bifunctions. An application of the proposed algorithm to multivalued variational inequality problems (MVIP) is presented. Finally, another algorithm is introduced for MVIPs in which we only use a value of main operator at the current approximation to construct the next approximation. Some preliminary numerical experiments are implemented to illustrate the convergence and computational performance of our algorithms over others.     

A splitting algorithm for a class of bilevel equilibrium problems involving nonexpansive mappings

We propose splitting, parallel algorithms for solving strongly equilibrium problems over the intersection of a finite number of closed convex sets given as the fixed-point sets of nonexpansive mappings in real Hilbert spaces. The algorithm is a combination between the gradient method and the Mann-Krasnosel’skii iterative scheme, where the projection can be computed onto each set separately rather than onto their intersection. Strong convergence is proved. Some special cases involving bilevel equilibrium problems with inverse strongly monotone variational inequality, monotone equilibrium constraints and maximal monotone inclusions are discussed. An illustrative example involving a system of integral equations is presented.     

New subgradient extragradient methods for solving monotone bilevel equilibrium problems

ABSTRACT

In this paper, we propose new subgradient extragradient methods for finding a solution of a strongly monotone equilibrium problem over the solution set of another monotone equilibrium problem which usually is called monotone bilevel equilibrium problem in Hilbert spaces. The first proposed algorithm is based on the subgradient extragradient method presented by Censor et al. [Censor Y, Gibali A, Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. J Optim Theory Appl. 2011;148:318–335]. The strong convergence of the algorithm is established under monotone assumptions of the cost bifunctions with Lipschitz-type continuous conditions recently presented by Mastroeni in the auxiliary problem principle. We also present a modification of the algorithm for solving an equilibrium problem, where the constraint domain is the common solution set of another equilibrium problem and a fixed point problem. Several fundamental experiments are provided to illustrate the numerical behaviour of the algorithms and to compare with others.     

An algorithm for a bilevel problem with equilibrium and fixed point constraints

We prove the solution existence and propose an iterative algorithm for solving equilibrium problems over the common solutions of a monotone equilibrium problem and the fixed points of a strictly pseudocontractive mapping in Hilbert spaces. The algorithm is a combination of the proximal point and Halpern methods. Strong convergence is established.     

Regularization Algorithms for Solving Monotone Ky Fan Inequalities with Application to a Nash-Cournot Equilibrium Model

We make use of the Banach contraction mapping principle to prove the linear convergence of a regularization algorithm for strongly monotone Ky Fan inequalities that satisfy a Lipschitz-type condition recently introduced by Mastroeni. We then modify the proposed algorithm to obtain a line search-free algorithm which does not require the Lipschitz-type condition. We apply the proposed algorithms to implement inexact proximal methods for solving monotone (not necessarily strongly monotone) Ky Fan inequalities. Applications to variational inequality and complementarity problems are discussed. As a consequence, a linearly convergent derivative-free algorithm without line search for strongly monotone nonlinear complementarity problem is obtained. Application to a Nash-Cournot equilibrium model is discussed and some preliminary computational results are reported.     

The primal douglas-rachford splitting algorithm for a class of monotone mappings with application to the traffic equilibrium problem

We apply the Douglas-Rachford splitting algorithm to a class of multi-valued equations consisting of the sum of two monotone mappings. Compared with the dual application of the same algorithm, which is known as the alternating direction method of multipliers, the primal application yields algorithms that seem somewhat involved. However, the resulting algorithms may be applied effectively to problems with certain special structure. In particular we show that they can be used to derive decomposition algorithms for solving the variational inequality formulation of the traffic equilibrium problem. This research was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

求解非线性单调方程组的一种无导数投影算法

推广了一种修正的CG_DESCENT共轭梯度方法,并建立了一种有效求解非线性单调方程组问题的无导数投影算法.在适当的线搜索条件下,证明了算法的全局收敛性.由于新算法不需要借助任何导数信息,故它适应于求解大规模非光滑的非线性单调方程组问题.大量的数值试验表明,新算法对给定的测试问题是有效的.     

Inexact non-interior continuation method for solving large-scale monotone SDCP

For exact Newton method for solving monotone semidefinite complementarity problems (SDCP), one needs to exactly solve a linear system of equations at each iteration. For problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a new inexact smoothing/continuation algorithm for solution of large-scale monotone SDCP. At each iteration the corresponding linear system of equations is solved only approximately. Under mild assumptions, the algorithm is shown to be both globally and superlinearly convergent.     

Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search

In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally complementary solution to the monotone SCCP under some assumptions. This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200)     

A block monotone domain decomposition algorithm for a semilinear convection–diffusion problem

This paper deals with discrete monotone iterative algorithms for solving a nonlinear singularly perturbed convection–diffusion problem. A block monotone domain decomposition algorithm based on a Schwarz alternating method and on block iterative scheme is constructed. This monotone algorithm solves only linear discrete systems at each iterative step of the iterative process and converges monotonically to the exact solution of the nonlinear problem. The rate of convergence of the block monotone domain decomposition algorithm is estimated. Numerical experiments are presented.     

An LQP-based descent method for structured monotone variational inequalities

This paper proposes a descent method to solve a class of structured monotone variational inequalities. The descent directions are constructed from the iterates generated by a prediction-correction method [B.S. He, Y. Xu, X.M. Yuan, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Comput. Optim. Appl. 35 (2006) 19-46], which is based on the logarithmic-quadratic proximal method. In addition, the optimal step-sizes along these descent directions are identified to accelerate the convergence of the new method. Finally, some numerical results for solving traffic equilibrium problems are reported.     

Partial inverse of a monotone operator

ForT a maximal monotone operator on a Hilbert spaceH andA a closed subspace ofH, the “partial inverse”T _A ofT with respect toA is introduced.T _A is maximal monotone. The proximal point algorithm, as it applies toT _A , results in a simple procedure, the “method of partial inverses”, for solving problems in which the object is to findx ∈ A andy ∈ A ^⊥ such thaty ∈ T(x). This method specializes to give new algorithms for solving numerous optimization and equilibrium problems.     

New Alternating Direction Method for a Class of Nonlinear Variational Inequality Problems

The alternating direction method is an attractive method for a class of variational inequality problems if the subproblems can be solved efficiently. However, solving the subproblems exactly is expensive even when the subproblem is strongly monotone or linear. To overcome this disadvantage, this paper develops a new alternating direction method for cocoercive nonlinear variational inequality problems. To illustrate the performance of this approach, we implement it for traffic assignment problems with fixed demand and for large-scale spatial price equilibrium problems.     

一般单调变分不等式的一个改进的预估-校正算法

最近何炳生等提出了解大规模单调变分不等式的一种预估-校正算法,然而,这个方法在计算每一个试验点时需要一次投影运算,因而计算量较大．为了克服这个缺点,我们提出了一个解一般大规模g-单调变分不等式的新的预估-校正算法,该方法使用了一个非常有效的预估步长准则,每个步长的选取只需要计算一次投影,这将大大减少计算量．数值试验说明我们的算法比最新文献中出现的投影类方法有效．     

Split common fixed point and common null point problem

In this paper, we present a new algorithm for solving the split common null point and common fixed point problem, to find a point that belongs to the common element of common zero points of an infinite family of maximal monotone operators and common fixed points of an infinite family of demicontractive mappings such that its image under a linear transformation belongs to the common zero points of another infinite family of maximal monotone operators and its image under another linear transformation belongs to the common fixed point of another infinite family of demicontractive mappings in the image space. We establish strong convergence for the algorithm to find a unique solution of the variational inequality, which is the optimality condition for the minimization problem. As special cases, we shall use our results to study the split equilibrium problems and the split optimization problems.     

A descent algorithm for solving monotone variational inequalities and monotone complementarity problems

The paper provides a descent algorithm for solving certain monotone variational inequalities and shows how this algorithm may be used for solving certain monotone complementarity problems. Convergence is proved under natural monotonicity and smoothness conditions; neither symmetry nor strict monotonicity is required.The author is grateful to two anonymous referees for their very valuable comments on an earlier draft of this paper.     

Outer Approximation Method for Constrained Composite Fixed Point Problems Involving Lipschitz Pseudo Contractive Operators

We propose a method for solving constrained fixed point problems involving compositions of Lipschitz pseudo contractive and firmly nonexpansive operators in Hilbert spaces. Each iteration of the method uses separate evaluations of these operators and an outer approximation given by the projection onto a closed half-space containing the constraint set. Its convergence is established and applications to monotone inclusion splitting and constrained equilibrium problems are demonstrated.     

Shooting method for solving equilibrium programming problems

A new iterative method is proposed for solving equilibrium programming problems. The sequence of points it generates is proved to converge weakly to the solution set of the equilibrium problem under study. If the initial point has at least one projection onto the solution set of the equilibrium problem, the sequence generated by the method is shown to converge strongly to the set of these projections. The partial gradient of the initial data is assumed to be invertible and strictly monotone, which differs from the classical skew-symmetry condition.     

Iterative Algorithm for Solving Triple-Hierarchical Constrained Optimization Problem

Many practical problems such as signal processing and network resource allocation are formulated as the monotone variational inequality over the fixed point set of a nonexpansive mapping, and iterative algorithms to solve these problems have been proposed. This paper discusses a monotone variational inequality with variational inequality constraint over the fixed point set of a nonexpansive mapping, which is called the triple-hierarchical constrained optimization problem, and presents an iterative algorithm for solving it. Strong convergence of the algorithm to the unique solution of the problem is guaranteed under certain assumptions.