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

A Monotonic projective algorithm for Fractional Linear Programming

algorithmICA 1986年第1-4期1卷 483-498页

作者： Anstreicher, Kurt M. Yale Univ Sch Management New Haven CT 06520 USA

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.

关键词： Linear programming Fractional linear programming Karmarkar's algorithm projective algorithm

来源：评论

学校读者我要写书评

暂无评论

STRICT MONOTONICITY AND IMPROVED COMPLEXITY IN THE STANDARD FORM projective algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1993年第3期62卷 517-535页

作者： ANSTREICHER, KM UNIV CATHOLIQUE LOUVAIN CTR OPERAT RES & ECONOMETRB-1348 LOUVAINBELGIUM

In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve O(square-root n L) step complexity, opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.

关键词： LINEAR PROGRAMMING KARMARKAR algorithm projective algorithm STANDARD FORM

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPUTATION OF WEIGHTED ANALYTIC CENTERS AND DUAL ELLIPSOIDS WITH THE projective algorithm

引用

MATHEMATICAL PROGRAMMING 1993年第1期60卷 81-92页

作者： GOFFIN, JL VIAL, JP UNIV GENEVA DEPT ECON COMMERCIALE & IND CH-1211 GENEVA 4 SWITZERLAND

The primal projective algorithm for linear programs with unknown optimal objective function value is extended to the case where one uses a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimum. The minimization of this potential when the lower bound is kept fixed, yields a primal and a dual feasible solution. The dual solution is the weighted analytic center of a certain dual polytope. Finally one exhibits a pair of homothetic dual ellipsoids that extends results obtained by Sonnevend, Todd, Ye, Freund and Anstreicher.

关键词： projective algorithm ANALYTIC CENTERS DUAL ELLIPSOIDS

来源：评论

学校读者我要写书评

暂无评论

ON ANSTREICHERS COMBINED PHASE-I PHASE-II projective algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1992年第1期55卷 1-15页

作者： TODD, MJ 1. School of Operations Research and Industrial Engineering College of Engineering Cornell University 14853 Ithaca NY USA

Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.

关键词： LINEAR PROGRAMMING INTERIOR-POINT METHOD projective algorithm COMBINING PHASE-I PHASE-II

来源：评论

学校读者我要写书评

暂无评论

A COMBINED PHASE-I PHASE-II projective algorithm FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1989年第2期43卷 209-223页

作者： ANSTREICHER, KM 1.Yale School of Organization and Management Box 1A 06520 New Haven CT USA

We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasible) standard form linear program, without the addition of any “bigM“ terms or conversion to a primal-dual problem.

关键词： Linear programming Karmarkar's algorithm projective algorithm artificial variable phase I

来源：评论

学校读者我要写书评

暂无评论

SHORT STEPS WITH KARMARKARS projective algorithm FOR LINEAR-PROGRAMMING

引用

SIAM JOURNAL ON OPTIMIZATION 1994年第1期4卷 193-207页

作者： GOFFIN, JL VIAL, JP MCGILL UNIV FAC MANAGEMENTMONTREAL H3A 165PQCANADA DEPT ECON COMMERCIALE & IND CH-1211 GENEVA 4SWITZERLAND

A path-following, or short-step, version of Karmarkar's algorithm is proposed. When the first term of Karmarkar's potential function is given the weight (n + n(delta)), with delta greater than or equal to 0, the algorithm converges in O(n(max{delta/2,1-delta/2})L) iterations. The best convergence result O(root nL) is achieved for delta = 1. Two proofs of convergence are given: one based on duality gap reductions and the other on potential reductions. The weighted version of the standard projective algorithm is also analyzed. It is interpreted as a max-step algorithm. It is known to converge in at most O((n + n(delta))L) iterations. The reduction of the duality gap when an updating of the lower bound is performed is studied. It is shown to be of a multiplicative factor at most equal to 1 - n(delta)/(n + n(delta))(1 - theta), where 0 < theta < 1 is a fixed parameter in the algorithm. It is deduced from it that the total number of updates of the lower bound in the weighted projective algorithm is at most O(n(1-delta))L) for 0 less than or equal to delta less than or equal to 1.

关键词： LINEAR PROGRAMMING INTERIOR POINT METHOD projective algorithm PATH FOLLOWING

来源：评论

学校读者我要写书评

暂无评论

DECOMPOSITION AND NONDIFFERENTIABLE OPTIMIZATION WITH THE projective algorithm

引用

MANAGEMENT SCIENCE 1992年第2期38卷 284-302页

作者： GOFFIN, JL HAURIE, A VIAL, JP ECOLE HAUTES ETUD COMMERCIALES MONTREAL GERADMONTREALQUEBECCANADA UNIV GENEVA DEPT ECON COMMERCIALE & INDCH-1211 GENEVA 4SWITZERLAND

This paper deals with an application of a variant of Karmarkar's projective algorithm for linear programming to the solution of a generic nondifferentiable minimization problem. This problem is closely related to the Dantzig-Wolfe decomposition technique used in large-scale convex programming. The proposed method is based on a column generation technique defining a sequence of primal linear programming maximization problems. Associated with each problem one defines a weighted potential function which is minimized using a variant of the projective algorithm. When a point close to the minimum of the potential function is reached, a corresponding point in the dual space is constructed, which is close to the analytic center of a polytope containing the solution set of the nondifferentiable optimization problem. An admissible cut of the polytope, corresponding to a new supporting hyperplane of the epigraph of the function of minimize, is then generated at this approximate analytic center. In the primal space this new cut translates into a new column for the associated linear programming problem. The algorithm has performed well on a set of convex nondifferentiable programming problems.

关键词： projective algorithm INTERIOR POINT METHOD CUTTING PLANE DECOMPOSITION NONDIFFERENTIABLE OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

A PRIMAL projective INTERIOR POINT METHOD FOR LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1991年第1期51卷 17-43页

作者： GOLDFARB, D XIAO, D 1. Department of Industrial Engineering and Operations Research Columbia University 10027 New York NY USA

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.

关键词： INTERIOR POINT METHODS LINEAR PROGRAMMING FRACTIONAL LINEAR PROGRAMMING projective algorithm KARMARKARS algorithm POLYNOMIAL-TYPE algorithm

来源：评论

学校读者我要写书评

暂无评论

SEARCH DIRECTIONS FOR INTERIOR LINEAR-PROGRAMMING METHODS

引用

algorithmICA 1991年第2期6卷 153-181页

作者： GONZAGA, CC 1. Department of Electrical Engineering and Computer Sciences University of California 94720 Berkeley CA USA

Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. This paper examines several search directions in a common framework that does not need any problem transformation. These directions prove to be combinations of two problem-dependent vectors, and can all be improved by a bidirectional search procedure. We conclude that there are essentially two polynomial algorithms: Karmarkar's method and the algorithm that follows a central trajectory, and they differ only in a choice of parameters (respectively lower bound and penalty multiplier).

关键词： KARMARKAR algorithm LINEAR PROGRAMMING projective algorithm CONICAL PROJECTION INTERIOR METHODS

来源：评论

学校读者我要写书评

暂无评论

A path-following version of the Todd-Burrell procedure for linear programming

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 1997年第2期46卷 153-167页

作者： Vial, JP Univ Geneva LOGILAB Management Studies CH-1211 Geneva 4 Switzerland

We propose a path-following version of the Todd-Burrell procedure to solve linear programming problems with an unknown optimal value. The path-following scheme is not restricted to Karmarkar's primal step;it can a... 详细信息

关键词： projective algorithm path-following interior point method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：