检索结果-内蒙古大学图书馆

A simplicial algorithm FOR THE NONLINEAR STATIONARY POINT PROBLEM ON AN UNBOUNDED POLYHEDRON

SIAM JOURNAL ON OPTIMIZATION 1991年第2期1卷 151-165页

作者： Dai, Y. Van der Laan, G. Talman, A. J. J. Yamamoto, Y. Univ Tsukuba Inst Socio Econ Planning Tsukuba Ibaraki 305 Japan Vrije Univ Amsterdam Dept Econometr NL-1007 MC Amsterdam Netherlands Tilburg Univ Dept Econometr NL-5000 LE Tilburg Netherlands

A path-following algorithm is proposed for finding a solution to the nonlinear stationary point problem on an unbounded, convex, and pointed polyhedron. The algorithm can start at an arbitrary point of the polyhedron. The path to be followed by the algorithm is described as the path of zeros of some piecewise continuously differentiable function defined on an appropriate subdivided manifold. This manifold is induced by a generalized primal-dual pair of subdivided manifolds. The path of zeros can be approximately followed by dividing the polyhedron into simplices and replacing the original function by its piecewise linear approximation with respect to this subdivision. The piecewise linear path of this function can be generated by alternating replacement steps and linear programming pivot steps. A condition under which the path of zeros converges to a solution is also stated, and a description of how the algorithm operates when the problem is linear or when the polyhedron is the Cartesian product of a polytope and an unbounded polyhedron is given.

关键词： simplicial algorithm stationary point problem subdivided manifold convergence condition

来源：评论

学校读者我要写书评

暂无评论

A simplicial algorithm for the nonlinear complementarity problem

引用

Mathematical Programming 1974年第1期6卷 281-300页

作者： Fisher, M.L. Gould, F.J. University of Chicago Chicago Ill. United States

A triangulation of the nonnegative orthant and a special labeling of the vertices lead to a combinatorial procedure for seeking solutions or approximate solutions to the nonlinear complementarity problem under coercive-like assumptions on the problem functions. Derivatives are not required. Convergence is proved, computational considerations are discussed, and some preliminary applications to convex programming and saddle point computation, along with numerical results, are presented. © 1974, The Mathematical Programming Society. All rights reserved.

关键词： Approximate Solution Mathematical Method Saddle Point Complementarity Problem simplicial algorithm

来源：评论

学校读者我要写书评

暂无评论

The (n + 1)2^m-ray algorithm: a new simplicial algorithm for the variational inequality problem on ℝ₊^m×Sⁿ

引用

Annals of Operations Research 1993年第1期44卷 93-113页

作者： Yamamoto, Yoshitsugu Yang, Zaifu Institute of Socio-Economic Planning University of Tsukuba Tsukuba Ibaraki 305 Japan Department of Econometrics Tilburg University Tilburg 5000 LE Netherlands

In this paper we propose a variable dimension simplicial algorithm for solving the variational inequality problem on the cross product of the nonnegative orthant ℝ+m of the m-dimensional Euclidean space ℝm and the n-d... 详细信息

In this paper we propose a variable dimension simplicial algorithm for solving the variational inequality problem on the cross product of the nonnegative orthant ℝ₊^m of the m-dimensional Euclidean space ℝ^m and the n-dimensional unit simplex Sⁿ of ℝⁿ⁺¹. Starting from an arbitrary point (u, v) j{cyrillic, ukrainian}ℝ₊^m×Sⁿ, the algorithm generates a piecewise linear path in ℝ₊^m×Sⁿ. The path is traced by making alternately linear programming pivot operations and replacement steps in an appropriate simplicial subdivision of ℝ₊^m×Sⁿ. The algorithm differs from the thus far known algorithm in the number of directions in which it may leave the starting point. More precisely, the algorithm has (n+1)2^m rays to leave the starting point whereas the existing algorithm has n+m+1 rays. A convergence condition is presented and the accuracy estimation of an approximate solution generated is also given. © 1993 J.C. Baltzer AG, Science Publishers.

关键词： convergence condition nonlinear complementarity problem piecewise linear approximation simplicial algorithm triangulation Variational inequality problem

来源：评论

学校读者我要写书评

暂无评论

An Arbitrary Starting simplicial algorithm for Constructively Proving Tarski’s Fixed Point Theorem on an n-dimensional Box

An Arbitrary Starting Simplicial Algorithm for Constructivel...

引用

第七届运筹学及其应用国际研讨会

作者： Chuangyin Dang Dept. of Manufacturing Engineering ＆ Engineering Management City University of Hong Kong

The well-known Tarski’s fixed point theorem asserts that an increasing mapping from an n-dimensional box to itself has a fixed point. In this paper, a constructive proof of this theorem is obtained from an application of the （n+1）-ray arbitrary starting simplicial algorithm. The algorithm assigns an integer label to each point of the box and employs a triangulation to subdivide the box into simplices. For any given mesh size of the triangulation, starting from an arbitrary interior point of the box, the algorithm generates within a finite number of iterations a complete n-dimensional simplex, any point of which yields an approximate fixed point. If the accuracy is not good enough, the mesh size of the triangulation is refined and the algorithm is restarted. When the mesh size goes to zero sequentially, one will obtain a sequence of approximate fixed points satisfying that every limit point of the sequence is a fixed point.

关键词： Increasing Mapping Fixed Point Tarski’s Fixed Point Theorem Constructive Proof Integer Labeling Triangulation simplicial algorithm

来源：评论

学校读者我要写书评

暂无评论

simplicial APPROXIMATION OF SOLUTIONS TO THE NONLINEAR COMPLEMENTARITY-PROBLEM WITH LOWER AND UPPER-BOUNDS

引用

MATHEMATICAL PROGRAMMING 1987年第1期38卷 1-15页

作者： VANDERLAAN, G TALMAN, AJJ TILBURG UNIV DEPT ECONOMETR5000 LE TILBURGNETHERLANDS

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR n developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solvin... 详细信息

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR ⁿ developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the2n-ray zero point finding algorithm onR ⁿ. It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables.

关键词： simplicial algorithm triangulation nonlinear complementarity problem

来源：评论

学校读者我要写书评

暂无评论

EFFICIENCY AND IMPLEMENTATION OF simplicial ZERO-POINT algorithmS

引用

MATHEMATICAL PROGRAMMING 1984年第2期30卷 196-217页

作者： VANDERLAAN, G SEELEN, LP Department of Actuarial Sciences and Econometrics Vrije Universiteit De Boelelaan 1081 1081 HV Amsterdam The Netherlands

In this paper we compare the efficiency of several simplicial variable dimension algorithms. To do so, we first treat the issues of degeneracy and accelerating. We present a device for solving degeneracy. Furthermore we compare several accelerating techniques. The technique of iterated quasi-Newton steps after each major cycle of the simplicial algorithm is implemented in a computer code, which is used to compare the efficiency of the (n+1)-ray, 2n-ray, 2n-ray and (3n−1)-ray algorithms. Except for the (n+1)-ray algorithm, the number of function evaluations does not differ very much between the various algorithms. It appeared, however, that the 2n-algorithm needs considerably less computation time.

关键词： simplicial algorithm Zero Point Linear Programming Step Efficiency

来源：评论

学校读者我要写书评

暂无评论

Variational inequality problems with a continuum of solutions: Existence and computation

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2001年第6期39卷 1852-1873页

作者： Herings, PJJ Talman, D Yang, ZF Univ Maastricht Dept Econ NL-6200 MD Maastricht Netherlands Tilburg Univ Dept Econometr & CentER NL-5000 LE Tilburg Netherlands Yokohama Natl Univ Fac Business Adm Yokohama Kanagawa 2408501 Japan

In this paper three sufficient conditions are provided under each of which an upper semicontinuous point-to-set mapping defined on an arbitrary polytope has a connected set of zero points that connect two distinct faces of the polytope. Furthermore, we obtain an existence theorem of a connected set of solutions to a nonlinear variational inequality problem over arbitrary polytopes. These results follow in a constructive way by designing a new simplicial algorithm. The algorithm operates on a triangulation of the polytope and generates a piecewise linear path of points connecting two distinct faces of the polytope. Each point on the path is an approximate zero point. As the mesh size of the triangulation goes to zero, the path converges to a connected set of zero points linking the two distinct faces. As a consequence, our results generalize Browder's fixed point theorem [ Summa Brasiliensis Mathematicae, 4 (1960), pp. 183-191] and an earlier result by the authors [ Math. Oper. Res., 21 (1996), pp. 675-696] on the n-dimensional unit cube. An application in economics and some numerical examples are also discussed.

关键词： polytope simplicial algorithm continuum of zero points system of nonlinear equations variational inequality economic equilibrium model

来源：评论

学校读者我要写书评

暂无评论

A vector labeling method for solving discrete zero point and complementarity problems

引用

SIAM JOURNAL ON OPTIMIZATION 2007年第1期18卷 290-308页

作者： Van Der Laan, Gerard Talman, Dolf Yang, Zaifu Vrije Univ Amsterdam Dept Econometr NL-1081 HV Amsterdam Netherlands Vrije Univ Amsterdam Tinbergen Inst NL-1081 HV Amsterdam Netherlands Tilburg Univ Dept Econometr & Operat NL-5000 LE Tilburg Netherlands Tilburg Univ CentER NL-5000 LE Tilburg Netherlands Yokohama Natl Univ Fac Business Adm Yokohama Kanagawa 2408501 Japan

In this paper we establish the existence of a discrete zero point of a function from the n-dimensional integer lattice Z(n) to the n-dimensional Euclidean space R-n under very general conditions with respect to the behavior of the function. The proof is constructive and uses a combinatorial argument based on a simplicial algorithm with vector labeling and lexicographic linear programming pivot steps. The algorithm provides an efficient method to find an exact solution. We also discuss how to adapt the algorithm for two related problems, namely, to find a discrete zero point of a function under a general antipodal condition and to find a solution to a discrete nonlinear complementarity problem. In both cases the modified algorithm provides a constructive existence proof, too. We further show that the algorithm for the discrete nonlinear complementarity problem generalizes the well-known Lemke's method to nonlinear environments. An economic application is also presented.

关键词： integer lattice zero point vector labeling rule simplicial algorithm discrete complementarity

来源：评论

学校读者我要写书评

暂无评论

Existence and approximation of robust solutions of variational inequality problems over polytopes

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1999年第2期37卷 333-352页

作者： Van Der Laan, G Talman, D Yang, Z Free Univ Amsterdam Dept Econometrics NL-1081 HV Amsterdam Netherlands Tilburg Univ Dept Econometrics & Ctr NL-5000 LE Tilburg Netherlands Yokohama Natl Univ Fac Business Adm Yokohama Kanagawa 2400067 Japan

We study nonlinear variational inequality problems over polytopes from a viewpoint of stability and propose a new solution concept. Extending an earlier concept proposed by Yang [Z. Yang, SIAM J. Control Optim., 34 (1996), pp. 491-506] on the unit simplex, we will introduce the concept of the robust stationary point, which is a refinement of the concept of the stationary point. Though a stationary point need not be robust, it is shown that every continuous function on a polytope has a robust stationary point. We develop a simplicial algorithm to compute a robust stationary point of a continuous function on a polytope. The algorithm can be briefly stated as follows. Starting with any point in the relative interior of a polytope, the algorithm generates a piecewise linear path which leads to an approximate robust stationary point of any a priori chosen accuracy within a finite number of steps. Moreover, we also discuss several numerical examples and apply the new concept to noncooperative games and economic equilibrium problems.

关键词： variational inequality problem robust stationary point polytopes simplicial algorithm fixed points stability Nash equilibrium Walrasian equilibrium

来源：评论

学校读者我要写书评

暂无评论

Solving discrete zero point problems

引用

MATHEMATICAL PROGRAMMING 2006年第1期108卷 127-134页

作者： Van der Laan, G. Talman, D. A. J. J. Yang, Z. Vrije Univ Amsterdam Dept Econometr NL-1081 HV Amsterdam Netherlands Vrije Univ Amsterdam Tinbergen Inst NL-1081 HV Amsterdam Netherlands Tilburg Univ Dept Econometr & Operat Res NL-5000 LE Tilburg Netherlands Tilburg Univ CentER NL-5000 LE Tilburg Netherlands Yokohama Natl Univ Fac Business Adm Yokohama Kanagawa 2408501 Japan

In this paper we present two theorems on the existence of a discrete zero point of a function from the n-dimensional integer lattice Z(n) to the n-dimensional Euclidean space R-n. The theorems differ in their boundary conditions. For both theorems we give a proof using a combinatorial lemma and present a constructive proof based on a simplicial algorithm that finds a discrete zero point within a finite number of steps.

关键词： discrete zero point labeling rule simplicial algorithm triangulation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：