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

affine-scaling TRAJECTORIES ASSOCIATED WITH A SEMIINFINITE LINEAR PROGRAM

MATHEMATICS OF OPERATIONS RESEARCH 1995年第1期20卷 163-174页

作者： VANDERBEI, RJ Program in Statistics and Operations Research Princeton University Princeton New Jersey 08544

Semi-infinite linear programs often arise as the limit of a sequence of approximating linear programs. Hence, studying the behavior of extensions of linear programming algorithms to semi-infinite problems can yield valuable insight into the behavior of the underlying linear programming algorithm when the number of constraints or the number of variables is very large. In this paper, we study the behavior of the affine-scaling algorithm on a particular semi-infinite linear programming problem. We show that the continuous trajectories converge to the optimal solution but that, for any strictly positive step, there are starting points for which the discrete algorithm converges to nonoptimal boundary points.

关键词： SEMIINFINITE PROGRAMMING affine-scaling algorithms INTERIOR POINT METHODS LINEAR PROGRAMMING THEORY LINEAR PROGRAMMING algorithms

来源：评论

学校读者我要写书评

暂无评论

USING EFFICIENT ANCHORING POINTS FOR GENERATING SEARCH DIRECTIONS IN INTERIOR MULTIOBJECTIVE LINEAR-PROGRAMMING

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 1994年第3期45卷 330-344页

作者： ARBEL, A TEL AVIV UNIV DEPT IND ENGNIL-69978 TEL AVIVISRAEL

This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.

关键词： affine-scaling algorithms INTERIOR-POINT METHODS MULTIOBJECTIVE LINEAR PROGRAMMING (MOLP) MULTICRITERIA DECISION MAKING (MCDM)

来源：评论

学校读者我要写书评

暂无评论

Two-thirds is sharp for affine scaling

引用

Operations Research Letters 1993年第4期13卷 197-197页

作者： Hall, L.A. Vanderbei, R.J. Program in Statistics & Operations Research Princeton University Princeton NJ 08544 USA

Tsuchiya and Muramatsu recently proved that the affine-scaling algorithm for linear programming generates convergent sequences of primal and dual variables whose limits are optimal for the corresponding primal and dual problems as long as the step size is no more than two-thirds of the distance to the nearest face of the polytope. An important feature of this result is that it does not require any nondegeneracy assumptions. In this paper we show that Tsuchiya and Muramatsu's result is sharp by providing a simple linear programming problem for which the sequence of dual variables fails to converge for every step size greater than two-thirds.

关键词： linear programming theory linear programming algorithms affine-scaling algorithms fixed points

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：