Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

Nonlinear iterative operator splitting methods and applications for nonlinear differential equations

In this paper we discuss decomposition methods that are used for solving nonlinear differential equations. The motivation arose from the need to decouple nonlinear operator equations into simpler, computable operator equations [1]; [2]. We consider iterative operator-splitting methods for the decoupling of the differential equations and we apply iterative steps to achieve linearisation. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

非线性方程组的具有单边初值条件的分裂型单调迭代法

本文利用区间迭代法的思想，提出了一种使用单边初值条件的分裂型单调迭代方法，证明了该方法的收敛性，并且具体化到常见的单调迭代法。     

A stable primal–dual approach for linear programming under nondegeneracy assumptions

This paper studies a primal–dual interior/exterior-point path-following approach for linear programming that is motivated on using an iterative solver rather than a direct solver for the search direction. We begin with the usual perturbed primal–dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. Assuming that a basis matrix (easily factorizable and well-conditioned) can be found, we apply a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in a single bilinear equation that maintains the well-posedness property. Sparsity is maintained. We then apply either a direct solution method or an iterative solver (within an inexact Newton framework) to solve this equation. Since the linearization is well posed, we use affine scaling and do not maintain nonnegativity once we are close enough to the optimum, i.e. we apply a change to a pure Newton step technique. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). We test our method with random nondegenerate problems and problems from the Netlib set, and we compare it with the standard Normal Equations NEQ approach. We use a heuristic to find the basis matrix. We show that our method is efficient for large, well-conditioned problems. It is slower than NEQ on ill-conditioned problems, but it yields higher accuracy solutions.     

A General Iterative Procedure for Solving Nonsmooth Generalized Equations

We present a general iterative procedure for solving generalized equations in the nonsmooth framework. To this end, we consider a class of functions admitting a certain type of approximation and establish a local convergence theorem that one can apply to a wide range of particular problems.Mathematics Subject Classification (2000): 47H04, 65K10     

Majorizing sequences for iterative methods

We provide convergence results for very general majorizing sequences of iterative methods. Using our new concept of recurrent functions, we unify the semilocal convergence analysis of Newton-type methods (NTM) under more general Lipschitz-type conditions. We present two very general majorizing sequences and we extend the applicability of (NTM) using the same information before Chen and Yamamoto (1989) [13], Deuflhard (2004) [16], Kantorovich and Akilov (1982) [19], Miel (1979) [20], Miel (1980) [21] and Rheinboldt (1968) [30]. Applications, special cases and examples are also provided in this study to justify the theoretical results of our new approach.     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

A NOTE ON COMPARISON THEOREM OF TWO-STAGE ITERATIVE METHOD FOR HERMITIAN POSITIVE DEFINITE LINEAR SYSTEMS

We discuss two-stage iterative methods for the solution of linear system Ax = b, and give a new proof of the comparison theorems of two-stage iterative method for an Hermitian positive definite matrix. Meanwhile, we put forward two new versions of well known comparison theorem and apply them to some examples.     

Operator-splitting methods in respect of eigenvalue problems for nonlinear equations and applications for Burgers equations

In this article we consider iterative operator-splitting methods for nonlinear differential equations with respect to their eigenvalues. The main focus of the proposed idea is the fixed-point iterative scheme that linearizes our underlying equations. On the basis of the approximated eigenvalues of such linearized systems we choose the order of the operators for our iterative splitting scheme. The convergence properties of such a mixed method are studied and demonstrated. We confirm with numerical applications the effectiveness of the proposed scheme in comparison with the standard operator-splitting methods by providing improved results and convergence rates. We apply our results to deposition processes.     

A NEW APPROACH TO SOLVE SYSTEMS OF LINEAR EQUATIONS

1. IntroductionThe new aPProaCh is based on the analysis of the motion of a damped harmonic oscillatorin the gravitational field 11]. The associated equation of motion ismXtt + oXt + aX = b (1)where X = X(t), is the one dimensions di8PlaCement of Of a mass m under a dissipation(o > 0), a ~nic potential (a > 0) and a constant acceleration (b, gravitational field). Thetotal energy variation is given by the equationwhereThe solution of the motion equation (1) is given by the sum of two contr…     

Household Lifetime Strategies under a Self-Contagious Market

In this paper, we consider the optimal strategies in asset allocation, consumption, and life insurance for a household with an exogenous stochastic income under a self-contagious market which is modeled by bivariate self-exciting Hawkes jump processes. By using the Hawkes process, jump intensities of the risky asset depend on the history path of that asset. In addition to the financial risk, the household is also subject to an uncertain lifetime and a fixed retirement date. A lump-sum payment will be paid as a heritage, if the wage earner dies before the retirement date. Under the dynamic programming principle, explicit solutions of the optimal controls are obtained when asset prices follow special jump distributions. For more general cases, we apply the Feynman–Kac formula and develop an iterative numerical scheme to derive the optimal strategies. We also prove the existence and uniqueness of the solution to the fixed point equation and the convergence of an iterative numerical algorithm. Numerical examples are presented to show the effect of jump intensities on the optimal controls.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

Numerical transformation methods: a constructive approach

Within group invariance theory we consider a constructive approach in order to define numerical transformation methods. These are initial-value methods for the solution of boundary value problems governed by ordinary differential equations. Here we consider the class of free boundary value problems governed by the most general second-order equation in normal form. For this class of problems the main theorem is concerned with the definition of an iterative transformation method. The definition of a noniterative method, applicable to a subclass of the original class of problems, follows as a corollary. Therefore, the proposed constructive approach allows us to establish a unifying framework for noniterative and iterative transformation methods.     

Comparison of the EM algorithm and alternatives

The Expectation-Maximization (EM) algorithm is widely used also in industry for parameter estimation within a Maximum Likelihood (ML) framework in case of missing data. It is well-known that EM shows good convergence in several cases of practical interest. To the best of our knowledge, results showing under which conditions EM converges fast are only available for specific cases. In this paper, we analyze the connection of the EM algorithm to other ascent methods as well as the convergence rates of the EM algorithm in general including also nonlinear models and apply this to the PMHT model. We compare the EM with other known iterative schemes such as gradient and Newton-type methods. It is shown that EM reaches Newton-convergence in case of well-separated objects and a Newton-EM combination turns out to be robust and efficient even in cases of closely-spaced targets.     

The general iterative methods for nonexpansive mappings in Banach spaces

In this paper, we introduce a general iterative approximation method for finding a common fixed point of a countable family of nonexpansive mappings which is a unique solution of some variational inequality. We prove the strong convergence theorems of such iterative scheme in a reflexive Banach space which admits a weakly continuous duality mapping. As applications, at the end of the paper, we apply our results to the problem of finding a zero of an accretive operator. The main result extends various results existing in the current literature.     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

A Hybrid Viscosity Approximation Method for a Common Solution of a General System of Variational Inequalities,an Equilibrium Problem,and Fixed Point Problems

In this paper, we introduce a new iterative method based on the hybrid viscosity approximation method for finding a common element of the set of solutions of a general system of variational inequalities, an equilibrium problem, and the set of common fixed points of a countable family of nonexpansive mappings in a Hilbert space. We prove a strong convergence theorem of the proposed iterative scheme under some suitable conditions on the parameters. Furthermore, we apply our main result for W-mappings. Finally, we give two numerical results to show the consistency and accuracy of the scheme.     

Optimal Secant-Type Methods for Operator Equations

We prove an existence and uniqueness theorem for operator equations in Banach spaces with (generally non-differentiable) operators whose divided differences are Lipschitz continuous on operator's domain. The theorem makes possible to apply the concept of entropy optimality of iterative methods introduced in our earlier work to the class of secant-type methods. Using this concept, we show that it is feasible to get a method that needs the same information (one value of the operator) per iteration but exhibits a faster convergence than the secant and secant-update methods.     

Landweber iterative methods for angle-limited image reconstruction

We introduce a general iterative scheme for angle-limited image reconstruction based on Landwebet＇s method. We derive a representation formula for this scheme and consequently establish its convergence conditions. Our results suggest certain relaxation strategies for an accelerated convergence for angle-limited image reconstruction in L^2-norm comparing with alternative projection methods. The convolution-backprojection algorithm is given for this iterative process.     

Stein’s method on Wiener chaos

We combine Malliavin calculus with Stein’s method, in order to derive explicit bounds in the Gaussian and Gamma approximations of random variables in a fixed Wiener chaos of a general Gaussian process. Our approach generalizes, refines and unifies the central and non-central limit theorems for multiple Wiener–Itô integrals recently proved (in several papers, from 2005 to 2007) by Nourdin, Nualart, Ortiz-Latorre, Peccati and Tudor. We apply our techniques to prove Berry–Esséen bounds in the Breuer–Major CLT for subordinated functionals of fractional Brownian motion. By using the well-known Mehler’s formula for Ornstein–Uhlenbeck semigroups, we also recover a technical result recently proved by Chatterjee, concerning the Gaussian approximation of functionals of finite-dimensional Gaussian vectors.