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

A POTENTIAL-FUNCTION REDUCTION ALGORITHM FOR SOLVING A linear PROGRAM DIRECTLY FROM AN INFEASIBLE WARM START

MATHEMATICAL programming 1991年第3期52卷 441-466页

作者： FREUND, RM Sloan School of Management Massachusetts Institute of Technology Cambridge USA

This paper develops an algorithm for solving a standard-form linear program directly from an infeasible "warm start", i.e., directly from a given infeasible solution x that satisfies Ax = b but x not greater than or equal to 0. The algorithm is a potential function reduction algorithm, but the potential function is somewhat different than other interior-point method potential functions, and is given by F(x, B) = q ln(c(T)x - B) - SIGMA(j = 1)n. ln(x(j) + h(j)(c(T)x - B) where q = n + square-root n is a given constant, h is a given strictly positive shift vector used to shift the nonnegativity constraints, and B is a lower bound on the optimal value of the linear program. The duality gap c(T)x = B is used both in the leading tem as well as in the barrier term to help shift the nonnegativity constraints. The algorithm is shown under suitable conditions to achieve a constant decrease in the potential function and so achieves a constant decrease in the duality gap (and hence also in the infeasibility) in O(n) iterations. Under more restrictive assumptions regarding the dual feasible region, this algorithm is modified by the addition of a dual barrier term, and will achieve a constant decrease in the duality gap (and in the infeasibility) in O(square-root n) iterations.

关键词： linear PROGRAM POTENTIAL FUNCTION SHIFTED BARRIER interior point ALGORITHM POLYNOMIAL TIME BOUND

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL EXPERIENCE WITH A PRIMAL-DUAL interior point METHOD FOR linear-programming

引用

linear ALGEBRA AND ITS APPLICATIONS 1991年第C期152卷 191-222页

作者： LUSTIG, IJ MARSTEN, RE SHANNO, DF GEORGIA INST TECHNOL SCH IND ENGN & OPERAT RESATLANTAGA 30332 RUTGERS STATE UNIV CTR OPERAT RESNEW BRUNSWICKNJ 08903

A new comprehensive implementation of a primal-dual algorithm for linear programming is described. It allows for easy handling of simple bounds on the primal variables and incorporates free variables, which have not previously been included in a primal-dual implementation. We discuss in detail a variety of computational issues concerning the primal-dual implementation and barrier methods for linear programming in general. We show that, in a certain way, Lustig's method for obtaining feasibility is equivalent to Newton's method. This demonstrates that the method is in some sense the natural way to reduce infeasibility. The role of the barrier parameter in computational practice is studied in detail. Numerical results are given for the entire expanded NETLIB test set for the basic algorithm and its variants, as well as version 5.3 of MINOS.

关键词：

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL ISSUES IN SOLVING LMIS

COMPUTATIONAL ISSUES IN SOLVING LMIS

引用

30TH IEEE CONF ON DECISION AND CONTROL / 1991 ANNUAL MEETING OF THE IEEE CONTROL SYSTEM SOC

作者： BECK, C CALTECH DEPT ELECT ENGN PASADENA CA 91125 USA

ISBN: (纸本)0780304500

Optimization methods which have been applied to LMI (linear matrix inequality) problems are described and results are noted. Descent methods are briefly described, and one descent method approach for solving LMI problems is discussed. Convex programming methods and applications are also outlined. interior point methods are then discussed, and recent results of applications to LMI problems are given.

关键词： Decision theory

来源：评论

学校读者我要写书评

暂无评论

A fast algorithm for power system optimization problems using an interior point method

A fast algorithm for power system optimization problems usin...

引用

Power Industry Computer Application Conference (PICA)

作者： K. Ponnambalam V.H. Quintana A. Vannelli Department of Systems Design Engineering University of Waterloo Waterloo ONT Canada Department of Electrical & Computer Engineering University of Waterloo Waterloo ONT Canada

Variants of simplex-based methodologies are generally used to solve underlying linear programming (LP) problems. An implementation of the dual affine (DA) algorithm (a variant of N. Karmarkar's (1984) interior point method) is described in detail and some computational results are presented. This algorithm is particularly suitable for problems with a large number of constraints, and is applicable to linear and nonlinear optimization problems. In contrast with the simplex method, the number of iterations required by the DA algorithm to solve large-scale problems is relatively small. The DA algorithm has been implemented considering the sparsity of the constraint matrix. The normal equation that is required to be solved in every iteration is solved using a preconditioned conjugate gradient method. An application of the technique to a hydro-scheduling is presented; the largest problem is solved over nine times faster than an efficient simplex (MINOS) code. A new heuristic basis recovery procedure is implemented to provide primal and dual optimal basic solutions which are not generally available if interior point methods are used. The tested examples indicate that this new approach requires less than 10% of the original iterations of the simplex method to find the optimal basis.< >

关键词： Power systems Optimization methods linear programming Design engineering Power engineering and energy Constraint optimization Large-scale systems Testing Systems engineering and theory Power engineering computing

来源：评论

学校读者我要写书评

暂无评论

NEW TRAJECTORY-FOLLOWING POLYNOMIAL-TIME ALGORITHM FOR linear-programming PROBLEMS

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 1989年第3期63卷 433-458页

作者： ROOS, C Department of Mathematics and Informatics/Computer Science Delft University of Technology Delft Holland

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.

关键词： interior point methods linear programming pathfollowing methods polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

MODEL PREDICTIVE CONTROL - theory AND practice - A SURVEY

引用

AUTOMATICA 1989年第3期25卷 335-348页

作者： GARCIA, CE PRETT, DM MORARI, M CALTECH CHEM ENGN206-41PASADENACA 91125 SHELL DEV CO HOUSTONTX 77110

We refer to Model Predictive Control (MPC) as that family of controllers in which there is a direct use of an explicit and separately identifiable model. Control design methods based on the MPC concept have found wide acceptance in industrial applications and have been studied by academia. The reason for such popularity is the ability of MPC designs to yield high performance control systems capable of operating without expert intervention for long periods of time. In this paper the issues of importance that any control system should address are stated. MPC techniques are then reviewed in the light of these issues in order to point out their advantages in design and implementation. A number of design techniques emanating from MPC, namely Dynamic Matrix Control, Model Algorithmic Control, Inferential Control and Internal Model Control, are put in perspective with respect to each other and the relation to more traditional methods like linear Quadratic Control is examined. The flexible constraint handling capabilities of MPC are shown to be a significant advantage in the context of the overall operating objectives of the process industries and the 1-, 2-, and ∞-norm formulations of the performance objective are discussed. The application of MPC to non-linear systems is examined and it is shown that its main attractions carry over. Finally, it is explained that though MPC is not inherently more or less robust than classical feedback, it can be adjusted more easily for robustness.

关键词： (constrained control) Computer control predictive control process control quadratic programming

来源：评论

学校读者我要写书评

暂无评论

INVERSION OF BAND-LIMITED REFLECTION SEISMOGRAMS - theory AND practice

引用

PROCEEDINGS OF THE IEEE 1986年第3期74卷 487-497页

作者： OLDENBURG, DW LEVY, S STINSON, KJ IT&A INVERSE THEORY & APPLICAT INC RICHMOND V6X 1A5 BC CANADA

This paper examines the problem of recovering the acoustic impedance from band-limited normal incidence reflection seismograms. Recognizing the inherent nonuniqueness in the inversion, we proceed by constructing an impedance model which satisfies the processed seismogram, has a minimum of structural variation, honors any point impedance constraints that are provided, and incorporates information from stacking velocities. The constrained inversion is carried out in a single operation using linear programming methods. The constructed impedance is consistent with available geological and geophysical information and therefore constitutes a well-constrained estimate of the true earth impedance. A basic assumption in our inversion is that each seismic trace is a band-limited representation of the true reflectivity function. When seismic data do not conform with this assumption, pre-inversion processing of the data is required; this involves a series of data checks and possible corrections. A complete processing sequence incorporating all steps of the practical inversion is presented and illustrated with field data examples.

关键词： Earth Surface impedance Acoustic reflection Stacking Reflectivity Surface waves Equations Inverse problems Geology Geophysics

来源：评论

学校读者我要写书评

暂无评论

METHOD FOR DETERMINING EQUILIBRIUM STATES OF DYNAMIC-SYSTEMS

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 1977年第3期21卷 299-317页

作者： RED, WE UNIV SW LOUISIANA DEPT MECH ENGNLAFAYETTELA 70501

A heuristic method is presented for determining the equilibrium states of motion of dynamic systems, in particular, spacecraft. The method can also be applied to the solution of sets of linear or nonlinear algebraic equations. A positive-semidefinite functional is formed to convert the problem to that of finding those minimum points where the functional vanishes. The process is initiated within a selecteddomain of interest by random search; convergence to a minimum is obtained by a modified Davidon's deflected gradient technique. To render this approach feasible in the presence of constraints, the functional is modified to include penalty terms which cause the functional to approach infinity at the constraint boundaries. Close approximations to solutions near the constraint boundaries are found by applying Carroll's approach in successively reducing the weighting factors of the penalty terms. After finding a minimum, the local domain around this point is eliminated by adding to the functional an interior constraint term, representing the surface under a hypersphere centered at the minimum point. The domain of consideration now becomes the subdomain formed by subtracting the space contained within this hypersphere from the previous domain of interest. Minima are now sought within the remaining space, as before.

关键词： Aerospace engineering nonlinear programming penalty-function methods singular points variable-metric methods

来源：评论

学校读者我要写书评

暂无评论

interior point Techniques in Optimization 1

引用

丛书名： Applied Optimization

1000年

作者： Benjamin Jansen

ISBN: (数字)9781475755619

ISBN: (纸本)9780792344308;9781441947727

Operations research and mathematical programming would not be as advanced today without the many advances in interior point methods during the last decade. These methods can now solve very efficiently and robustly large scale linear, nonlinear and combinatorial optimization problems that arise in various practical applications. The main ideas underlying interior point methods have influenced virtually all areas of mathematical programming including: analyzing and solving linear and nonlinear programming problems, sensitivity analysis, complexity analysis, the analysis of Newton's method, decomposition methods, polynomial approximation for combinatorial problems etc. This book covers the implications of interior techniques for the entire field of mathematical programming, bringing together many results in a uniform and coherent way. For the topics mentioned above the book provides theoretical as well as computational results, explains the intuition behind the main ideas, gives examples as well as proofs, and contains an extensive up-to-date bibliography.;The book is intended for students, researchers and practitioners with a background in operations research, mathematics, mathematical programming, or statistics.

关键词： Optimization Operations Research/Decision theory theory of Computation Statistics, general

来源：评论

学校读者我要写书评

暂无评论

interior point Approach to linear, Quadratic and Convex programming 1

引用

丛书名： Mathematics and Its Applications

1000年

作者： D. Hertog

ISBN: (数字)9789401111348

ISBN: (纸本)9780792327349;9789401044967

This book describes the rapidly developing field of interior point methods (IPMs). An extensive analysis is given of path-following methods for linear programming, quadratic programming and convex programming. These methods, which form a subclass of interior point methods, follow the central path, which is an analytic curve defined by the problem. Relatively simple and elegant proofs for polynomiality are given. The theory is illustrated using several explicit examples. Moreover, an overview of other classes of IPMs is given. It is shown that all these methods rely on the same notion as the path-following methods: all these methods use the central path implicitly or explicitly as a reference path to go to the optimum.;For specialists in IPMs as well as those seeking an introduction to IPMs. The book is accessible to any mathematician with basic mathematical programming knowledge.

关键词： Optimization Algorithms theory of Computation Convex and Discrete Geometry Numeric Computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：