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

THE PRIMAL-DUAL potential reduction ALGORITHM FOR POSITIVE SEMI-DEFINITE PROGRAMMING

Journal of Computational Mathematics 2003年第3期21卷 339-346页

作者： Si-ming Huang(Institute of Policy and Management, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 100080, China) Institute of Policy and Management Academy of Mathematics and System Sciences Chinese Academy of Sciences 北京 100080

In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. The complexity of the algorithm is either O(nlog(X0 · S0/ε) or O(nlog(X0· S0/ε) depends on the value of ρ in the primal-dual potential function, where X0 and S0 is the initial interior matrices of the positive semi-definite programming.

关键词： Positive semi-definite programming potential reduction algorithms Complexity.

来源：评论

学校读者我要写书评

暂无评论

On the worst case complexity of potential reduction algorithms for linear programming

引用

MATHEMATICAL PROGRAMMING 1997年第3期77卷 321-333页

作者： Bertsimas, D Luo, XD MIT CTR OPERAT RESCAMBRIDGEMA 02139

There are several classes of interior point algorithms that solve linear programming problems in O(root L) iterations, Among them, several potential reduction algorithms combine both theoretical (O(root L) iterations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity bounds. In the present paper we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we allow line searches in the potential function, and even for problems that have network structure, the bound O(root nL) is tight for several potential reduction algorithms, i.e., there is a class of examples with network structure, in which the algorithms need at least Omega(root nL) iterations to find an optimal solution. (C) 1997 The Mathematical Programming Society, Inc.

关键词： interior point methods lower bounds on complexity potential reduction algorithms

来源：评论

学校读者我要写书评

暂无评论

On the length of primal-dual projection of potential reduction algorithm

引用

Optimization 1995年第2期34卷 161-171页

作者： Huang, S. Kortanek, K.O. Department of Information and Systems Management School of Business and Management Hong Kong University of Science and Technology Kowloon Clear Water Bay Hong Kong Department of Management Science College of Business University of Iowa Iowa City Iowa 52242 United States

The length of projection of search directions takes an important role in analyzing the complexity of potential reduction algorithms. We show, in this paper, that the length of the projection is bounded below by 1/4 if... 详细信息

, and is greater than or equal to one if, where p is a parameter in

关键词： Linear programming potential reduction algorithms Projection

来源：评论

学校读者我要写书评

暂无评论

A GLOBALLY CONVERGENT PRIMAL DUAL INTERIOR-POINT ALGORITHM FOR CONVEX-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1994年第2期64卷 123-147页

作者： MONTEIRO, RDC Systems and Industrial Engineering Department University of Arizona Tucson USA

In this paper, we study the global convergence of a large class of primal-dual interior point algorithms for solving the linearly constrained convex programming problem. The algorithms in this class decrease the value of a primal-dual potential function and hence belong to the class of so-called potential reduction algorithms. An inexact line search based on Armijo stepsize rule is used to compute the stepsize. The directions used by the algorithms are the same as the ones used in primal-dual path following and potential reduction algorithms and a very mild condition on the choice of the ''centering parameter'' is assumed. The algorithms always keep primal and dual feasibility and, in contrast to the polynomial potential reduction algorithms, they do not need to drive the value of the potential function towards - infinity in order to converge. One of the techniques used in the convergence analysis of these algorithms has its root in nonlinear unconstrained optimization theory.

关键词： INTERIOR-POINT METHODS CONVEX PROGRAMMING KARMARKAR ALGORITHM GLOBAL CONVERGENCE potential FUNCTION potential reduction algorithms ARMIJO STEPSIZE RULE

来源：评论

学校读者我要写书评

暂无评论

ON ADAPTIVE-STEP PRIMAL-DUAL INTERIOR-POINT algorithms FOR LINEAR-PROGRAMMING

引用

MATHEMATICS OF OPERATIONS RESEARCH 1993年第4期18卷 964-981页

作者： MIZUNO, S TODD, MJ YE, YY CORNELL UNIV SCH OPERAT RES & IND ENGNITHACANY 14853 UNIV IOWA DEPT MANAGEMENT SCIIOWA CITYIA 52242

We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice than guaranteed by the worst-case estimates, based on an analysis using a nonrigorous probabilistic assumption.

关键词： LINEAR PROGRAMMING INTERIOR POINT algorithms PATH-FOLLOWING algorithms potential reduction algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE CONTINUOUS TRAJECTORIES FOR A potential reduction ALGORITHM FOR LINEAR-PROGRAMMING

引用

MATHEMATICS OF OPERATIONS RESEARCH 1992年第1期17卷 225-253页

作者： MONTEIRO, RDC AT&T BELL LABS HOLMDELNJ 07733

For a possibly degenerate linear program min x{c(T)x;Ax = b, x greater-than-or-equal-to 0} (A is an m X n real matrix, b is-an-element-of R(m) and c is-an-element-to R(n)), whose optimal value is 0, we study the limiting behavior of the trajectories of the family of vector fields [GRAPHICS] for all values of q greater-than-or-equal-to n, where X is the diagonal matrix associated with x and P(AX) is the projection operator onto the null space of AX. A polynomial algorithm based on the directions PHI(q)(x) has been presented by Gonzaga [6] when q = n or q = n + square-root n . We show that all trajectories of PHI(q)(x) converge to the unique "center" of the optimal face of the given linear program. When this face consists of a unique vertex, it is shown that any trajectory of PHI(q)(x) approaches this vertex along the same direction. When the optimal face consists of more than one point, we show that there is a threshold value tau > 0 such that: for q > tau, "most" of the trajectories of PHI(q)(x) converge to the "center" tangentially to the optimal face and that the direction of approach of a trajectory of PHI(q)(x) depends on the initial condition;for q < tau (q = tau), the trajectories of PHI(q)(x) converge to the "center" along a unique direction (along several directions which depend on the initial condition) forming a positive angle with the optimal face.

关键词： INTERIOR POINT algorithms LINEAR PROGRAMMING KARMARKAR ALGORITHM CONTINUOUS TRAJECTORIES FOR LINEAR PROGRAMMING potential reduction algorithms potential FUNCTION

来源：评论

学校读者我要写书评

暂无评论

A CLASS OF PROJECTIVE TRANSFORMATIONS FOR LINEAR-PROGRAMMING: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1990年第3期19卷 457-466页; 作者： YE, YY Univ of Iowa IA United States; A class of projective transformations under which potential functions are invariant for linear programming is described. As a result, a new projective algorithm converging in O(Ln<span style="position: absolut... 详细信息; A class of projective transformations under which potential functions are invariant for linear programming is described. As a result, a new projective algorithm converging in $O (L \sqrt{n})$; 来源：评论; 学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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