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预估校正方法的绝对稳定区间大,最后用对比数值试验对结果进行了验证.     

Comparison of Two Kinds of Prediction-Correction Methods for Monotone Variational Inequalities

In this paper, we study the relationship between the forward-backward splitting method and the extra-gradient method for monotone variational inequalities. Both of the methods can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. Our analysis explains theoretically why the extra-gradient methods usually outperform the forward-backward splitting methods. We suggest some modifications for the two methods and numerical results are given to verify the superiority of the modified methods.     

Self-adaptive projection-based prediction-correction method for constrained variational inequalities

The problems studied in this paper are a class of monotone constrained variational inequalities VI (S, f) in which S is a convex set with some linear constraints. By introducing Lagrangian multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. We focus on the mapping f that does not have an explicit form. Therefore, only its function values can be employed in the numerical methods. The number of iterations is significantly dependent on a parameter that balances the primal and dual variables. To overcome potential difficulties, we present a self-adaptive prediction-correction method that adjusts the scalar parameter automatically. Convergence of the proposed method is proved under mild conditions. Preliminary numerical experiments including some traffic equilibrium problems indicate the effectiveness of the proposed methods.     

Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.     

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

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

A generalized proximal-point-based prediction–correction method for variational inequality problems

In a class of variational inequality problems arising frequently from applications, the underlying mappings have no explicit expression, which make the subproblems involved in most numerical methods for solving them difficult to implement. In this paper, we propose a generalized proximal-point-based prediction–correction method for solving such problems. At each iteration, we first find a prediction point, which only needs several function evaluations; then using the information from the prediction, we update the iteration. Under mild conditions, we prove the global convergence of the method. The preliminary numerical results illustrate the simplicity and effectiveness of the method.     

Singly Diagonally Implicit Runge–Kutta Methods with an Explicit First Stage

The purpose of this paper is to construct methods for solving stiff ODEs, in particular singular perturbation problems. We consider embedded pairs of singly diagonally implicit Runge–Kutta methods with an explicit first stage (ESDIRKs). Stiffly accurate pairs of order 3/2, 4/3 and 5/4 are constructed.     

Modified Implicit–Explicit BDF Methods for Nonlinear Parabolic Equations

Implicit–explicit multistep methods for nonlinear parabolic equations were recently analyzed. If the implicit scheme is one of the backward differentiation formulae (BDF) of order up to six, then the corresponding implicit–explicit method of the same order is stable provided the stability constant is less than a specific scheme-dependent constant. Based on BDF, implicit methods are constructed such that the corresponding implicit–explicit scheme of the same order exhibits improved stability properties.     

On unconditionally positivity preserving DG schemes for shallow water flows with shock capturing by adaptive filtering procedures

In this work, we present an unconditionally positivity preserving implicit time integration scheme for the DG method applied to shallow water flows. For locally refined grids with very small elements, the ODE resulting from space discretization is stiff and requires implicit or partially implicit time stepping. However, for simulations including wetting and drying or regions with small water height, severe time step restrictions have to be imposed due to positivity preservation. Nevertheless, as implicit time stepping demands a significant amount of computational time in order to solve a large system of nonlinear equations for each time step we need large time steps to obtain an efficient scheme. In this context, we propose a novel approach to the strategy of positivity preservation. This new technique is based on the so-called Patankar trick and guarantees non-negativity of the water height for any time step size while still preserving conservativity. Due to this modification, the implicit scheme can take full advantage of larger time steps and is therefore able to beat explicit time stepping in terms of CPU time. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

一类显式的k阶线性k步法基本公式

本文给出了一类比Adams-Bashforth方法的局部截断误差主项系数小和绝对稳定区间大的显式k阶线性k步法基本公式.作者求出了公式的分数形式的精确系数,阶数和局部截断误差主项系数,给出了3-9步公式的绝对稳定区间,构造了由新公式的4阶显式公式和一个同阶隐式基本公式组合而成的特殊预估-校正方法,它的绝对稳定区间大于预估公式而且等于校正公式, 比著名的Adams-Bashforth-Moulton预估校正方法的绝对稳定区间大, 最后用数值试验对结果进行了验证,适合于求解常微分方程初值问题.     

Nonoverlapping domain decomposition and additive splitting up methods for multidimensional parabolic problem

The explicit implicit domain decomposition methods are noniterative types of methods for nonoverlapping domain decomposition but due to the use of the explicit step for the interface prediction, the methods suffer from inaccuracy of the usual explicit scheme. In this article a specific type of first‐ and second‐order splitting up method, of additive type, for the dependent variables is initially considered to solve the two‐ or three‐dimensional parabolic problem over nonoverlapping subdomains. We have also considered the parallel explicit splitting up algorithm to define (predict) the interface boundary conditions with respect to each spatial variable and for each nonoverlapping subdomains. The parallel second‐order splitting up algorithm is then considered to solve the subproblems defined over each subdomain; the correction step will then be considered for the predicted interface nodal points using the most recent solution values over the subdomains. Finally several model problems will be considered to test the efficiency of the presented algorithm. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006