An algorithm for a class of nonlinear complementarity problems with non-Lipschitzian functions

In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective.     

均衡及约束凸优化问题公共解的一般迭代算法

梯度投影法在解决约束凸极小化问题中起到了重要的作用. 基于Tian的一般迭代算法, 本文将梯度投影法和平均算子方法相结合, 首次提出隐式和显式的复合迭代算法, 寻求均衡问题和约束凸极小化问题的公共解. 在适当条件下, 获得了强收敛定理.     

A Hybrid of the Newton-GMRES and Electromagnetic Meta-Heuristic Methods for Solving Systems of Nonlinear Equations

Solving systems of nonlinear equations is perhaps one of the most difficult problems in all numerical computation. Although numerous methods have been developed to attack this class of numerical problems, one of the simplest and oldest methods, Newton’s method is arguably the most commonly used. As is well known, the convergence and performance characteristics of Newton’s method can be highly sensitive to the initial guess of the solution supplied to the method. In this paper a hybrid scheme is proposed, in which the Electromagnetic Meta-Heuristic method (EM) is used to supply a good initial guess of the solution to the finite difference version of the Newton-GMRES method (NG) for solving a system of nonlinear equations. Numerical examples are given in order to compare the performance of the hybrid of the EM and NG methods. Empirical results show that the proposed method is an efficient approach for solving systems of nonlinear equations.     

A high‐order finite difference method for 1D nonhomogeneous heat equations

In this article a sixth‐order approximation method (in both temporal and spatial variables) for solving nonhomogeneous heat equations is proposed. We first develop a sixth‐order finite difference approximation scheme for a two‐point boundary value problem, and then heat equation is approximated by a system of ODEs defined on spatial grid points. The ODE system is discretized to a Sylvester matrix equation via boundary value method. The obtained algebraic system is solved by a modified Bartels‐Stewart method. The proposed approach is unconditionally stable. Numerical results are provided to illustrate the accuracy and efficiency of our approximation method along with comparisons with those generated by the standard second‐order Crank‐Nicolson scheme as well as Sun‐Zhang's recent fourth‐order method. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

General iterative methods for equilibrium and constrained convex minimization problem

The gradient-projection algorithm (GPA) plays an important role in solving constrained convex minimization problems. Based on Marino and Xu's method [G. Marino and H.-K. Xu, A general method for nonexpansive mappings in Hilbert space, J. Math. Anal. Appl. 318 (2006), pp. 43–52], we combine GPA and averaged mapping approach to propose implicit and explicit composite iterative algorithms for finding a common solution of an equilibrium and a constrained convex minimization problem for the first time in this article. Under suitable conditions, strong convergence theorems are obtained.     

Numerical solution of nonlinear partial quadratic integro‐differential equations of fractional order via hybrid of block‐pulse and parabolic functions

In this paper, an effective numerical approach based on a new two‐dimensional hybrid of parabolic and block‐pulse functions (2D‐PBPFs) is presented for solving nonlinear partial quadratic integro‐differential equations of fractional order. Our approach is based on 2D‐PBPFs operational matrix method together with the fractional integral operator, described in the Riemann–Liouville sense. The main characteristic behind this approach is to reduce such problems to those of solving systems of algebraic equations, which greatly simplifies the problem. By using Newton's iterative method, this system is solved, and the solution of fractional nonlinear partial quadratic integro‐differential equations is achieved. Convergence analysis and an error estimate associated with the proposed method is obtained, and it is proved that the numerical convergence order of the suggested numerical method is O(h³) . The validity and applicability of the method are demonstrated by solving three numerical examples. Numerical examples are presented in the form of tables and graphs to make comparisons with the exact solutions much easier.     

A numerical scheme based on Bernoulli wavelets and collocation method for solving fractional partial differential equations with Dirichlet boundary conditions

In this paper, an efficient and accurate numerical method is presented for solving two types of fractional partial differential equations. The fractional derivative is described in the Caputo sense. Our approach is based on Bernoulli wavelets collocation techniques together with the fractional integral operator, described in the Riemann‐Liouville sense. The main characteristic behind this approach is to reduce such problems to those of solving systems of algebraic equations, which greatly simplifies the problem. By using Newton's iterative method, this system is solved and the solution of fractional partial differential equations is achieved. Some results concerning the error analysis are obtained. The validity and applicability of the method are demonstrated by solving four numerical examples. Numerical examples are presented in the form of tables and graphs to make comparisons with the results obtained by other methods and with the exact solutions much easier.     

Algorithms for vector field generation in mass consistent models

Diagnostic models in meteorology are based on the fulfillment of some time independent physical constraints as, for instance, mass conservation. A successful method to generate an adjusted wind field, based on mass conservation equation, was proposed by Sasaki and leads to the solution of an elliptic problem for the multiplier. Here we study the problem of generating an adjusted wind field from given horizontal initial velocity data, by two ways. The first one is based on orthogonal projection in Hilbert spaces and leads to the same elliptic problem but with natural boundary conditions for the multiplier. We derive from this approach the so called E–algorithm. An innovative alternative proposal is obtained from a second approach where we consider the saddle–point formulation of the problem—avoiding boundary conditions for the multiplier— and solving this problem by iterative conjugate gradient methods. This leads to an algorithm that we call the CG–algorithm, which is inspired from Glowinsk's approach to solve Stokes–like problems in computational fluid dynamics. Finally, the introduction of new boundary conditions for the multiplier in the elliptic problem generates better adjusted fields than those obtained with the original boundary conditions. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Newton’s method as applied to the Riemann problem for media with general equations of state

An approach based on Newton’s method is proposed for solving the Riemann problem for media with normal equations of state. The Riemann integrals are evaluated using a cubic approximation of an isentropic curve that is superior to the Simpson method in terms of accuracy, convergence rate, and efficiency. The potentials of the approach are demonstrated by solving problems for media obeying the Mie-Grüneisen equation of state. The algebraic equation of the isentropic curve and some exact solutions for configurations with rarefaction waves are explicitly given.     

Uniformly convergent novel finite difference methods for singularly perturbed reaction–diffusion equations

In this paper, we construct a kind of novel finite difference (NFD) method for solving singularly perturbed reaction–diffusion problems. Different from directly truncating the high‐order derivative terms of the Taylor's series in the traditional finite difference method, we rearrange the Taylor's expansion in a more elaborate way based on the original equation to develop the NFD scheme for 1D problems. It is proved that this approach not only can highly improve the calculation accuracy but also is uniformly convergent. Then, applying alternating direction implicit technique, the newly deduced schemes are extended to 2D equations, and the uniform error estimation based on Shishkin mesh is derived, too. Finally, numerical experiments are presented to verify the high computational accuracy and theoretical prediction.     

Construction and validation of distribution-based regression simulation metamodels

Metamodels are used as analysis tools for solving optimization problems. A metamodel is a simplification of the simulation model, representing the system's input–output relationship through a mathematical function with customized parameters. The proposed approach uses confidence intervals as an acceptance procedure, and as a predictive validation procedure when new points are employed. To improve the knowledge about the system, the response is depicted by modelling both the mean and variance functions of a normal distribution along the experimental region. Such metamodels are specially useful when the variance of the output varies significantly. These metamodels may be used for minimizing product quality loss and improving production robustness. The development of such metamodels is illustrated with two examples.     

Spectral graph wavelet optimized finite difference method for solution of Burger's equation with different boundary conditions

In this paper, spectral graph wavelet optimized finite difference method (SPGWOFD) has been proposed for solving Burger's equation with distinct boundary conditions. Central finite difference approach is utilized for the approximations of the differential operators and the grid on which the numerical solution is obtained is chosen with the help of spectral graph wavelet. Four test problems (with Dirichlet, Periodic, Robin and Neumann's boundary conditions) are considered and the convergence of the technique is checked. For assessing the efficiency of the developed technique, the computational time taken by the developed technique is compared to that of the finite difference method. It has been observed that developed technique is extremely efficient.     

Linear models for the approximate solution of the problem of packing equal circles into a given domain

The linear models for the approximate solution of the problem of packing the maximum number of equal circles of the given radius into a given closed bounded domain G are proposed. We construct a grid in G; the nodes of this grid form a finite set of points T, and it is assumed that the centers of circles to be packed can be placed only at the points of T. The packing problems of equal circles with the centers at the points of T are reduced to 0–1 linear programming problems. A heuristic algorithm for solving the packing problems based on linear models is proposed. This algorithm makes it possible to solve packing problems for arbitrary connected closed bounded domains independently of their shape in a unified manner. Numerical results demonstrating the effectiveness of this approach are presented.     

A new metaheuristic algorithm based on shark smell optimization

In this article, a new metaheuristic optimization algorithm is introduced. This algorithm is based on the ability of shark, as a superior hunter in the nature, for finding prey, which is taken from the smell sense of shark and its movement to the odor source. Various behaviors of shark within the search environment, that is, sea water, are mathematically modeled within the proposed optimization approach. The effectiveness of the suggested approach is compared with many other heuristic optimization methods based on standard benchmark functions. Also, to illustrate the efficiency of the proposed optimization method for solving real‐world engineering problems, it is applied for the solution of load frequency control problem in electrical power systems. The obtained results confirm the validity of the proposed metaheuristic optimization algorithm. © 2014 Wiley Periodicals, Inc. Complexity 21: 97–116, 2016     

A fast numerical method for solving coupled Burgers' equations

A new fast numerical scheme is proposed for solving time‐dependent coupled Burgers' equations. The idea of operator splitting is used to decompose the original problem into nonlinear pure convection subproblems and diffusion subproblems at each time step. Using Taylor's expansion, the nonlinearity in convection subproblems is explicitly treated by resolving a linear convection system with artificial inflow boundary conditions that can be independently solved. A multistep technique is proposed to rescue the possible instability caused by the explicit treatment of the convection system. Meanwhile, the diffusion subproblems are always self‐adjoint and coercive at each time step, and they can be efficiently solved by some existing preconditioned iterative solvers like the preconditioned conjugate galerkin method, and so forth. With the help of finite element discretization, all the major stiffness matrices remain invariant during the time marching process, which makes the present approach extremely fast for the time‐dependent nonlinear problems. Finally, several numerical examples are performed to verify the stability, convergence and performance of the new method.© 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 1823–1838, 2017     

Chebyshev center based column generation

The classical column generation approach often shows a very slow convergence. Many different acceleration techniques have been proposed recently to improve the convergence. Here, we briefly survey these methods and propose a novel algorithm based on the Chebyshev center of the dual polyhedron. The Chebyshev center can be obtained by solving a linear program; consequently, the proposed method can be applied with small modifications on the classical column generation procedure. We also show that the performance of our algorithm can be enhanced by introducing proximity parameters which enable the position of the Chebyshev center to be adjusted. Numerical experiments are conducted on the binpacking, vehicle routing problem with time windows, and the generalized assignment problem. The computational results of these experiments demonstrate the effectiveness of our proposed method.     

A simply constructed third-order modifications of Newton's method

In this paper, we present a simple and easily applicable approach to construct some third-order modifications of Newton's method for solving nonlinear equations. It is shown by way of illustration that existing third-order methods can be employed to construct new third-order iterative methods. The proposed approach is applied to the classical Chebyshev–Halley methods to derive their second-derivative-free variants. Numerical examples are given to support that the methods thus obtained can compete with known third-order methods.     

Clarkson's algorithm for violator spaces

Clarkson's algorithm is a three-staged randomized algorithm for solving linear programs. This algorithm has been simplified and adapted to fit the framework of LP-type problems. In this framework we can tackle a number of non-linear problems such as computing the smallest enclosing ball of a set of points in Rd. In 2006, it has been shown that the algorithm in its original form works for violator spaces too, which are a proper generalization of LP-type problems. It was not clear, however, whether previous simplifications of the algorithm carry over to the new setting.In this paper we show the following theoretical results: (a) It is shown, for the first time, that Clarkson's second stage can be simplified. (b) The previous simplifications of Clarkson's first stage carry over to the violator space setting. (c) The equivalence of violator spaces and partitions of the hypercube by hypercubes.     

求解分布控制问题的预处理最小残量方法(英文)

通过分析Bai(Bai Z Z.Block preconditioners for elliptic PDE-constrained optimization problems.Computing,2011,91:379-395)给出的离散分布控制问题的块反对角预处理线性系统,提出了该问题的一个等价线性系统,并且运用带有预处理子的最小残量方法对该系统进行求解.理论分析和数值实验结果表明,所提出的预处理最小残量方法对于求解该类椭圆型偏微分方程约束最优分布控制问题非常有效,尤其当正则参数适当小的时候.