Some Goldstein's type methods for co-coercive variant variational inequalities

The classical Goldstein's method has been well studied in the context of variational inequalities (VIs). In particular, it has been shown in the literature that the Goldstein's method works well for co-coercive VIs where the underlying mapping is co-coercive. In this paper, we show that the Goldstein's method can be extended to solve co-coercive variant variational inequalities (VVIs). We first show that when the Goldstein's method is applied to solve VVIs, the iterative scheme can be improved by identifying a refined step-size if the involved co-coercive modulus is known. By doing so, the allowable range of the involved scaling parameter ensuring convergence is enlarged compared to that in the context of VVIs with Lipschitz and strongly monotone operators. Then, we show that for such a VVI whose co-coercive modulus is unknown, the Goldstein's method is still convergent provided that an easily-implementable Armijo's type strategy of adjusting the scaling parameter self-adaptively is employed. Some numerical results are reported to verify that the proposed Goldstein's type methods are efficient for solving VVIs.     

A modified projection method with a new direction for solving variational inequalities

In this paper, we propose a new projection method for solving variational inequality problems, which can be viewed as an improvement of the method of Li et al. [M. Li, L.Z. Liao, X.M. Yuan, A modified projection method for co-coercive variational inequality, European Journal of Operational Research 189 (2008) 310-323], by adopting a new direction. Under the same assumptions as those in Li et al. (2008), we establish the global convergence of the proposed algorithm. Some preliminary computational results are reported, which illustrated that the new method is more efficient than the method of Li et al. (2008).     

A CLASS OF TRUST REGION METHODS FOR LINEAR INEQUALITY CONSTRAINED OPTIMIZATION AND ITS THEORY ANALYSIS：Ⅰ. ALGORITHM AND GLOBAL CONVERGENCE

A class of trust region methods tor solving linear inequality constrained problems is propo6ed in this paper. It is shown that the algorithm is of global convergence. The algorithm uses a version of the two-slded projection and the strategy of the unconstrained trust region methods. It keeps the good convergence properties of the unconstrained case and has the merits of the projection method. In some sense, our algorithm can be regarded as an extension and improvement of the projected type algorithm.     

An alternating direction method for general variational inequalities

In this paper, we present an alternating direction method for structured general variational inequalities. This method only needs functional values for given variables in the solution process and does not require the estimate of the co-coercive modulus. All the computing process are easily implemented and the global convergence is also presented under mild assumptions. Some preliminary computational results are given.     

Fixed point solutions of variational inequality and generalized equilibrium problems with applications

In this paper, we introduce a new iterative scheme for finding a common element of the set of fixed points of a nonexpansive mapping, the set of solution of generalized equilibrium problem and the set of solutions of the variational inequality problem for a co-coercive mapping in a real Hilbert space. Then strong convergence of the scheme to a common element of the three sets is proved. Furthermore, new convergence results are deduced and finally we apply our results to solving optimization problems and obtaining zeroes of maximal monotone operators and co-coercive mappings.     

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).     

Local linear convergence of approximate projections onto regularized sets

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.     

Solving cone-constrained convex programs by differential inclusions

A differential inclusion is designed for solving cone-constrained convex programs. The method is of subgradient-projection type. It involves projection, penalties and Lagrangian relaxation. Nonsmooth data can be accommodated. A novelty is that multipliers converge monotonically upwards to equilibrium levels. An application to stochastic programming is considered.Corresponding author.     

Partly convex programming and zermelo's navigation problems

Mathematical programs, that become convex programs after freezing some variables, are termed partly convex. For such programs we give saddle-point conditions that are both necessary and sufficient that a feasible point be globally optimal. The conditions require cooperation of the feasible point tested for optimality, an assumption implied by lower semicontinuity of the feasible set mapping. The characterizations are simplified if certain point-to-set mappings satisfy a sandwich condition.The tools of parametric optimization and basic point-to-set topology are used in formulating both optimality conditions and numerical methods. In particular, we solve a large class of Zermelo's navigation problems and establish global optimality of the numerical solutions.Research partly supported by NSERC of Canada.     

A two-stage prediction–correction method for solving monotone variational inequalities

In this paper, we present a two-stage prediction–correction method for solving monotone variational inequalities. The method generates the two predictors which should satisfy two acceptance criteria. We also enhance the method with an adaptive rule to update prediction step size which makes the method more effective. Under mild assumptions, we prove the convergence of the proposed method. Our proposed method based on projection only needs the function values, so it is practical and the computation load is quite tiny. Some numerical experiments were carried out to validate its efficiency and practicality.     

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC¹${\text{SC}}^1$) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems.     

A parallel projection method for solving generalized linear least-squares problems

Summary A parallel projection algorithm is proposed to solve the generalized linear least-squares problem: find a vector to minimize the 2-norm distance from its image under an affine mapping to a closed convex cone. In each iteration of the algorithm the problem is decomposed into several independent small problems of finding projections onto subspaces, which are simple and can be tackled parallelly. The algorithm can be viewed as a dual version of the algorithm proposed by Han and Lou [8]. For the special problem under consideration, stronger convergence results are established. The algorithm is also related to the block iterative methods of Elfving [6], Dennis and Steihaug [5], and the primal-dual method of Springarn [14].This material is based on work supported in part by the National Science foundation under Grant DMS-8602416 and by the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign     

Convergence Properties of Projection and Contraction Methods for Variational Inequality Problems

In this paper we develop the convergence theory of a general class of projection and contraction algorithms (PC method), where an extended stepsize rule is used, for solving variational inequality (VI) problems. It is shown that, by defining a scaled projection residue, the PC method forces the sequence of the residues to zero. It is also shown that, by defining a projected function, the PC method forces the sequence of projected functions to zero. A consequence of this result is that if the PC method converges to a nondegenerate solution of the VI problem, then after a finite number of iterations, the optimal face is identified. Finally, we study local convergence behavior of the extragradient algorithm for solving the KKT system of the inequality constrained VI problem. \keywords{Variational inequality, Projection and contraction method, Predictor-corrector stepsize, Convergence property.} \amsclass{90C30, 90C33, 65K05.} Accepted 5 September 2000. Online publication 16 January 2001.     

Filled function method for nonlinear equations

Systems of nonlinear equations are ubiquitous in engineering, physics and mechanics, and have myriad applications. Generally, they are very difficult to solve. In this paper, we will present a filled function method to solve nonlinear systems. We will first convert the nonlinear systems into equivalent global optimization problems with the property: x^∗ is a global minimizer if and only if its function value is zero. A filled function method is proposed to solve the converted global optimization problem. Numerical examples are presented to illustrate our new techniques.     

Projection algorithms for solving a system of general variational inequalities

In this paper, we introduce and consider a new system of general variational inequalities involving four different operators. Using the projection operator technique, we suggest and analyze some new explicit iterative methods for this system of variational inequalities. We also study the convergence analysis of the new iterative method under certain mild conditions. Since this new system includes the system of variational inequalities involving three operators, variational inequalities and related optimization problems as special cases, results obtained in this paper continue to hold for these problems. Our results can be viewed as a refinement and improvement of the previously known results for variational inequalities.     

A Modified Alternating Direction Method for Variational Inequality Problems

The alternating direction method is an attractive method for solving large-scale variational inequality problems whenever the subproblems can be solved efficiently. However, the subproblems are still variational inequality problems, which are as structurally difficult to solve as the original one. To overcome this disadvantage, in this paper we propose a new alternating direction method for solving a class of nonlinear monotone variational inequality problems. In each iteration the method just makes an orthogonal projection to a simple set and some function evaluations. We report some preliminary computational results to illustrate the efficiency of the method. Accepted 4 May 2001. Online publication 19 October, 2001.     

A modified descent method for co-coercive variational inequalities

This paper presents a modified descent method for solving co-coercive variational inequalities. Incorporating with the techniques of identifying descent directions and optimal step sizes along these directions, the new method improves the efficiencies of some existing projection methods. Some numerical results for an economic equilibrium problem are reported.     

A globally convergent derivative-free method for solving large-scale nonlinear monotone equations

In this paper, we propose two derivative-free iterative methods for solving nonlinear monotone equations, which combines two modified HS methods with the projection method in Solodov and Svaiter (1998) [5]. The proposed methods can be applied to solve nonsmooth equations. They are suitable to large-scale equations due to their lower storage requirement. Under mild conditions, we show that the proposed methods are globally convergent. The reported numerical results show that the methods are efficient.     

Iterative method for fixed point problem, variational inequality and generalized mixed equilibrium problems with applications

In this paper, we introduce a new iterative scheme for finding a common element of the set of fixed points of a nonexpansive mapping, the set of solution of generalized mixed equilibrium problem and the set of solutions of the variational inequality problem for a co-coercive mapping in a real Hilbert space. Then strong convergence of the scheme to a common element of the three sets is proved. Furthermore, new convergence results are deduced and finally we apply our results to solving optimization problems and present other applications.     

On cone of nonsymmetric positive semidefinite matrices

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P₀-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone.