An efficient algorithm for finding all solutions of separable systems of nonlinear equations

An efficient algorithm is proposed for finding all solutions of systems of nonlinear equations with separable mappings. This algorithm is based on interval analysis, the dual simplex method, the contraction method, and a special technique which makes the algorithm not require large memory space and not require copying tableaus. By numerical examples, it is shown that the proposed algorithm could find all solutions of a system of 2000 nonlinear equations in acceptable computation time. AMS subject classification (2000)  65H10, 65G10     

LP narrowing: A new strategy for finding all solutions of nonlinear equations

An efficient algorithm is proposed for finding all solutions of systems of n nonlinear equations. This algorithm is based on interval analysis and a new strategy called LP narrowing. In the LP narrowing strategy, boxes (n-dimensional rectangles in the solution domain) containing no solution are excluded, and boxes containing solutions are narrowed so that no solution is lost by using linear programming techniques. Since the LP narrowing is very powerful, all solutions can be found very efficiently. By numerical examples, it is shown that the proposed algorithm could find all solutions of systems of 5000-50,000 nonlinear equations in practical computation time.     

Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.     

求解非线性单调方程组的一种无导数投影算法

推广了一种修正的CG_DESCENT共轭梯度方法,并建立了一种有效求解非线性单调方程组问题的无导数投影算法.在适当的线搜索条件下,证明了算法的全局收敛性.由于新算法不需要借助任何导数信息,故它适应于求解大规模非光滑的非线性单调方程组问题.大量的数值试验表明,新算法对给定的测试问题是有效的.     

Exp-function method for traveling wave solutions of nonlinear evolution equations

In this paper, we apply the exp-function method to construct generalized solitary and periodic solutions of nonlinear evolution equations. The proposed technique is tested on the modified Zakharov-Kuznetsov (ZK) and Zakharov-Kuznetsov-Modified-Equal-Width (ZK-MEW) equations. These equations play a very important role in mathematical physics and engineering sciences. The suggested algorithm is quite efficient and is practically well suited for use in these problems. Numerical results clearly indicate the reliability and efficiency of the proposed exp-function method.     

Parametric continuation of the solitary traveling pulse solution in the reaction-diffusion system using the Newton-Krylov method

The matrix-free Newton-Krylov method that uses the GMRES algorithm (an iterative algorithm for solving systems of linear algebraic equations) is used for the parametric continuation of the solitary traveling pulse solution in a three-component reaction-diffusion system. Using the results of integration on a short time interval, we replace the original system of nonlinear algebraic equations by another system that has more convenient (from the viewpoint of the spectral properties of the GMRES algorithm) Jacobi matrix. The proposed parametric continuation proved to be efficient for large-scale problems, and it made it possible to thoroughly examine the dependence of localized solutions on a parameter of the model.     

Exact solutions of nonlinear evolution equations with variable coefficients using exp-function method

In this paper, we apply the exp-function method to construct generalized solitary and periodic solutions of nonlinear evolution equations with variable coefficients. The proposed technique is tested on the Zakharov-Kuznetsov and (2+1)-dimensional Broer-Kaup equations with variable coefficients. These equations play a very important role in mathematical physics and engineering sciences. The suggested algorithm is quite efficient and is practically well suited for use in these problems. Obtained results clearly indicate the reliability and efficiency of the proposed exp-function method.     

Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm

Several numerical methods for solving nonlinear systems of equations assume that derivative information is available. Furthermore, these approaches usually do not consider the problem of finding all solutions to a nonlinear system. Rather, most methods output a single solution. In this paper, we address the problem of finding all roots of a system of equations. Our method makes use of a biased random-key genetic algorithm (BRKGA). Given a nonlinear system, we construct a corresponding optimization problem, which we solve multiple times, making use of a BRKGA, with areas of repulsion around roots that have already been found. The heuristic makes no use of derivative information. We illustrate the approach on seven nonlinear equations systems with multiple roots from the literature.     

A comprehensive simplex-like algorithm for network optimization and perturbation analysis

The family of network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, and transportation. Although it is long known that these problems can be modeled as linear programs (LP), this is generally not done. Due to the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models, these problems are usually treated by one of over 100 specialized algorithms. This leads to several difficulties. The solution algorithms are not unified and each algorithm uses a different strategy to exploit the special structure of a specific problem. Furthermore, small variations in the problem, such as the introduction of side constraints, destroys the special structure and requires modifying andjor restarting the algorithm. Also, these algorithms obtain solution efficiency at the expense of managerial insight, as the final solutions from these algorithms do not have sufficient information to perform postoptimality analysis.

Another approach is to adapt the simplex to network optimization problems through network simplex. This provides unification of the various problems but maintains all the inefficiencies of simplex, as well as, most of the network inflexibility to handle changes such as side constraints. Even ordinary sensitivity analysis (OSA), long available in the tabular simplex, has been only recently transferred to network simplex.

This paper provides a single unified algorithm for all five network models. The proposed solution algorithm is a variant of the self-dual simplex with a warm start. This algorithm makes available the full power of LP perturbation analysis (PA) extended to handle optimal degeneracy. In contrast to OSA, the proposed PA provides ranges for which the current optimal strategy remains optimal, for simultaneous dependent or independent changes from the nominal values in costs, arc capacities, or suppliesJdemands. The proposed solution algorithm also facilitates incorporation of network structural changes and side constraints. It has the advantage of being computationally practical, easy for managers to understand and use, and provides useful PA information in all cases. Computer implementation issues are discussed and illustrative numerical examples are provided in the Appendix     

Combination of the variational iteration method and numerical algorithms for nonlinear problems

A very simple and efficient local variational iteration method (LVIM), or variational iteration method with local property, for solving problems of nonlinear science is proposed in this paper. The analytical iteration formula of this method is derived first using a general form of first order nonlinear differential equations, followed by straightforward discretization using Chebyshev polynomials and collocation method. The resulting numerical algorithm is very concise and easy to use, only involving highly sparse matrix operations of addition and multiplication, and no inversion of the Jacobian in nonlinear problems. Apart from the simple yet efficient iteration formula, another extraordinary feature of LVIM is that in each local domain, all the collocation nodes participate in the calculation simultaneously, thus each local domain can be regarded as one “node” in calculation through GPU acceleration and parallel processing. For illustration, the proposed algorithm of LVIM is applied to various nonlinear problems including Blasius equations in fluid mechanics, buckled bar equations in solid mechanics, the Chandrasekhar equation in astrophysics, the low-Earth-orbit equation in orbital mechanics, etc. Using the built-in highly optimized ode45 function of MATLAB as a comparison, it is found that the LVIM is not only very accurate, but also much faster by an order of magnitude than ode45 in all the numerical examples, especially when the nonlinear terms are very complicated and difficult to evaluate.     

Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.     

基于非线性相位恢复的X射线相位衬度断层成像算法

对全息测量下的X射线相位衬度断层成像问题提出了一种新的重建算法．该算法的主要想法是利用牛顿迭代法求解非线性的相位恢复问题．我们证明了牛顿方向满足的线性方程是非适定的,并利用共轭梯度法得到方程的正则化解．最后利用模拟数据进行了数值实验,数值结果验证了算法的合理性以及对噪声数据的数值稳定性,同时通过与线性化相位恢复算法的数值结果比较说明了新算法对探测数据不要求限制在Fresnel区域的近场,适用范围更广．     

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.     

A Numerical Study of the Exact Evolution Equations for Surface Waves in Water of Finite Depth

We describe a pseudo-spectral numerical method to solve the systems of one-dimensional evolution equations for free surface waves in a homogeneous layer of an ideal fluid. We use the method to solve a system of one-dimensional integro-differential equations, first proposed by Ovsjannikov and later derived by Dyachenko, Zakharov, and Kuznetsov, to simulate the exact evolution of nonlinear free surface waves governed by the two-dimensional Euler equations. These equations are written in the transformed plane where the free surface is mapped onto a flat surface and do not require the common assumption that the waves have small amplitude used in deriving the weakly nonlinear Korteweg–de Vries and Boussinesq long-wave equations. We compare the solution of the exact reduced equations with these weakly nonlinear long-wave models and with the nonlinear long-wave equations of Su and Gardner that do not assume the waves have small amplitude. The Su and Gardner solutions are in remarkably close agreement with the exact Euler solutions for large amplitude solitary wave interactions while the interactions of low-amplitude solitary waves of all four models agree. The simulations demonstrate that our method is an efficient and accurate approach to integrate all of these equations and conserves the mass, momentum, and energy of the Euler equations over very long simulations.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

带非线性不等式约束优化问题的信赖域算法

借助于KKT条件和NCP函数,提出了求解带非线性不等式约束优化问题的信赖域算法.该算法在每一步迭代时,不必求解带信赖域界的二次规划子问题,仅需求一线性方程组系统.在适当的假设条件下,它还是整体收敛的和局部超线性收敛的.数值实验结果表明该方法是有效的.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

Markov decision processes for infinite horizon problems solved with the cosine simplex method

This article presents a new method of linear programming (LP) for solving Markov decision processes (MDPs) based on the simplex method (SM). SM has shown to be the most efficient method in many practical problems; unfortunately, classical SM has an exponential complexity. Therefore, new SMs have emerged for obtaining optimal solutions in the most efficient way. The cosine simplex method (CSM) is one of them. CSM is based on the Karush Kuhn Tucker conditions, and is able to efficiently solve general LP problems. This work presents a new method named the Markov Cosine Simplex Method (MCSM) for solving MDP problems, which is an extension of CSM. In this article, the efficiency of MCSM is compared to the traditional revised simplex method (RSM); experimental results show that MCSM is far more efficient than RSM.     

Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms

The dual simplex algorithm has become a strong contender in solving large scale LP problems. One key problem of any dual simplex algorithm is to obtain a dual feasible basis as a starting point. We give an overview of methods which have been proposed in the literature and present new stable and efficient ways to combine them within a state-of-the-art optimization system for solving real world linear and mixed integer programs. Furthermore, we address implementation aspects and the connection between dual feasibility and LP-preprocessing. Computational results are given for a large set of large scale LP problems, which show our dual simplex implementation to be superior to the best existing research and open-source codes and competitive to the leading commercial code on many of our most difficult problem instances.     

A superlinearly convergent projection method for constrained systems of nonlinear equations

In this paper, a new projection method for solving a system of nonlinear equations with convex constraints is presented. Compared with the existing projection method for solving the problem, the projection region in this new algorithm is modified which makes an optimal stepsize available at each iteration and hence guarantees that the next iterate is more closer to the solution set. Under mild conditions, we show that the method is globally convergent, and if an error bound assumption holds in addition, it is shown to be superlinearly convergent. Preliminary numerical experiments also show that this method is more efficient and promising than the existing projection method. This work was done when Yiju Wang visited Chongqing Normal University.