Iterative methods for solving monotone equilibrium problems via dual gap functions

This paper proposes an iterative method for solving strongly monotone equilibrium problems by using gap functions combined with double projection-type mappings. Global convergence of the proposed algorithm is proved and its complexity is estimated. This algorithm is then coupled with the proximal point method to generate a new algorithm for solving monotone equilibrium problems. A class of linear equilibrium problems is investigated and numerical examples are implemented to verify our algorithms.     

A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems

Traditionally, minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.     

A new method for a generalized Hirota-Satsuma coupled KdV equation

In this paper, differential transform method (DTM), which is one of the approximate methods is implemented for solving the nonlinear Hirota-Satsuma coupled KdV partial differential equation. A variety of initial value system is considered, and the convergence of the method as applied to the Hirota-Satsuma coupled KdV equation is illustrated numerically. The obtained results are presented and only few terms of the expansion are required to obtain the approximate solution which is found to be accurate and efficient. Numerical examples are illustrated the pertinent features of the proposed algorithm.     

Algorithm for solving the Navier–Stokes equations for the modeling of creeping flows

We study a coupled algorithm for solving the two-dimensional Navier–Stokes equations in the stream function–vorticity variables. The algorithm is based on a finite-difference scheme in which the inertial terms in the vortex transport equation are taken from the lower time layer and the dissipative terms, from the upper time layer. In the linear approximation, we study the stability of this algorithm and use test computations to show its advantages when modeling flows at moderate Reynolds numbers.     

A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.     

Improved scatter search for the global optimization of computationally expensive dynamic models

A new algorithm for global optimization of costly nonlinear continuous problems is presented in this paper. The algorithm is based on the scatter search metaheuristic, which has recently proved to be efficient for solving combinatorial and nonlinear optimization problems. A kriging-based prediction method has been coupled to the main optimization routine in order to discard the evaluation of solutions that are not likely to provide high quality function values. This makes the algorithm suitable for the optimization of computationally costly problems, as is illustrated in its application to two benchmark problems and its comparison with other algorithms.     

Iterative solutions to coupled Sylvester-transpose matrix equations

This note studies the iterative solutions to the coupled Sylvester-transpose matrix equation with a unique solution. By using the hierarchical identification principle, an iterative algorithm is presented for solving this class of coupled matrix equations. It is proved that the iterative solution consistently converges to the exact solution for any initial values. Meanwhile, sufficient conditions are derived to guarantee that the iterative solutions given by the proposed algorithm converge to the exact solution for any initial matrices. Finally, a numerical example is given to illustrate the efficiency of the proposed approach.     

Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine

In this paper we propose a hybrid branch and bound algorithm for solving the problem of minimizing mean tardiness for a single machine problem subject to minimum number of tardy jobs. Although the minimum number of tardy jobs is known, the subset of tardy job is not known. The proposed algorithm uses traditional branch and bound scheme where lower bounds on mean tardiness are calculated coupled with using the information that the number of tardy jobs is known. It also uses an insertion algorithm which determines the optimal mean tardiness once the subset of tardy jobs is specified. An example is solved to illustrate the developed procedure.     

车辆-轨道垂向耦合系统求解过程的改进算法

考虑到轨道结构长度随系统响应持时的增加而增长，提出了一种改进的车辆 轨道垂向耦合系统的动力响应求解算法.该算法事先选定某一定长度的轨道结构，并获得该轨道结构的质量矩阵、阻尼矩阵和刚度矩阵；通过在求解过程中不断地对车辆子系统定位，判断是否需要对车辆子系统的位置和轨道结构的响应矩阵进行调整，以此来达到仅增加系统响应持时而不增加轨道结构长度的目的.算例表明:该改进加快算法是精确、高效的，不仅可以真实地模拟车辆在轨道上的前进运行状态，而且可以保证轨道子系统的轨道单元数量不随系统响应持时的增加而增长，这为快速求解车辆 轨道垂向耦合系统提供了一种有效的计算方法.     

Amplitude–shape approximation as an extension of separation of variables

Separation of variables is a well‐known technique for solving differential equations. However, it is seldom used in practical applications since it is impossible to carry out a separation of variables in most cases. In this paper, we propose the amplitude–shape approximation (ASA) which may be considered as an extension of the separation of variables method for ordinary differential equations. The main idea of the ASA is to write the solution as a product of an amplitude function and a shape function, both depending on time, and may be viewed as an incomplete separation of variables. In fact, it will be seen that such a separation exists naturally when the method of lines is used to solve certain classes of coupled partial differential equations. We derive new conditions which may be used to solve the shape equations directly and present a numerical algorithm for solving the resulting system of ordinary differential equations for the amplitude functions. Alternatively, we propose a numerical method, similar to the well‐established exponential time differencing method, for solving the shape equations. We consider stability conditions for the specific case corresponding to the explicit Euler method. We also consider a generalization of the method for solving systems of coupled partial differential equations. Finally, we consider the simple reaction diffusion equation and a numerical example from chemical kinetics to demonstrate the effectiveness of the method. The ASA results in far superior numerical results when the relative errors are compared to the separation of variables method. Furthermore, the method leads to a reduction in CPU time as compared to using the Rosenbrock semi‐implicit method for solving a stiff system of ordinary differential equations resulting from a method of lines solution of a coupled pair of partial differential equations. The present amplitude–shape method is a simplified version of previous ones due to the use of a linear approximation to the time dependence of the shape function. Copyright © 2007 John Wiley & Sons, Ltd.     

Semi-Infinite Programming and Applications to Minimax Problems

A minimisation problem with infinitely many constraints – semi-infinite programming problem (SIP) is considered. The problem is solved using a two stage procedure that searches for global maximum violation of the constraints. A version of the algorithm that searches for any violation of constraints is also considered, and the performance of the two algorithm is compared. An application to solving minimax problem (with and without coupled constraints) is given and a comparison with the algorithm for continuous minimax of Rustem and Howe (2001) is included. Finally, we consider an application to chemical engineering problems.     

Parallel pivotal algorithm for solving the linear complementarity problem

We propose a parallel implementation of the classical Lemke's algorithm for solving the linear complementarity problem. The algorithm is designed for a loosely coupled network of computers which is characterized by relatively high communication costs. We provide an accurate prediction of speedup based on a simple operation count. The algorithm produces speedup nearp, wherep is the number of processors, when tested on large problems as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-84-20963 and DCR-850-21228 and by Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the University of Wisconsin, Madison, Wisconsin.     

A reliable algorithm to solve 3D frictional multi-contact problems: Application to granular media

We present in this paper an improved non-smooth Discrete Element Method (DEM) in 3D based on the Non-Smooth Contact Dynamics (NSCD) method. We consider a three-dimensional collection of rigid particles (spheres) during the motion of which contacts can occur or break. The dry friction is modeled by Coulomb’s law which is typically non-associated. The non-associativity of the constitutive law poses numerical challenges. By adopting the use of the bi-potential concept in the framework of the NSCD DEM, a faster and more robust time stepping algorithm with only one predictor-corrector step where the contact and the friction are coupled can be devised. This contrasts with the classical method where contact and friction are treated separately leading to a time stepping algorithm that involves two predictor-corrector steps. The algorithm has been introduced in a 3D version of the NSCD DEM software MULTICOR. Numerical applications will show the robustness of the algorithm and the possibilities of the MULTICOR software for solving three-dimensional problems.     

Euler-type schemes for weakly coupled forward-backward stochastic differential equations and optimal convergence analysis

We introduce a new Euler-type scheme and its iterative algorithm for solving weakly coupled forward-backward stochastic differential equations (FBSDEs). Although the schemes share some common features with the ones proposed by C. Bender and J. Zhang [Ann. Appl. Probab., 2008, 18: 143–177], less computational work is needed for our method. For both our schemes and the ones proposed by Bender and Zhang, we rigorously obtain first-order error estimates, which improve the half-order error estimates of Bender and Zhang. Moreover, numerical tests are given to demonstrate the first-order accuracy of the schemes.     

Dichotomy and conjugate gradients in the stiff initial value problem

We propose, analyze, and experiment with solution techniques which employ the conjugate gradient algorithm coupled with prediction steps for solving the algebraic equations arising at each mesh point in the numerical development of solutions of the model stiff system $\text{x}\text{}\text{= Ax}$. A stability and error analysis based on a dichotomization of the solutions of the system into rapidly and slowly decaying modes is made, to demonstrate the numerical stability of these methods. Stiff problems are characterized by this dichotomy, and we note that the conjugate gradient algorithm improves in effectiveness with the exaggeration of this characterization.     

A note on the iterative solutions of general coupled matrix equation

Recently, Ding and Chen [F. Ding, T. Chen, On iterative solutions of general coupled matrix equations, SIAM J. Control Optim. 44 (2006) 2269-2284] developed a gradient-based iterative method for solving a class of coupled Sylvester matrix equations. The basic idea is to regard the unknown matrices to be solved as parameters of a system to be identified, so that the iterative solutions are obtained by applying hierarchical identification principle. In this note, by considering the coupled Sylvester matrix equation as a linear operator equation we give a natural way to derive this algorithm. We also propose some faster algorithms and present some numerical results.     

Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems

A new algorithm for solving large-scale convex optimization problems with a separable objective function is proposed. The basic idea is to combine three techniques: Lagrangian dual decomposition, excessive gap and smoothing. The main advantage of this algorithm is that it automatically and simultaneously updates the smoothness parameters which significantly improves its performance. The convergence of the algorithm is proved under weak conditions imposed on the original problem. The rate of convergence is $O(\frac {1}{k})$ , where k is the iteration counter. In the second part of the paper, the proposed algorithm is coupled with a dual scheme to construct a switching variant in a dual decomposition framework. We discuss implementation issues and make a theoretical comparison. Numerical examples confirm the theoretical results.     

Stability Analysis of Decoupled Solution Strategies for Coupled Multi-field Problems – A General Framework

A coupled partial differential equation (PDE) system, stemming from the mathematical modelling of a coupled phenomenon, is usually solved numerically following a monolithic or a decoupled solution method. In spite of the potential unconditional stability offered by monolithic solvers, their usage for solving complex problems sometimes proves cumbersome. This has motivated the development of various partitioned and staggered solution strategies, generally known as decoupled solution schemes. To this end, the problem is broken down into several isolated yet communicating sub-problems that are independently advanced in time, possibly by different integrators. Nevertheless, using a decoupled solver introduces additional errors to the system and, therefore, may jeopardise the stability of the solution [1]. Consequently, to scrutinise the stability of the solution scheme becomes a pertinent step in proposing decoupled solution strategies. Here, we endeavour to present a practical stability analysis algorithm, which can readily be used to reveal the stability condition of numerical solvers. To illustrate its capabilities, the algorithm is then utilised for the stability analysis of solution schemes applied to multi variate coupled PDE systems resulting from the mathematical modelling of surface- and volume-coupled multi-field problems. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Adaptive partitioning techniques for ordinary differential equations

Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65Y05     

Solution of a coupled problem of thermopiezoelectricity based on a geometrically exact shell element

Based on a 7-parameter shell model, a numerical algorithm has been developed for solving a coupled problem of thermoelectroelasticity for a laminated piezoelectric shell subjected to a thermoelectromechanical loading. As unknowns, six tangential and transverse displacements of outer surfaces and the transverse displacement of shell midsurface are chosen. This choice provides a possibility of utilizing the complete 3D constitutive equations of thermopiezoelectricity. A geometrically exact 3D hybrid piezoelectric shell element is formulated by using nonconventional analytical integration. With the help of this finite element, solutions of coupled problems of thermoelectroelasticity for laminated plates and shells with segmented and distributed piezoelectric sensors and actuators are obtained.