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

Monotone variable-metric algorithm for linearly constrained nonlinear programming

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2000年第2期104卷 255-279页

作者： Pacelli, G Recchioni, MC Univ Ancona Inst Math & Stat Ancona Italy

A new method for linearly constrained nonlinear programming is proposed. This method follows affine scaling paths defined by systems of ordinary differential equations and it is fully parallelizable. The convergence of the method is proved for a nondegenerate problem with pseudoconvex objective function. In practice, the algorithm works also under more general assumptions on the objective function. Numerical results obtained with this computational method on several test problems are shown.

关键词： nonlinear programming path-following methods differential equations projective algorithms

来源：评论

学校读者我要写书评

暂无评论

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})$; 来源：评论; 学校读者我要写书评

暂无评论

Search directions for a class of projective methods

引用

ZOR Zeitschrift für Operations Research Methods and Models of Operations Research 1990年第5期34卷 353-379页

作者： Zimmermann, U. Abteilung für Mathematische Optimierung Institut für Angewandte Mathematik Technische Universität Carolo-Wilhelmina Braunschweig D-3300 Pockelsstraße 14 Germany

For solving linear programming problems, we describe and evaluate descent directions for projective methods in the setting of the method of de Ghellinck and Vial (1986). It is shown that choosing search directions from the projected simplex centered at 1 in transformed space guarantees a polynomial time bound. In particular, the projection of 1 coincides with the direction chosen by de Ghellinck and Vial (1986) which is well known to be equivalent to Karmarkar's search direction when the initial solution is feasible. Close to that search direction the complexity of the method is unchanged [0(nL) iterations] while in general the bound is 0(n² ·L), where L is the size of the linear programming problem. The investigations were not made in order to improve worst case bounds, but rather to enable a free choice of search directions from a quite large class of "polynomial" directions. We show how different directions can be computed in one iteration using the projection of 1 with relatively small extra computational effort. In projective methods linear programming is reformulated as one-parametric feasibility problem where the parameter is the currently known upper bound on the optimal value. It is therefore very important to improve that bound whenever possible. Generalizing bounds from de Ghellinck and Vial (1986) we prove some infeasibility criteria. In particular, any computed search direction yields some upper bound which eventually improves that currently used. All bounds can be computed by solving sets of simple linear and quadratic equations. © 1990 Physica-Verlag.

关键词： computation of descent directions linear programming polynomial complexity projective algorithms

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还