PPA BASED PREDICTION-CORRECTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

In this paper we study the proximal point algorithm (PPA) based prediction-correction (PC) methods for monotone variational inequalities. Each iteration of these methods consists of a prediction and a correction. The predictors are produced by inexact PPA steps. The new iterates are then updated by a correction using the PPA formula. We present two profit functions which serve two purposes: First we show that the profit functions are tight lower bounds of the improvements obtained in each iteration. Based on this conclusion we obtain the convergence inexactness restrictions for the prediction step. Second we show that the profit functions are quadratically dependent upon the step lengths, thus the optimal step lengths are obtained in the correction step. In the last part of the paper we compare the strengths of different methods based on their inexactness restrictions.     

Prediction-correction method with BB step sizes

In the prediction-correction method for variational inequality (VI) problems, the step size selection plays an important role for its performance. In this paper, we employ the Barzilai-Borwein (BB) strategy in the prediction step, which is efficient for many optimization problems from a computational point of view. To guarantee the convergence, we adopt the line search technique, and relax the conditions to accept the BB step sizes as large as possible. In the correction step, we utilize a longer step length to calculate the next iteration point. Finally, we present some preliminary numerical results to show the efficiency of the algorithms.     

A COMPARISON OF DIFFERENT CONTRACTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

It is interesting to compare the efficiency of two methods when their computational loads in each iteration are equal. In this paper, two classes of contraction methods for monotone variational inequalities are studied in a unified framework. The methods of both classes can be viewed as prediction-correction methods, which generate the same test vector in the prediction step and adopt the same step-size rule in the correction step. The only difference is that they use different search directions. The computational loads of each iteration of the different classes are equal. Our analysis explains theoretically why one class of the contraction methods usually outperforms the other class. It is demonstrated that many known methods belong to these two classes of methods. Finally, the presented numerical results demonstrate the validity of our analysis.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

一类凸优化的混合下降算法

邻近点算法(PPA)是一类求解凸优化问题的经典算法, 但往往需要精确求解隐式子问题,于是近似邻近点算法(APPA)在满足一定的近似规则下非精确求解PPA的子问题, 降低了求解难度. 本文利用近似规则的历史信息和随机数扩张预测校正步产生了两个方向, 通过随机数组合两个方向获得了一类凸优化的混合下降算法.在近似规则满足的情况下, 给出了混合下降算法的收敛性证明. 一系列的数值试验表明了混合下降算法的有效性和效率性.     

Prediction-correction alternating direction method for a class of constrained min-max problems

The problems concerned in this paper are a class of constrained min-max problems. By introducing the Lagrange multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. However, to obtain components of the predictor one by one, we use an alternating direction method. And then the new iterate is generated by a minor correction. Global convergence of the proposed method is proved. Finally, numerical results for a constrained single-facility location problem are provided to verify that the new method is effective for some practical problems.      

半定规划问题的一种新的预测-校正算法

本文首先将半定规划转化为一个变分不等式问题,在满足单调性和Lipschitz连续的条件下,提出了一种基于Korpelevich-Khobotv算法的新的预测-校正算法,并给出算法的收敛性分析.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

Numerical Integration of Reaction–Diffusion Systems

Approximating numerically the solutions of a reaction–diffusion system in an efficient manner requires the application of implicit methods, since the Courant–Friedrichs–Lewy condition on explicit methods imposes a time step of the order of the square of the space step. In this article, we review two types of strategies which are expected to yield reasonably precise solutions within a reasonable computing time. The first examines methods for solving the linear step necessary in any resolution procedure; estimates of CPU time in terms of the error are given in the non preconditioned and in the preconditioned case – provided that it is possible to define an efficient preconditioner. The second strategy is based on splitting, with or without extrapolation. The respective faults and qualities of both strategies are examined; they lead to a list of difficult analytical and numerical problems with possible hints as to their solution.     

一类隐式的k+1阶线性k步法

本文首先给出了一类比Adams-Moulton方法的绝对稳定区间大的隐式k+1阶线性k步法基本公式.求出了3-9步新公式的分数形式的精确系数,阶数,局部截断误差主项系数和绝对稳定区间,然后构造了由4阶隐式新公式和同阶显式Nyström公式组合而成的预估-校正方法,比著名的Adams-Bashforth-Moulton和Nyström-Adams-Moulton预估校正方法的绝对稳定区间大,最后用对比数值试验对结果进行了验证.