互补问题算法的新进展

互补问题是一类重要的优化问题,在最近３０多年的时间里,人们为求解它而提出了许多算法,该文主要介绍１９９０－１９９７年之间出现的某些新算法,它们大致可归类为：（１）光滑方程法;（２）非光滑方程法;（３）可微无约束优化法;（４）ＧＬＰ投影法;（５）内点法;（６）磨光与非内点连续法,文中对每类算法及相应的收敛性结果做了描述与评论,并列出有关文献。     

On the generation of mono-implicit Runge-Kutta-Nyström methods by mono-implicit Runge-Kutta methods

Mono-implicit Runge-Kutta methods can be used to generate implicit Runge-Kutta-Nyström (IRKN) methods for the numerical solution of systems of second-order differential equations. The paper is concerned with the investigation of the conditions to be fulfilled by the mono-implicit Runge-Kutta (MIRK) method in order to generate a mono-implicit Runge-Kutta-Nyström method (MIRKN) that is P-stable. One of the main theoretical results is the property that MIRK methods (in standard form) cannot generate MIRKN methods (in standard form) of order greater than 4. Many examples of MIRKN methods generated by MIRK methods are presented.     

A semi-lagrangian numerical method for geometric optics type problems

Linear multistep methods (LMMs) are written as irreducible general linear methods (GLMs). A-stable LMMs are shown to be algebraically stable GLMs for strictly positive definite G-matrices. Optimal order error bounds, independent of stiffness, are derived for A-stable methods, without considering one-leg methods (OLMs). As a GLM, the OLM is shown to be the transpose of the LMM. For A-stable methods, the LMM G-matrix is the inverse of the OLM G-matrix. Examples of G-symplectic LMMs are given. AMS subject classification (2000) 65L20     

New higher-order methods for the simultaneous inclusion of polynomial zeros

Higher-order methods for the simultaneous inclusion of complex zeros of algebraic polynomials are presented in parallel (total-step) and serial (single-step) versions. If the multiplicities of each zeros are given in advance, the proposed methods can be extended for multiple zeros using appropriate corrections. These methods are constructed on the basis of the zero-relation of Gargantini’s type, the inclusion isotonicity property and suitable corrections that appear in two-point methods of the fourth order for solving nonlinear equations. It is proved that the order of convergence of the proposed methods is at least six. The computational efficiency of the new methods is very high since the acceleration of convergence order from 3 (basic methods) to 6 (new methods) is attained using only n polynomial evaluations per iteration. Computational efficiency of the considered methods is studied in detail and two numerical examples are given to demonstrate the convergence behavior of the proposed methods.     

Twostep-by-twostep continuous PIRKN-type PC methods for nonstiff IVPs

In this paper, we start with the consideration of direct collocation-based Runge-Kutta-Nyström (RKN) methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of special second-order differential equations y″(t) = f(t, y(t)). At nth step, the continuous output formulas can be used for calculating the step values at (n + 2)th step and the integration processes can be proceeded twostep-by-twostep. In this case, we obtain twostep-by-twostep RKN methods with continuous output formulas (continuous TBTRKN methods). Furthermore, we consider a parallel predictor-corrector (PC) iteration scheme using the continuous TBTRKN methods as corrector methods with predictor methods defined by the continuous output formulas. The resulting twostep-by-twostep parallel-iterated RKN-type PC methods with continuous output formulas (twostep-by-twostep continuous PIRKN-type PC methods or TBTCPIRKN methods) give us a faster integration processes. Numerical comparisons based on the solution of a few widely-used test problems show that the new TBTCPIRKN methods are much more efficient than the well-known PIRKN methods, the famous nonstiff sequential ODEX2, DOP853 codes and comparable with the CPIRKN methods.     

Efficient fourth orderP-stable formulae

In this paper, a family of fourth orderP-stable methods for solving second order initial value problems is considered. When applied to a nonlinear differential system, all the methods in the family give rise to a nonlinear system which may be solved using a modified Newton method. The classical methods of this type involve at least three (new) function evaluations per iteration (that is, they are 3-stage methods) and most involve using complex arithmetic in factorising their iteration matrix. We derive methods which require only two (new) function evaluations per iteration and for which the iteration matrix is a true real perfect square. This implies that real arithmetic will be used and that at most one real matrix must be factorised at each step. Also we consider various computational aspects such as local error estimation and a strategy for changing the step size.     

Twostep-by-twostep PIRK-type PC methods with continuous output formulas

This paper deals with parallel predictor–corrector (PC) iteration methods based on collocation Runge–Kutta (RK) corrector methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of first-order differential equations. At n$n$th step, the continuous output formulas are used not only for predicting the stage values in the PC iteration methods but also for calculating the step values at (n+2)$(n+2)$th step. In this case, the integration processes can be proceeded twostep-by-twostep. The resulting twostep-by-twostep (TBT) parallel-iterated RK-type (PIRK-type) methods with continuous output formulas (twostep-by-twostep PIRKC methods or TBTPIRKC methods) give us a faster integration process. Fixed stepsize applications of these TBTPIRKC methods to a few widely-used test problems reveal that the new PC methods are much more efficient when compared with the well-known parallel-iterated RK methods (PIRK methods), parallel-iterated RK-type PC methods with continuous output formulas (PIRKC methods) and sequential explicit RK codes DOPRI5 and DOP853 available from the literature.     

Efficient sixth order methods for nonlinear oscillation problems

A class of two-step (hybrid) methods is considered for solving pure oscillation second order initial value problems. The nonlinear system, which results on applying methods of this type to a nonlinear differential system, may be solved using a modified Newton iteration scheme. From this class the author has derived methods which are fourth order accurate,P-stable, require only two (new) function evaluations per iteration and have a true real perfect square iteration matrix. Now, we propose an extension to sixth order,P-stable methods which require only three (new) function evaluations per iteration and for which the iteration matrix is a true realperfect cube. This implies that at most one real matrix must be factorised at each step. These methods have been implemented in a new variable step, local error controlling code.     

A One-step Method of Order 10 for y' = f(x, y)

In some situations, especially if one demands the solution ofthe differential equation with a great precision, it is preferableto use high-order methods. The methods considered here are similarto Runge—Kutta methods, but for the second-order equationy'= f(x, y). As for Runge—Kutta methods, the complexityof the order conditions grows rapidly with the order, so thatwe have to solve a non—linear system of 440 algebraicequations to obtain a tenth—order method. We demonstratehow this system can be solved. Finally we give the coefficients(20 decimals) of two methods with small local truncation errors.     

Proximal-like contraction methods for monotone variational inequalities in a unified framework?II: general methods and numerical experiments

Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. In Part I of this paper (He et al. in Proximal-like contraction methods for monotone variational inequalities in a unified framework I: effective quadruplet and primary methods, 2010), we proposed a unified framework consisting of an effective quadruplet and a corresponding accepting rule. Under the framework, various existing APPAs can be grouped in the same class of methods (called primary or elementary methods) which adopt one of the geminate directions in the effective quadruplet and take the unit step size. In this paper, we extend the primary methods by using the same effective quadruplet and the accepting rule. The extended (general) contraction methods need only minor extra even negligible costs in each iteration, whereas having better properties than the primary methods in sense of the distance to the solution set. A set of matrix approximation examples as well as six other groups of numerical experiments are constructed to compare the performance between the primary (elementary) and extended (general) methods. As expected, the numerical results show the efficiency of the extended (general) methods are much better than that of the primary (elementary) ones.     

Coaxing a planar curve to comply

A long-standing problem in computer graphics is to find a planar curve that is shaped the way you want it to be shaped. A selection of various methods for achieving this goal is presented. The focus is on mathematical conditions that we can use to control curves while still allowing the curves some freedom. We start with methods invented by Newton (1643–1727) and Lagrange (1736–1813) and proceed to recent methods that are the subject of current research. We illustrate almost all the methods discussed with diagrams. Three methods of control that are of special interest are interpolation methods, global minimization methods (such as least squares), and (Bézier) control points. We concentrate on the first of these, interpolation methods.     

Analytic continuation of Taylor series and the boundary value problems of some nonlinear ordinary differential equations

We compare and discuss the respective efficiency of three methods (with two variants for each of them), based respectively on Taylor (Maclaurin) series, Padé approximants and conformal mappings, for solving quasi-analytically a two-point boundary value problem of a nonlinear ordinary differential equation (ODE). Six configurations of ODE and boundary conditions are successively considered according to the increasing difficulties that they present. After having indicated that the Taylor series method almost always requires the recourse to analytical continuation procedures to be efficient, we use the complementarity of the two remaining methods (Padé and conformal mapping) to illustrate their respective advantages and limitations. We emphasize the importance of the existence of solutions with movable singularities for the efficiency of the methods, particularly for the so-called Padé-Hankel method. (We show that this latter method is equivalent to pushing a movable pole to infinity.) For each configuration, we determine the singularity distribution (in the complex plane of the independent variable) of the solution sought and show how this distribution controls the efficiency of the two methods. In general the method based on Padé approximants is easy to use and robust but may be awkward in some circumstances whereas the conformal mapping method is a very fine method which should be used when high accuracy is required.     

Two-step-by-two-step PIRK-type PC methods based on Gauss-Legendre collocation points

This paper concerns with parallel predictor-corrector (PC) iteration methods for solving nonstiff initial-value problems (IVPs) for systems of first-order differential equations. The predictor methods are based on Adams-type formulas. The corrector methods are constructed by using coefficients of s-stage collocation Gauss-Legendre Runge-Kutta (RK) methods based on c₁,…,c_s and the 2s-stage collocation RK methods based on c₁,…,c_s,1+c₁,…,1+c_s. At nth integration step, the stage values of the 2s-stage collocation RK methods evaluated at t_n+(1+c₁)h,…,t_n+(1+c_s)h can be used as the stage values of the collocation Gauss-Legendre RK method for (n+2)th integration step. By this way, we obtain the corrector methods in which the integration processes can be proceeded two-step-by-two-step. The resulting parallel PC iteration methods which are called two-step-by-two-step (TBT) parallel-iterated RK-type (PIRK-type) PC methods based on Gauss-Legendre collocation points (two-step-by-two-step PIRKG methods or TBTPIRKG methods) give us a faster integration process. Fixed step size applications of these TBTPIRKG methods to the three widely used test problems reveal that the new parallel PC iteration methods are much more efficient when compared with the well-known parallel-iterated RK methods (PIRK methods) and sequential codes ODEX, DOPRI5 and DOP853 available from the literature.     

By How Much Can Residual Minimization Accelerate the Convergence of Orthogonal Residual Methods?

We capitalize upon the known relationship between pairs of orthogonal and minimal residual methods (or, biorthogonal and quasi-minimal residual methods) in order to estimate how much smaller the residuals or quasi-residuals of the minimizing methods can be compared to those of the corresponding Galerkin or Petrov–Galerkin method. Examples of such pairs are the conjugate gradient (CG) and the conjugate residual (CR) methods, the full orthogonalization method (FOM) and the generalized minimal residual (GMRES) method, the CGNE and BiCG versions of applying CG to the normal equations, as well as the biconjugate gradient (BiCG) and the quasi-minimal residual (QMR) methods. Also the pairs consisting of the (bi)conjugate gradient squared (CGS) and the transpose-free QMR (TFQMR) methods can be added to this list if the residuals at half-steps are included, and further examples can be created easily.The analysis is more generally applicable to the minimal residual (MR) and quasi-minimal residual (QMR) smoothing processes, which are known to provide the transition from the results of the first method of such a pair to those of the second one. By an interpretation of these smoothing processes in coordinate space we deepen the understanding of some of the underlying relationships and introduce a unifying framework for minimal residual and quasi-minimal residual smoothing. This framework includes the general notion of QMR-type methods.     

Robust multicategory support vector machines using difference convex algorithm

The support vector machine (SVM) is one of the most popular classification methods in the machine learning literature. Binary SVM methods have been extensively studied, and have achieved many successes in various disciplines. However, generalization to multicategory SVM (MSVM) methods can be very challenging. Many existing methods estimate k functions for k classes with an explicit sum-to-zero constraint. It was shown recently that such a formulation can be suboptimal. Moreover, many existing MSVMs are not Fisher consistent, or do not take into account the effect of outliers. In this paper, we focus on classification in the angle-based framework, which is free of the explicit sum-to-zero constraint, hence more efficient, and propose two robust MSVM methods using truncated hinge loss functions. We show that our new classifiers can enjoy Fisher consistency, and simultaneously alleviate the impact of outliers to achieve more stable classification performance. To implement our proposed classifiers, we employ the difference convex algorithm for efficient computation. Theoretical and numerical results obtained indicate that for problems with potential outliers, our robust angle-based MSVMs can be very competitive among existing methods.     

Convergence Aspects of Step-Parallel Iteration of Runge-Kutta Methods for Delay Differential Equations

Implicit Runge-Kutta methods are known as highly accurate and stable methods for solving differential equations. However, the iteration technique used to solve implicit Runge-Kutta methods requires a lot of computational efforts. To lessen the computational effort, one can iterate simultaneously at a number of points along the t-axis. In this paper, we extend the PDIRK (Parallel Diagonal Iterated Runge-Kutta) methods to delay differential equations (DDEs). We give the region of convergence and analyze the speed of convergence in three parts for the P-stability region of the Runge-Kutta corrector. It is proved that PDIRK methods to DDEs are efficient, and the diagonal matrix D of the PDIRK methods for DDES can be selected in the same way as for ordinary differential equations (ODEs).     

A family of hybrid conjugate gradient methods for unconstrained optimization

Conjugate gradient methods are an important class of methods for unconstrained optimization, especially for large-scale problems. Recently, they have been much studied. This paper proposes a three-parameter family of hybrid conjugate gradient methods. Two important features of the family are that (i) it can avoid the propensity of small steps, namely, if a small step is generated away from the solution point, the next search direction will be close to the negative gradient direction; and (ii) its descent property and global convergence are likely to be achieved provided that the line search satisfies the Wolfe conditions. Some numerical results with the family are also presented.

     

Application of homotopy-perturbation and variational iteration methods to nonlinear heat transfer and porous media equations

Perturbation methods depend on a small parameter which is difficult to be found for real-life nonlinear problems. To overcome this shortcoming, two new but powerful analytical methods are introduced to solve nonlinear heat transfer problems in this article; one is He's variational iteration method (VIM) and the other is the homotopy-perturbation method (HPM). The VIM is to construct correction functionals using general Lagrange multipliers identified optimally via the variational theory, and the initial approximations can be freely chosen with unknown constants. The HPM deforms a difficult problem into a simple problem which can be easily solved. Nonlinear convective–radiative cooling equation, nonlinear heat equation (porous media equation) and nonlinear heat equation with cubic nonlinearity are used as examples to illustrate the simple solution procedures. Comparison of the applied methods with exact solutions reveals that both methods are tremendously effective.     

A split-step finite difference method for nonparaxial nonlinear Schrödinger equation at critical dimension

The critical nonlinear Schrödinger equation (NLS) is the model equation for propagation of laser beam in bulk Kerr medium. One of the final stages in the derivation of NLS from the nonlinear Helmholtz equation (NLH) is to apply paraxial approximation. However, there is numerical evidence suggesting nonparaxiality prevents singularity formation in the solutions of NLS. Therefore, it is important to develop numerical methods for solving nonparaxial NLS. Split-step methods are widely used for finding numerical solutions of NLS equation. Nevertheless, these methods cannot be applied to nonparaxial NLS directly. In this study, we extend the applicability of split-step methods to nonparaxial NLS by using Padé approximant operators. In particular, split-step Crank-Nicolson (SSCN) method is used in conjunction with Padé approximants to provide examples of numerical solutions of nonparaxial NLS.