On the Solution of Linear Programs by Jacobian Smoothing Methods

We introduce a class of algorithms for the solution of linear programs. This class is motivated by some recent methods suggested for the solution of complementarity problems. It reformulates the optimality conditions of a linear program as a nonlinear system of equations and applies a Newton-type method to this system of equations. We investigate the global and local convergence properties and present some numerical results. The algorithms introduced here are somewhat related to the class of primal–dual interior-point methods. Although, at this stage of our research, the theoretical results and the numerical performance of our method are not as good as for interior-point methods, our approach seems to have some advantages which will also be discussed in detail.     

Q,r Inventory Models with Time-Weighted Backorders

This paper attempts to show that the iterative methods that are used to solve a class of reorder point inventory models can be replaced by some non-iterative method. The method is described in general terms and two sufficient conditions are derived to check if the method applies to a model. As illustrations, two time-weighted backorder models are considered and they are solved for Normal and Gamma leadtime demand by the proposed method. It is observed that some of the computational advantages of the method also carry over to a class of multi-item models.     

On the convergence of Runge–Kutta methods for stiff non linear differential equations

Summary. This paper studies the convergence properties of general Runge–Kutta methods when applied to the numerical solution of a special class of stiff non linear initial value problems. It is proved that under weaker assumptions on the coefficients of a Runge–Kutta method than in the standard theory of B-convergence, it is possible to ensure the convergence of the method for stiff non linear systems belonging to the above mentioned class. Thus, it is shown that some methods which are not algebraically stable, like the Lobatto IIIA or A-stable SIRK methods, are convergent for the class of stiff problems under consideration. Finally, some results on the existence and uniqueness of the Runge–Kutta solution are also presented. Received November 18, 1996 / Revised version received October 6, 1997     

On the Power of Adaption

Optimal error bounds for adaptive and nonadaptive numerical methods are compared. Since the class of adaptive methods is much larger, a well-chosen adaptive method might seem to be better than any nonadaptive method. Nevertheless there are several results saying that under natural assumptions adaptive methods are not better than nonadaptive ones. There are also other results, however, saying that adaptive methods can be significantly better than nonadaptive ones as well as bounds on how much better they can be. It turns out that the answer to the “adaption problem” depends very much on what is known a priori about the problem in question; even a seemingly small change of the assumptions can lead to a different answer.     

A Monte Carlo evaluation of three methods to detect local dependence in binary data latent class models

Binary data latent class analysis is a form of model-based clustering applied in a wide range of fields. A central assumption of this model is that of conditional independence of responses given latent class membership, often referred to as the “local independence” assumption. The results of latent class analysis may be severely biased when this crucial assumption is violated; investigating the degree to which bivariate relationships between observed variables fit this hypothesis therefore provides vital information. This article evaluates three methods of doing so. The first is the commonly applied method of referring the so-called “bivariate residuals” to a Chi-square distribution. We also introduce two alternative methods that are novel to the investigation of local dependence in latent class analysis: bootstrapping the bivariate residuals, and the asymptotic score test or “modification index”. Our Monte Carlo simulation indicates that the latter two methods perform adequately, while the first method does not perform as intended.     

Supervised learning algorithms for multi-class classification problems with partial class memberships

In several application domains such as biology, computer vision, social network analysis and information retrieval, multi-class classification problems arise in which data instances not simply belong to one particular class, but exhibit a partial membership to several classes. Existing machine learning or fuzzy set approaches for representing this type of fuzzy information mainly focus on unsupervised methods. In contrast, we present in this article supervised learning algorithms for classification problems with partial class memberships, where class memberships instead of crisp class labels serve as input for fitting a model to the data. Using kernel logistic regression (KLR) as a baseline method, first a basic one-versus-all approach is proposed, by replacing the binary-coded label vectors with [0,1]-valued class memberships in the likelihood. Subsequently, we use this KLR extension as base classifier to construct one-versus-one decompositions, in which partial class memberships are transformed and estimated in a pairwise manner. Empirical results on synthetic data and a real-world application in bioinformatics confirm that our approach delivers promising results. The one-versus-all method yields the best computational efficiency, while the one-versus-one methods are preferred in terms of predictive performance, especially when the observed class memberships are heavily unbalanced.     

Time and resonance patterns in chaotic piece-wise linear systems

The aim of this paper is to characterize time and resonant behavior in a class of piece-wise linear systems evolving chaotically. To this end, statistical methods are used to reveal interactions of different parts of the system. The system under study comprises a continuous time subsystem and a switching rule that induces an oscillatory path by switching alternately between stable and unstable conditions. Since the system is not continuous, the principal oscillation frequency depends on the switching regime and linear subsystem parameters; therefore, many time and resonant patterns can be observed. It is shown that the system may display resonance produced by the action of a external signal (switching law), as well as internal and combinational resonance. The effect of system parameters on time evolution and resonance is studied. It is shown that the nature of subsystems eigenvalues plays a crucial role in the type of resonance observed, producing in some cases complex interaction of resonance modes.     

Fractional-step <Emphasis Type="Italic">θ</Emphasis>-method for solving singularly perturbed problem in ecology

We consider a predator-prey model arising in ecology that describes a slow-fast dynamical system. The dynamics of the model is expressed by a system of nonlinear differential equations having different time scales. Designing numerical methods for solving problems exhibiting multiple time scales within a system, such as those considered in this paper, has always been a challenging task. To solve such complicated systems, we therefore use an efficient time-stepping algorithm based on fractional-step methods. To develop our algorithm, we first decouple the original system into fast and slow sub-systems, and then apply suitable sub-algorithms based on a class of θ-methods, to discretize each sub-system independently using different time-steps. Then the algorithm for the full problem is obtained by utilizing a higher-order product method by merging the sub-algorithms at each time-step. The nonlinear system resulting from the use of implicit schemes is solved by two different nonlinear solvers, namely, the Jacobian-free Newton-Krylov method and the well-known Anderson’s acceleration technique. The fractional-step θ-methods give us flexibility to use a variety of methods for each sub-system and they are able to preserve qualitative properties of the solution. We analyze these methods for stability and convergence. Several numerical results indicating the efficiency of the proposed method are presented. We also provide numerical results that confirm our theoretical investigations.     

Symmetric general linear methods

The article considers symmetric general linear methods, a class of numerical time integration methods which, like symmetric Runge–Kutta methods, are applicable to general time-reversible differential equations, not just those derived from separable second-order problems. A definition of time-reversal symmetry is formulated for general linear methods, and criteria are found for the methods to be free of linear parasitism. It is shown that symmetric parasitism-free methods cannot be explicit, but such a method of order 4 is constructed with only one implicit stage. Several characterizations of symmetry are given, and connections are made with G-symplecticity. Symmetric methods are shown to be of even order, a suitable symmetric starting method is constructed and shown to be essentially unique. The underlying one-step method is shown to be time-symmetric.     

Simulation of elastic wave propagation in geological media: Intercomparison of three numerical methods

For wave propagation in heterogeneous media, we compare numerical results produced by grid-characteristic methods on structured rectangular and unstructured triangular meshes and by a discontinuous Galerkin method on unstructured triangular meshes as applied to the linear system of elasticity equations in the context of direct seismic exploration with an anticlinal trap model. It is shown that the resulting synthetic seismograms are in reasonable quantitative agreement. The grid-characteristic method on structured meshes requires more nodes for approximating curved boundaries, but it has a higher computation speed, which makes it preferable for the given class of problems.     

A higher order iterative method for A^{(2)}_{T,S}

The aim of this paper is to propose a higher order iterative method for computing the outer inverse \(A^{(2)}_{T,S}\) for a given matrix A. Convergence analysis along with the error bounds of the proposed method is established. A number of numerical examples including singular square, rectangular, randomly generated rank deficient matrices and a set of singular matrices obtained from the Matrix Computation Toolbox (mctoolbox) are worked out. The performance measures used are the number of iterations, the mean CPU time (MCT) and the error bounds. The results obtained are compared with some of the existing methods. It is observed that our method gives improved results in terms of both computational speed and accuracy.     

Asymptotic stability of exact and discrete solutions for neutral multidelay-integro-differential equations

This paper concerns the long-time behavior of the exact and discrete solutions to a class of nonlinear neutral integro-differential equations with multiple delays. Using a generalized Halanay inequality, we give two sufficient conditions for the asymptotic stability of the exact solution to this class of equations. Runge–Kutta methods with compound quadrature rule are considered to discretize this class of equations with commensurate delays. Nonlinear stability conditions for the presented methods are derived. It is found that, under suitable conditions, this class of numerical methods retain the asymptotic stability of the underlying system. Some numerical examples that illustrate the theoretical results are given.     

A Convergent Variant of the Nelder–Mead Algorithm

The Nelder–Mead algorithm (1965) for unconstrained optimization has been used extensively to solve parameter estimation and other problems. Despite its age, it is still the method of choice for many practitioners in the fields of statistics, engineering, and the physical and medical sciences because it is easy to code and very easy to use. It belongs to a class of methods which do not require derivatives and which are often claimed to be robust for problems with discontinuities or where the function values are noisy. Recently (1998), it has been shown that the method can fail to converge or converge to nonsolutions on certain classes of problems. Only very limited convergence results exist for a restricted class of problems in one or two dimensions. In this paper, a provably convergent variant of the Nelder–Mead simplex method is presented and analyzed. Numerical results are included to show that the modified algorithm is effective in practice.     

Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation

We consider the so-called parallel and serial scheduling method for the classical resource-constrained project scheduling problem. Theoretical results on the class of schedules generated by each method are provided. Furthermore, an in-depth computational study is undertaken to investigate the relationship of single-pass scheduling and sampling for both methods. It is shown that the performance-ranking of priority rules does not differ for single-pass scheduling and sampling, that sampling improves the performance of single-pass scheduling significantly, and that the parallel method cannot be generally considered as superior.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

A third order,semi-explicit method in the numerical solution of first kind Volterra integral equations

We present a new numerical method for the solution of nonsingular Volterra integral equations of the first kind. It belongs to a new class of methods that are semi-explicit, provide self-starting algorithms and possess favourable stability properties. The third order convergence of the particular method exhibited is established, under suitable conditions, and numerical results are illustrated.     

ON THE BREAKDOWNS OF THE GALERKIN AND LEAST-SQUARES METHODS

1　ＩｎｔｒｏｄｕｃｔｉｏｎＷｅｃｏｎｓｉｄｅｒｌｉｎｅａｒｓｙｓｔｅｍｓｏｆｔｈｅｆｏｒｍＡｘ=ｂ,(1 )ｗｈｅｒｅＡ∈ＣＮ×Ｎｉｓｎｏｎｓｉｎｇｕｌａｒａｎｄｐｏｓｓｉｂｌｙｎｏｎ Ｈｅｒｍｉｔｉａｎ .Ａｍａｊｏｒｃｌａｓｓｏｆｍｅｔｈｏｄｓｆｏｒｓｏｌｖｉｎｇ (1 )ｉｓｔｈｅｃｌａｓｓｏｆＫｒｙｌｏｖｓｕｂｓｐａｃｅｍｅｔｈｏｄｓ (ｓｅｅ[6] ,[1 3]ｆｏｒｏｖｅｒｖｉｅｗｓｏｆｓｕｃｈｍｅｔｈｏｄｓ) ,ｄｅｆｉｎｅｄｂｙｔｈｅｐｒｏｐｅｒｔｉｅｓｘｍ ∈ｘ0 +Ｋｍ(ｒ0 ,Ａ) ;(2 )ｒｍ ⊥Ｌｍ, (3)ｗｈｅ…     

On the discrepancy principle for iterative and parametric methods to solve linear ill-posed equations

Summary. For the numerical solution of (non-necessarily well-posed) linear equations in Banach spaces we consider a class of iterative methods which contains well-known methods like the Richardson iteration, if the associated resolvent operator fulfils a condition with respect to a sector. It is the purpose of this paper to show that for given noisy right-hand side the discrepancy principle (being a stopping rule for the iteration methods belonging to the mentioned class) defines a regularization method, and convergence rates are proved under additional smoothness conditions on the initial error. This extends similar results obtained for positive semidefinite problems in Hilbert spaces. Then we consider a class of parametric methods which under the same resolvent condition contains the method of the abstract Cauchy problem, and (under a weaker resolvent condition) the iterated method of Lavrentiev. A modified discrepancy principle is formulated for them, and finally numerical illustrations are presented. Received August 29, 1994 / Revised version received September 19, 1995     

一类半整数自由度级的非线性共振及其在电力系统中的应用

本部分讨论下列两自由度实系统:(?) (1)其中“·”代表 d/(dt),λ_1>0,λ_2>0,ε为正小参数,k_1(t) 和 k_2(t) 是周期为(2x)/v 的周期函数.同时假设,f_1(x),f_2(x),k_1(t),k_2(t)都是足够光滑的.系统(1)包括双机电力系统为其特例.在§4中将叙述本文的结果在双机电力系统上的应用.本文关心的问题是在状态 x_1和 x_2之间,是否会发生周期与 k_1(t),k_2(t) 的周期相同的振动现象,以及具体的计算方法.为此,需要有 x 的方程.在 λ_1=λ_2时问题特别简单,     

Nonsingular decoupled terminal sliding-mode control for a class of fourth-order nonlinear systems

This paper presents a nonsingular decoupled terminal sliding mode control (NDTSMC) method for a class of fourth-order nonlinear systems. First, the nonlinear fourth-order system is decoupled into two second-order subsystems which are referred to as the primary and secondary subsystems. The sliding surface of each subsystem was designed by utilizing time-varying coefficients which are computed by linear functions derived from the input–output mapping of the one-dimensional fuzzy rule base. Then, the control target of the secondary subsystem was embedded to the primary subsystem by the help of an intermediate signal. Thereafter, a nonsingular terminal sliding mode control (NTSMC) method was utilized to make both subsystems converge to their equilibrium points in finite time. The simulation results on the inverted pendulum system are given to show the effectiveness of the proposed method. It is seen that the proposed method exhibits a considerable improvement in terms of a faster dynamic response and lower IAE and ITAE values as compared with the existing decoupled control methods.