We propose a new variable dimension algorithm for solving a system ofn equations inn variables. The algorithm solves a sequence of subproblems consisting of the first several equations, the dimension of subproblems do...
详细信息
We propose a new variable dimension algorithm for solving a system ofn equations inn variables. The algorithm solves a sequence of subproblems consisting of the first several equations, the dimension of subproblems does not, however, increase monotonically. A convergence condition is also presented.
In this paper we establish a basic theory for variable dimension algorithms which were originally developed for computing fixed points by Van der Laan and Talman. We introduce a new concept ‘primal—dual pair of subd...
详细信息
In this paper we establish a basic theory for variable dimension algorithms which were originally developed for computing fixed points by Van der Laan and Talman. We introduce a new concept ‘primal—dual pair of subdivided manifolds’ and by utilizing it we propose a basic model which will serve as a foundation for constructing a wide class of variable dimension algorithms. Our basic model furnishes interpretations to several existing methods: Lemke's algorithm for the linear complementarity problem, its extension to the nonlinear complementarity problem, a variable dimension algorithm on conical subdivisions and Merrill's algorithm. We shall present a method for solving systems of equations as an application of the second method and an efficient implementation of the fourth method to which our interpretation leads us. A method for constructing triangulations with an arbitrary refinement factor of mesh size is also proposed.
We propose an algorithm to find an integer point of a simplex. The algorithm is based on an integer labeling rule and a triangulation of the space. Starting atom integer point, the algorithm leaves it along one of n r...
详细信息
We propose an algorithm to find an integer point of a simplex. The algorithm is based on an integer labeling rule and a triangulation of the space. Starting atom integer point, the algorithm leaves it along one of n rays and generates a sequence of adjacent simplices of varying dimension. Within a finite number of iterations, the algorithm either yields an integer point of the simplex or proves that no such point exists.
A new variabledimension simplicial algorithm for the computation of solutions of systems of nonlinear equations or the computation of fixed points is presented. It uses the restrart technique of Merrill to improve th...
详细信息
A new variabledimension simplicial algorithm for the computation of solutions of systems of nonlinear equations or the computation of fixed points is presented. It uses the restrart technique of Merrill to improve the accuracy of the solution. The algorithm is shown to converge quadratically under certain conditions. The algorithm should be efficient and relatively easy to implement.
A continuous deformation algorithm is proposed for solving a variational inequality problem on a polytope K. The algorithm embeds the polytope K into K x [0, infinity) and starts by applying a variabledimension algor...
详细信息
A continuous deformation algorithm is proposed for solving a variational inequality problem on a polytope K. The algorithm embeds the polytope K into K x [0, infinity) and starts by applying a variable dimension algorithm on K x variable dimension algorithm until an approximate solution is found on K x variable dimension algorithm. Then by tracing the path of solutions of a system of equations the algorithm virtually follows a path of approximate solution in K x [0, infinity). When the path in K x [0, infinity) returns to level 0, i.e., K x variable dimension algorithm, the variable dimension algorithm is again used until a new approximate solution is found on K x variable dimension algorithm. The set K x [0, infinity) is triangulated so that the approximate solution on the path improves the accuracy as the level increases. A contrivance for a practical implementation of the algorithm is proposed and tested for some test problems.
When Merrill's method without an extra dimension is applied to solving sparse or partially separable systems of nonlinear equations, the computational efficiency can be further improved, i.e., a larger piece of li...
详细信息
When Merrill's method without an extra dimension is applied to solving sparse or partially separable systems of nonlinear equations, the computational efficiency can be further improved, i.e., a larger piece of linearity can be traversed in one step by using a suitable linear system. One of the linear systems is updated and the corresponding technique is shown to update information about the linear system and the large piece in the implementation of the method. Some numerical results of the method support the claim that it is efficient. Also, some mistakes from a previous paper, in which the main technique exploiting sparsity was proposed, are corrected.
In this paper we consider the problem of finding zeroes of a continuous function f from a convex, compact subset U of ℝn to ℝn. In the first part of the paper it is proved that f has a computable zero if f:Cn→ℝn sati...
详细信息
Determining whether there is an integer point in an n-dimensional simplex is an NPcomplete problem. In this paper, a new arbitrary starting variable dimension algorithm is developed for computing an integer point of a...
详细信息
Determining whether there is an integer point in an n-dimensional simplex is an NPcomplete problem. In this paper, a new arbitrary starting variable dimension algorithm is developed for computing an integer point of an n-dimensional simplex. The algorithm is derived from an introduction of an integer labeling rule and an application of a triangulation of the space and is composed of two phases, one of which forms a variable dimension algorithm and the other a fulldimension pivoting procedure. Starting at an arbitrary integer point, the algorithm interchanges from one phase to the other if necessary and follows a finite simplicial path that either leads to an integer point of the simplex or proves that no such points exist. An advantage of the algorithm is that all the existing superior triangulations can be its underlying triangulations without any modification.
In a companion paper (A new algorithm to solve calculus of variations problems using Wolfe's convergence theory, Part I: Theory and algorithm), a new algorithm with the properties of guaranteed finite termination ...
详细信息
In a companion paper (A new algorithm to solve calculus of variations problems using Wolfe's convergence theory, Part I: Theory and algorithm), a new algorithm with the properties of guaranteed finite termination and global convergence was proposed to solve calculus of variations problems. A detailed implementation of the algorithm is presented here. The implementation proposes a variabledimension method and incorporates a stable procedure to solve for the descent search direction. Numerical examples are given to illustrate the algorithm.
暂无评论