Search

Concave knapsack problems with integer variables have many applications in real life, and they are NP-hard. In this paper, an exact and efficient algorithm is presented for concave knapsack problems. The algorithm combines the contour cut with a special cut to improve the lower bound and reduce the duality gap gradually in the iterative process. The lower bound of the problem is obtained by solving a linear underestimation problem. A special cut is performed by exploiting the structures of the objective function and the feasible region of the primal problem. The optimal solution can be found in a finite number of iterations, and numerical experiments are also reported for two different types of concave objective functions. The computational results show the algorithm is efficient. [ABSTRACT FROM AUTHOR]

Recently, Salkuyeh and Fahim [A new iterative refinement of the solution of ill-conditioned linear system of equations, Int. Comput. Math. 88(5) (2011), pp. 950–956] have proposed a two-step iterative refinement of the solution of an ill-conditioned linear system of equations. In this paper, we first present a generalized two-step iterative refinement procedure to solve ill-conditioned linear system of equations and study its convergence properties. Afterward, it is shown that the idea of an orthogonal projection technique together with a basic stationary iterative method can be utilized to construct a new efficient and neat hybrid algorithm for solving the mentioned problem. The convergence of the offered hybrid approach is also established. Numerical examples are examined to demonstrate the feasibility of proposed algorithms and their superiority to some of existing approaches for solving ill-conditioned linear system of equations. [ABSTRACT FROM PUBLISHER]

In this paper,we propose a new predictor–corrector interior-point method for symmetric cone programming. This algorithm is based on a wide neighbourhood and the Nesterov–Todd direction. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of, whereris the rank of the associated Euclidean Jordan algebras. In particular, the complexity bound is, whereis a given tolerance. To our knowledge, this is the best complexity result obtained so far for interior-point methods with a wide neighbourhood over symmetric cones. The numerical results show that the proposed algorithm is effective. [ABSTRACT FROM AUTHOR]

In this paper we present some techniques for constructing high-order iterative methods in order to approximate the zeros of a non-linear equation f(x)=0, starting from a well-known family of cubic iterative processes. The first technique is based on an additional functional evaluation that allows us to increase the order of convergence from three to five. With the second technique, we make some changes aimed at minimizing the calculus of inverses. Finally, looking for a better efficiency, we eliminate terms that contribute to the error equation from sixth order onwards. The paper contains a comparative study of the asymptotic error constants of the methods and some theoretical and numerical examples that illustrate the given results. We also analyse the efficiency of the aforementioned methods, by showing some numerical examples with a set of test functions and by using adaptive multi-precision arithmetic in the computation. [ABSTRACT FROM AUTHOR]

This paper describes the Adaptive Steepest Descent (ASD) and Optimal Fletcher-Reeves (OFR) algorithms for linear neural network training. The algorithms are applied to well-known pattern classification and function approximation problems, belonging to benchmark collection Proben1. The paper discusses the convergence behavior and performance of the ASD and OFR training algorithms by computer simulations and compares the results with those produced by linear-RPROP method. [ABSTRACT FROM AUTHOR]

This paper presents a new hybrid algorithm for unconstrained optimization problems, which combines the idea of the IMPBOT algorithm with the nonmonotone line search technique. A feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step, via a modified limited-memory BFGS two loop recursion that requires only matrix–vector products, thus reducing the computations and storage. Furthermore, when the trial step is not accepted, the proposed method performs a line search along it using a modified nonmonotone scheme, thus a larger stepsize can be yielded in each line search procedure. Under some reasonable assumptions, the convergence properties of the proposed algorithm are analysed. Numerical results are also reported to show the efficiency of this proposed method. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a trust-region algorithm in association with line search filter technique for solving nonlinear equality constrained programming. At current iteration, a trial step is formed as the sum of a normal step and a tangential step which is generated by trust-region subproblem and the step size is decided by interior backtracking line search together with filter methods. Then, the next iteration is determined. This is different from general trust-region methods in which the next iteration is determined by the ratio of the actual reduction to the predicted reduction. The global convergence analysis for this algorithm is presented under some reasonable assumptions and the preliminary numerical results are reported. [ABSTRACT FROM PUBLISHER]

In this paper, the Hermitian positive-definite solutions of the matrix equationXs+A*X−tA=Qare considered. New necessary and sufficient conditions for the equation to have a Hermitian positive-definite solution are derived. In particular, whenAis singular, a new estimate of Hermitian positive-definite solutions is obtained. In the end, based on the fixed point theorem, an iterative algorithm for obtaining the positive-definite solutions of the equation withQ=Iis discussed. The error estimations are found. [ABSTRACT FROM AUTHOR]

In this paper, we propose an iterative algorithm for a simplified friction problem which is formulated as an elliptic variational inequality of the second kind. We approximate the simplified friction problem by a discrete system with the finite element method. Based on the use of the linearized technique and by constructing a particular function, we put forward the new algorithm to get the discrete solution. This algorithm is attractive due to its simple proof of convergence and easy implementation. A linear equation is solved in each iteration. Numerical results confirm that our algorithm is efficient and mesh independent. [ABSTRACT FROM AUTHOR]

In this paper, we present an iterative algorithm for solving the following coupled Sylvester-transpose matrix equationsover the generalized centro-symmetric matrix group (X1,X2, …,Xq). The solvability of the problem can be determined by the proposed algorithm, automatically. If the coupled Sylvester-transpose matrix equations are consistent over the generalized centro-symmetric matrices, then a generalized centro-symmetric solution group can be obtained within finite iterative steps for any initial generalized centro-symmetric matrix group in the exact arithmetic. Furthermore, it is shown that the least-norm generalized centro-symmetric solution group of the coupled Sylvester-transpose matrix equations can be computed by choosing an appropriate initial iterative matrix group. Moreover, the optimal approximate generalized centro-symmetric solution group to a given arbitrary matrix group (V1,V2, …,Vq) can be derived by finding the least-norm generalized centro-symmetric solution group of a new coupled Sylvester-transpose matrix equations. Finally, some numerical results are given to illustrate the validity and practicability of the theoretical results established in this work. [ABSTRACT FROM PUBLISHER]

This paper focuses on identification problems for Hammerstein systems with non-uniform sampling. By using the over-parameterization technique, we derive a linear regressive identification model with different input updating rates. To solve the identification problem of Hammerstein output error systems with the unmeasurable variables in the information vector, the least-squares-based iterative algorithm is presented by replacing the unmeasurable variables with their corresponding iterative estimates. The performances of the proposed algorithm are analysed and compared by using a numerical example. [ABSTRACT FROM PUBLISHER]

This paper provides a mathematical framework for modelling collaborative reputation systems (CRSs), which are useful in many fields of electronic commerce. A CRS is an algorithm that, at discrete points in time, receives in input from a set of users some ratings of a set of objects and generates a reputation for both the raters and the evaluated objects. Sufficient conditions for the convergence of a CRS are given, using basic results of the fixed point theory, and in particular for a broad class of iterative filtering methods and their related CRSs, generalizing some previous results. Finally, we analyse a simple kind of CRS which allows to use a priori information on the reliability of a subset of raters. Experimental results provide evidence that such CRSs exhibit high level of robustness against unfair raters. [ABSTRACT FROM AUTHOR]

In this paper, a novel hybrid method based on two approaches, evolutionary algorithms and an iterative scheme, for obtaining the approximate solution of optimal control governed by nonlinear Fredholm integral equations is presented. By converting the problem to a discretized form, it is considered as a quasi-assignment problem and then an iterative method is applied to find an approximate solution for the discretized form of the integral equation. An analysis for convergence of the proposed iterative method and its implementation for numerical examples are also given. [ABSTRACT FROM AUTHOR]

In this paper, combining the equivalent form of the unified coupled algebraic Riccati equation (UCARE) with the eigenvalue inequalities of a matrix's sum and product, using the properties of an M-matrix and its inverse matrix, we offer new lower and upper matrix bounds for the solution of the UCARE. Furthermore, applying the derived lower and upper matrix bounds and a fixed-point theorem, an existence uniqueness condition of the solution of the UCARE is proposed. Then, we propose a new fixed-point iterative algorithm for the solution of the UCARE. Finally, we present a corresponding numerical example to demonstrate the effectiveness of our results. [ABSTRACT FROM PUBLISHER]

Algebraic reconstruction techniques (ARTs), on both their successive and simultaneous formulations, have been developed since the early 1970s as efficient ‘row-action methods’ for solving the image-reconstruction problem in computerized tomography. In this respect, two important development directions were concerned with, first, their extension to the inconsistent case of the reconstruction problem and, second, their combination with constraining strategies, imposed by the particularities of the reconstructed image. In the first part of this paper, we introduce extending and constraining procedures for a general iterative method of an ART type and we propose a set of sufficient assumptions that ensure the convergence of the corresponding algorithms. As an application of this approach, we prove that Cimmino's simultaneous reflection method satisfies this set of assumptions, and we derive extended and constrained versions for it. Numerical experiments with all these versions are presented on a head phantom widely used in the image reconstruction literature. We also consider hard thresholding constraining used in sparse approximation problems and apply it successfully to a 3D particle image-reconstruction problem. [ABSTRACT FROM PUBLISHER]

In this paper, two predictor-corrector methods are proposed for solving nonlinear equations by combining the fuzzy parameterized method with the exponential iterative method and the regula falsi method. The parameter values are determined by a Γ-fuzzy number in the iterative procedure. These two methods present attractive features such as being independent of the initial values, or being adaptive for the iterative formulas. They are verified to also be quadratically convergent. Compared with the previously well-known methods, numerical experiments show that new predictor-corrector methods are effective. [ABSTRACT FROM AUTHOR]

Karimi and Toutounian [The block least squares method for solving nonsymmetric linear system with multiple right-hand sides, Appl. Math. Comput. 177 (2006), pp. 852-862], proposed a block version of the LSQR algorithm, say Bl-LSQR, for solving linear system of equations with multiple right-hand sides. In this paper, the convergence of the Bl-LSQR algorithm is studied. We deal with some computational aspects of the Bl-LSQR algorithm for solving matrix equations. Some numerical experiments on test matrices are presented. [ABSTRACT FROM AUTHOR]

In this paper, we propose a multi-projection method and its re-iterated algorithm for solving weakly singular Fredholm integral equations of the second kind. We apply our methods to Petrov-Galerkin versions to establish excellent superconvergence results, and we illustrate our theoretical results with a numerical example. [ABSTRACT FROM AUTHOR]

According to the special demands arising from the development of science and technology, in the last decades appeared a special class of problems that are inverse to the classical direct ones. Such an inverse problem is concerned with the opposite way, usually followed by a direct one: finding the cause of a given effect or finding the law of evolution given the cause and effect. Very frequently, such inverse problems are modelled by Fredholm first-kind integral equations that give rise after discretization to (very) ill-conditioned linear systems, in classical or least squares formulation. Then, an efficient numerical solution can be obtained by using the Tikhonov regularization technique. In this respect, in the present paper, we propose three Kovarik-like algorithms for numerical solution of the regularized problem. We prove convergence for all three methods and present numerical experiments on a mathematical model of an inverse problem concerned with the determination of charge distribution generating a given electric field. [ABSTRACT FROM AUTHOR]

In this paper, an iterative method is presented for finding the bisymmetric solutions of a pair of consistent matrix equations A1XB1=C1, A2XB2=C2, by which a bisymmetric solution can be obtained in finite iteration steps in the absence of round-off errors. Moreover, the solution with least Frobenius norm can be obtained by choosing a special kind of initial matrix. In the solution set of the matrix equations, the optimal approximation bisymmetric solution to a given matrix can also be derived by this iterative method. The efficiency of the proposed algorithm is shown by some numerical examples. [ABSTRACT FROM AUTHOR]

A novel approach to simulate cellular neural networks (CNN) is presented in this paper. The approach, time-multiplexing simulation, is prompted by the need to simulate hardware models and test hardware implementations of CNN. For practical applications, due to hardware limitations, it is impossible to have a one-to-one mapping between the CNN hardware processors and all the pixels of the image. This simulator provides a solution by processing the input image block by block, with the number of pixels in a block being the same as the number of CNN processors in the hardware. The algorithm for implementing this simulator is presented along with popular numerical integration algorithms. Some simulation results and comparisons are also presented. [ABSTRACT FROM AUTHOR]

In this paper, the variational iteration method is used to solve a system of third-order boundary value problem associated with obstacle, unilateral and contact problems. Numerical solution obtained by the method is of high accuracy. The numerical example compared with those considered by other authors shows that the method is more efficient. [ABSTRACT FROM AUTHOR]

This paper describes a cubically convergent iteration method for finding the multiple roots of nonlinear equations, f(x)=0, where f:→ is a continuous function. This work is the extension of our earlier work [P.K. Parida, and D.K. Gupta, An improved regula-falsi method for enclosing simple zeros of nonlinear equations, Appl. Math. Comput. 177 (2006), pp. 769-776] where we have developed a cubically convergent improved regula-falsi method for finding simple roots of f(x)=0. First, by using some suitable transformation, the given function f(x) with multiple roots is transformed to F(x) with simple roots. Then, starting with an initial point x0 near the simple root x* of F(x)=0, the sequence of iterates {xn}, n=0, 1, ... and the sequence of intervals {[an, bn]}, with x*∈{[an, bn]} for all n are generated such that the sequences {(xn-x*)} and {(bn-an)} converges cubically to 0 simultaneously. The convergence theorems are established for the described method. The method is tested on a number of numerical examples and the results obtained are compared with those obtained by King [R.F. King, A secant method for multiple roots, BIT 17 (1977), pp. 321-328.]. [ABSTRACT FROM AUTHOR]

In this paper, we present and analyse a new predictor-corrector iterative method for solving non-linear single variable equations. The convergence analysis establishes that the new method is cubically convergent. Numerical tests show that the method is comparable with the well-known existing methods and in many cases gives better results. [ABSTRACT FROM AUTHOR]

The extended version with the analysis of dynamic system for Wilkinson's iteration improvement of solution is presented in this paper. It turns out that the iteration improvement can be viewed as applying explicit Euler method with step size h=1 to a dynamic system which has a unique globally asymptotically stable equilibrium point, that is, the solution x*=A-1b of linear system Ax=b with non-singular matrix A. As a result, an extended iterative improvement process for solving ill-conditioned linear system of algebraic equations with non-singular coefficients matrix is proposed by following the solution curve of a linear system of ordinary differential equations. We prove the unconditional convergence and derive the roundoff results for the extended iterative refinement process. Several numerical experiments are given to show the effectiveness and competition of the extended iteration refinement in comparison with Wilkinson's. [ABSTRACT FROM AUTHOR]

This paper develops an iterative algorithm for the solution to a variable-coefficient semilinear heat equation with nonlocal boundary conditions in the reproducing space. It is proved that the approximate sequence un(x, t) converges to the exact solution u(x, t). Moreover, the partial derivatives of un(x, t) are also convergent to the partial derivatives of u(x, t). And the approximate sequence un(x, t) is the best approximation under a complete normal orthogonal system. [ABSTRACT FROM AUTHOR]

The development of optimization theory originated with economic requirements and problems, where optimal strategy was to be determined mathematically. At about the same time, approximation theory, which was already well developed, experienced a reinvigoration brought about by the advent of electronic computers. In this paper, what follows, we recall the functional analysis that constitutes the framework of our development of an extended conjugate gradient algorithm that does not involve any approximation in any of its steps. This is a computational enhancement over the conventional conjugate gradient method which is dependent on some approximation theory. We use this improved algorithm for the construction of some functional inequalities. [ABSTRACT FROM AUTHOR]

In this paper, we report on a non-uniform mesh smart alternating group explicit (SMAGE) parallel algorithm for the solution of non-linear singular two-point boundary value (BV) problems. The proposed method requires three non-uniform grid points and is applicable to both singular and non-singular problems. We also discuss the Newton-SMAGE parallel algorithm for the non-linear difference equations. The error analysis of the method is discussed and numerical tests are performed to demonstrate the utility of the proposed SMAGE iterative methods. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm for obtaining the Hermitian positive definite solutions of the nonlinear matrix equation X + A * X -1 A = I is considered and discussed. The convergence of the algorithm is proved. Numerical experiments to illustrate the behavior of the algorithm are executed. [ABSTRACT FROM AUTHOR]

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations such as when distributed mutual-exclusion algorithms are used, or when information retrieval algorithms need to compromise between fast access and small storage. The Diameter-Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph, G , with n nodes and a positive integer, k , find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP-complete, for all values of k ; 4≤ k ≤( n -2). In this paper, we investigate the behavior of the diameter of an MST in randomly generated graphs. Then, we present heuristics that produce approximate solutions for the DCMST problem in polynomial time. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs. [ABSTRACT FROM AUTHOR]

We consider parallel matrix multisplitting methods for solving linear complementarity problem that finds a real vector z ∈ R n such that Mz + q ≥0, z ≥0 and z T ( Mz + q )=0, where M ∈ R n × n is a given real matrix and q ∈ R n a given real vector. The recently developed parallel asynchronous multisplitting iterative methods based on fixed-point transformation of the problem, explicit projection of the system and implicit splittings of the matrix are reviewed; their asymptotic convergence properties for some typical matrix class are discussed; and their internal relationships are studied. Therefore, systematic algorithmic models in the sense of multisplitting and reliable theoretical guarantees in the sense of asymptotic convergence are presented for solving the large sparse linear complementarity problems on modern high-speed multiprocessor systems. This paper is a continuity of the recent work of Bai and Evans [18] , which includes the parallel synchronous and chaotic matrix multisplitting iterative methods and their convergence theories. [ABSTRACT FROM AUTHOR]

In this paper, the Alternating Group Explicit (AGE) method is developed from a judicious splitting of the implicit equations derived from the finite difference discretisation of the partial differential equations. The resulting equations can be reformulated in a (2 × 2) explicit form resulting in a new stable and efficient method. Finally, the AGE method is used to investigate the numerical solution of the Telegraph equation in various 2D forms. [ABSTRACT FROM AUTHOR]