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

Geometrically convergent projection method in matrix games

We propose a method which evaluates the solution of a matrix game. We reduce the problem of the search for the solution to a convex feasibility problem for which we present a method of projection onto an acute cone. The algorithm converges geometrically. At each iteration, we apply a combinatorial algorithm in order to evaluate the projection onto the standard simplex.     

The relaxed inexact projection methods for the split feasibility problem

In this paper we present several relaxed inexact projection methods for the split feasibility problem (SFP). Each iteration of the first proposed algorithm consists of a projection onto a halfspace containing the given closed convex set. The algorithm can be implemented easily and its global convergence to the solution can be established under suitable conditions. Moreover,we present some modifications of the relaxed inexact projection method with constant stepsize by adopting Armijo-like search. We furthermore present a variable-step relaxed inexact projection method which does not require the computation of the matrix inverses and the largest eigenvalue of the matrix A^TA, and the objective function can decrease sufficiently at each iteration. We show convergence of these modified algorithms under mild conditions. Finally, we perform some numerical experiments, which show the behavior of the algorithms proposed.     

A relaxed projection method for variational inequalities

This paper presents a modification of the projection methods for solving variational inequality problems. Each iteration of the proposed algorithm consists of projection onto a halfspace containing the given closed convex set rather than the latter set itself. The algorithm can thus be implemented very easily and its global convergence to the solution can be established under suitable conditions.This work was supported in part by Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

A variable-metric variant of the Karmarkar algorithm for linear programming

The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems. Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-29-83-K-0035, AFOSR 85-0243. Research sponsored by ARO DAAG-29-83-K-0035, AFOSR 85-0243, Shell Development Company.     

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.     

不等式约束优化一个基于滤子思想的广义梯度投影算法

讨论非线性不等式约束优化问题, 借鉴于滤子算法思想,提出了一个新型广义梯度投影算法.该方法既不使用罚函数又无真正意义下的滤子.每次迭代通过一个简单的显式广义投影法产生搜索方向,步长由目标函数值或者约束违反度函数值充分下降的Armijo型线搜索产生.算法的主要特点是: 不需要迭代序列的有界性假设;不需要传统滤子算法所必需的可行恢复阶段;使用了ε积极约束集减小计算量.在合适的假设条件下算法具有全局收敛性, 最后对算法进行了初步的数值实验.     

A Projected Subgradient Algorithm for Bilevel Equilibrium Problems and Applications

In this paper, we propose a new algorithm for solving a bilevel equilibrium problem in a real Hilbert space. In contrast to most other projection-type algorithms, which require to solve subproblems at each iteration, the subgradient method proposed in this paper requires only to calculate, at each iteration, two subgradients of convex functions and one projection onto a convex set. Hence, our algorithm has a low computational cost. We prove a strong convergence theorem for the proposed algorithm and apply it for solving the equilibrium problem over the fixed point set of a nonexpansive mapping. Some numerical experiments and comparisons are given to illustrate our results. Also, an application to Nash–Cournot equilibrium models of a semioligopolistic market is presented.     

The interior proximal extragradient method for solving equilibrium problems

In this article we present a new and efficient method for solving equilibrium problems on polyhedra. The method is based on an interior-quadratic proximal term which replaces the usual quadratic proximal term. This leads to an interior proximal type algorithm. Each iteration consists in a prediction step followed by a correction step as in the extragradient method. In a first algorithm each of these steps is obtained by solving an unconstrained minimization problem, while in a second algorithm the correction step is replaced by an Armijo-backtracking linesearch followed by an hyperplane projection step. We prove that our algorithms are convergent under mild assumptions: pseudomonotonicity for the two algorithms and a Lipschitz property for the first one. Finally we present some numerical experiments to illustrate the behavior of the proposed algorithms.     

A Projection-Proximal Point Algorithm for Solving Generalized Variational Inequalities

In this paper, a projection-proximal point method for solving a class of generalized variational inequalities is considered in Hilbert spaces. We investigate a general iterative algorithm, which consists of an inexact proximal point step followed by a suitable orthogonal projection onto a hyperplane. We prove the convergence of the algorithm for a pseudomonotone mapping with weakly upper semicontinuity and weakly compact and convex values. We also analyze the convergence rate of the iterative sequence under some suitable conditions.     

Remark on the Successive Projection Algorithm for the Multiple-Sets Split Feasibility Problem

Recently, assuming that the metric projection onto a closed convex set is easily calculated, Liu et al. (Numer. Func. Anal. Opt. 35:1459–1466, 2014) presented a successive projection algorithm for solving the multiple-sets split feasibility problem (MSFP). However, in some cases it is impossible or needs too much work to exactly compute the metric projection. The aim of this remark is to give a modification to the successive projection algorithm. That is, we propose a relaxed successive projection algorithm, in which the metric projections onto closed convex sets are replaced by the metric projections onto halfspaces. Clearly, the metric projection onto a halfspace may be directly calculated. So, the relaxed successive projection algorithm is easy to implement. Its theoretical convergence results are also given.     

Modified projection method for solving a system of monotone equations with convex constraints

In this paper, we propose a modified projection method for solving a system of monotone equations with convex constraints. At each iteration of the method, we first solve a system of linear equations approximately, and then perform a projection of the initial point onto the intersection set of the feasible set and two half spaces containing the current iterate to obtain the next one. The iterate sequence generated by the proposed algorithm possesses an expansive property with regard to the initial point. Under mild condition, we show that the proposed algorithm is globally convergent. Preliminary numerical experiments are also reported.     

A finite algorithm for finding the projection of a point onto the canonical simplex of ∝ n

An algorithm of successive location of the solution is developed for the problem of finding the projection of a point onto the canonical simplex in the Euclidean space ⁿ . This algorithm converges in a finite number of steps. Each iteration consists in finding the projection of a point onto an affine subspace and requires only explicit and very simple computations.     

An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.     

非线性不等式约束最优化快速收敛的可行信赖域算法

In this paper,by combining the trust region technique with the generalized gradient projection.a new trust region algorithm with feasible iteration points is presented for nonlinear inequality constrained optimization,and its trust region is a general compact set containing the origion as an inteior point.No penalty function is used in the algorithm,and it is feasible descent .Under suitable assumptions,the algorithm is proved to possess global and strong convergence as well as superlinear and quadratic convergence.Some numerical results are reported.     

ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING＊

In this paper, we consider the solution of the standard linear programming [Lt＇）. A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan [19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan＇s face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.     

MKPLS approach: switching strategies for the non-linear multi-kernel PLSR

We present two strategies to determine the kernel switching order for the non-linear multi-kernel PLSR algorithm. The multi-kernel PLS (MKPLS) algorithm builds upon a one kernel PLSR which uses a kernel matrix to hold the inner products of the projection of the independent data set onto a feature space. After building a PLSR model, MKPLS deflates the kernel matrix so that only that part which cannot be predicted by the model remains. This remainder is projected onto a different feature space and a new PLSR model is built. The switching algorithms presented for this approach address two questions: which kernel should be used at each iteration and; how many factors should be extracted before switching to another kernel.     

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.     

Finding projections onto the intersection of convex sets in Hilbert spaces. II

We present a parallel iterative algorithm to find the shortest distance projection of a given point onto the intersection of a finite number of closed convex sets in a real Hilbert space; the number of sets used at each iteration step, corresponding to the number of available processors, may be smaller than the total number of sets. The relaxation coefficient at each iteraction step is determined by a geometric condition in an associated Hilbert space, while for the weights mild conditions are given to assure norm convergence of the resulting sequence. These mild conditions leave enough flexibility to determine the weights more specifically in order to improve the speed of convergence.     

Inexact-Restoration Algorithm for Constrained Optimization1

We introduce a new model algorithm for solving nonlinear programming problems. No slack variables are introduced for dealing with inequality constraints. Each iteration of the method proceeds in two phases. In the first phase, feasibility of the current iterate is improved; in second phase, the objective function value is reduced in an approximate feasible set. The point that results from the second phase is compared with the current point using a nonsmooth merit function that combines feasibility and optimality. This merit function includes a penalty parameter that changes between consecutive iterations. A suitable updating procedure for this penalty parameter is included by means of which it can be increased or decreased along consecutive iterations. The conditions for feasibility improvement at the first phase and for optimality improvement at the second phase are mild, and large-scale implementation of the resulting method is possible. We prove that, under suitable conditions, which do not include regularity or existence of second derivatives, all the limit points of an infinite sequence generated by the algorithm are feasible, and that a suitable optimality measure can be made as small as desired. The algorithm is implemented and tested against the LANCELOT algorithm using a set of hard-spheres problems.