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

关于线性规划问题熵障碍对偶法的注记

引用

数学的实践与认识 1999年第3期29卷 66-73页

作者：田大钢费奇华中理工大学系统工程研究所武汉430074

线性规划是目标优化问题中最常用的模型。关于大规模线性规划问题的有效求解问题一直受到人们的关注。熵障碍对偶法是继内点法之后,又一解线性规划问题的新的算法。本文讨论了熵障碍对偶法的推广形式及其梯度类算法的收敛性。

关键词：线性规划熵故障对偶法收敛性有效解

来源：评论

学校读者我要写书评

暂无评论

Determinant maximization with linear matrix inequality constraints

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1998年第2期19卷 499-533页

作者： Vandenberghe, L Boyd, S Wu, SP Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA Stanford Univ Dept Elect Engn Informat Syst Lab Stanford CA 94305 USA

The problem of maximizing the determinant of a matrix subject to linear matrix inequalities (LMIs) arises in many fields, including computational geometry, statistics, system identification, experiment design, and information and communication theory. It can also be considered as a generalization of the semidefinite programming problem. We give an overview of the applications of the determinant maximization problem, pointing out simple cases where specialized algorithms or analytical solutions are known. We then describe an interior-point method, with a simplified analysis of the worst-case complexity and numerical results that indicate that the method is very efficient, both in theory and in practice. Compared to existing specialized algorithms (where they are available), the interior-point method will generally be slower;the advantage is that it handles a much wider variety of problems.

关键词： semidefinite programming interior-point methods linear matrix inequalities

来源：评论

学校读者我要写书评

暂无评论

Applications of second-order cone programming

引用

linear ALGEBRA AND ITS APPLICATIONS 1998年第1-3期284卷 193-228页

作者： Lobo, MS Vandenberghe, L Boyd, S Lebret, H Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90024 USA Stanford Univ Dept Elect Engn Informat Syst Lab Stanford CA 94305 USA Ecole Natl Super Tech Avancees Paris France

In a second-order cone program (SOCP) a linear function is minimized over the intersection of an affine set and the product of second-order (quadratic) cones. SOCPs are nonlinear convex problems that include linear and (convex) quadratic programs as special cases, but are less general than semidefinite programs (SDPs). Several efficient primal-dual interior-point methods for SOCP have been developed in the last few years. After reviewing the basic theory of SOCPs, we describe general families of problems that can be recast as SOCPs. These include robust linear programming and robust least-squares problems, problems involving sums or maxima of norms, or with convex hyperbolic constraints. We discuss a variety of engineering applications, such as filter design, antenna array weight design, truss design, and grasping force optimization in robotics. We describe an efficient primal-dual interior-point method for solving SOCPs, which shares many of the features of primal-dual interior-point methods for linear program-ming (LP): Worst-case theoretical analysis shows that the number of iterations required to solve a problem grows at most as the square root of the problem size, while numerical experiments indicate that the typical number of iterations ranges between 5 and 50, almost independent of the problem size. (C) 1998 Elsevier Science Inc. All rights reserved.

关键词： convex optimization quadratic programming semidefinite programming interior-point methods

来源：评论

学校读者我要写书评

暂无评论

Proximal methods in view of interior-point strategies

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 1998年第2期98卷 399-429页

作者： Kaplan, A Tichatschke, R Tech Univ Darmstadt Dept Math D-64287 Darmstadt Germany Univ Trier Dept Math 4 Trier Germany

This paper deals with regularized penalty-barrier methods for convex programming problems. In the spirit of an iterative proximal regularization approach, an interior-point method is constructed, in which at each step a strongly convex function has to be minimized and the prox-term can be scaled by a variable scaling factor. The convergence of the method is studied for an axiomatically given class of barrier functions. According to the results, a wide class of barrier functions (in particular, logarithmic and exponential functions) can be applied to design special algorithms. For the method with a logarithmic barrier, the rate of convergence is investigated and assumptions that ensure linear convergence are given.

关键词： interior-point methods convex optimization ill-posed problems proximal point algorithms

来源：评论

学校读者我要写书评

暂无评论

On two interior-point mappings for nonlinear semidefinite complementarity problems

引用

MATHEMATICS OF OPERATIONS RESEARCH 1998年第1期23卷 39-60页

作者： Monteiro, RDC Pang, JS Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Johns Hopkins Univ Dept Math Sci Baltimore MD 21218 USA

Extending our previous work (Monteiro and Pang 1996), this paper studies properties of two fundamental mappings associated with the family of interior-point methods for solving monotone nonlinear complementarity problems over the cone of symmetric positive semidefinite matrices. The first of these maps lead to a family of new continuous trajectories which include the central trajectory as a special case. These trajectories completely "fill up" the set of interior feasible points of the problem in the same way as the weighted central paths do the interior of the feasible region of a linear program. Unlike the approach based on the theory of maximal monotone maps taken by Shida and Shindoh(1996) and Shida, Shindoh, and Kojima (1995), our approach is based on the theory of local homeomorphic maps in nonlinear analysis.

关键词： interior point methods mixed nonlinear complementarity problems generalized complementarity problems maximal monotonicity monotone mappings continuous trajectories weighted central path nonlinear semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

On some properties of generalized proximal point methods for variational inequalities

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 1998年第2期96卷 337-362页

作者： Iusem, AN Inst Matemat Pura & Aplicada Rio De Janeiro Brazil

We discuss here generalized proximal point methods applied to variational inequality problems. These methods differ from the classical point method in that a so-called Bregman distance substitutes for the Euclidean distance and forces the sequence generated by the algorithm to remain in the interior of the feasible region, assumed to be nonempty. We consider here the case in which this region is a polyhedron (which includes linear and nonlinear programming, monotone linear complementarity problems, and also certain nonlinear complementarity problems), and present two alternatives to deal with linear equality constraints. We prove that the sequences generated by any of these alternatives, which in general are different, converge to the same point, namely the solution of the problem which is closest, in the sense of the Bregman distance, to the initial iterate, for a certain class of operators. This class consists essentially of point-to-point and differentiable operators such that their Jacobian matrices are positive semidefinite (not necessarily symmetric) and their kernels are constant in the feasible region and invariant through symmetrization. For these operators, the solution set of the problem is also a polyhedron. Thus, we extend a previous similar result which covered only linear operators with symmetric and positive-semidefinite matrices.

关键词： proximal point methods generalized distances variational inequalities interior point methods linear complementarity problems nonlinear complementarity problems

来源：评论

学校读者我要写书评

暂无评论

On effectively computing the analytic center of the solution set by primal-dual interior-point methods

引用

SIAM JOURNAL ON OPTIMIZATION 1998年第1期8卷 1-25页

作者： Gonzalez, MD Tapia, RA Potra, FA Univ Simon Bolivar Dept Comp Cient & Estadist Caracas 1080A Venezuela Univ Simon Bolivar Ctr Estadist & Software Matemat Caracas 1080A Venezuela Rice Univ Dept Computat & Appl Math Houston TX 77251 USA Rice Univ Ctr Res Parallel Computat Houston TX 77251 USA Univ Iowa Dept Math Iowa City IA 52242 USA Univ Iowa Dept Comp Sci Iowa City IA 52242 USA

The computation of the analytic center of the solution set can be important in linear programming applications where it is desirable to obtain a solution that is not near the relative boundary of the solution set. In this work we discuss the effective computation of the analytic center solution by the use of primal-dual interior-point methods. A primal-dual interior-point algorithm designed for effectively computing the analytic-center solution is proposed, and theory and numerical results are presented.

关键词： primal-dual interior-point algorithm analytic-center solution linear programming

来源：评论

学校读者我要写书评

暂无评论

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

引用

MATHEMATICAL programming 1998年第1期81卷 1-21页

作者： Todd, MJ Ye, YY Cornell Univ Sch Operat Res & Ind Engn Engn & Theory Ctr Ithaca NY 14853 USA Univ Iowa Dept Management Sci Iowa City IA 52242 USA

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primal-dual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain "certificates" that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. (C) 1998 The Mathematical programming Society, Inc. Published by Elsevier Science B.V.

关键词： linear programming Farkas lemma infeasible-interior-point methods stopping rules

来源：评论

学校读者我要写书评

暂无评论

Adaptive algorithms for sequential linear and quadratic programming with interior-point methods and fuzzy heuristics

Adaptive algorithms for sequential linear and quadratic prog...

引用

作者： Mulkay, Eric Layne Purdue University

学位级别：Ph.D.

interior-point algorithms are a new class of optimization routines which exhibit several theoretical and practical advantages over other methods for linear and quadratic programming. One goal of this work was to investigate the question of whether interior-point methods would prove as efficient when used to solve nonlinear engineering design problems. This was tested by using a primal-dual interior-point solver in sequential linear programming and sequential quadratic programming paradigms. The results show that interior-point methods do perform well for large-scale nonlinear engineering optimization. interior-point methods take fewer iterations in less time to solve large-scale problems than simplex-based algorithms, and are immune to constraint degeneracy. These two features make interior-point methods well suited to engineering optimization. A second focus of this work was the development of fuzzy heuristics to make the sequential linear and quadratic programming algorithms adaptable. While most optimization algorithms are derived from mathematical theory, certain algorithm parameters are often chosen from some acceptable range of values based on a programmer's judgement. Fuzzy logic was chosen to adaptively modify these values "on-the-fly". The resulting adaptive sequential linear programming algorithm not only performed better than the original sequential liner programming algorithm, but also performed as well or better than state-of-the-art sequential quadratic programming algorithms when solving large-scale problems. The simplicity of the sequential linear programming algorithm, coupled with adaptability from the fuzzy rules resulted in a robust, high-performance algorithm.

关键词：

来源：评论

学校读者我要写书评

暂无评论

An interior random vector algorithm for multistage stochastic linear programs

引用

SIAM JOURNAL ON OPTIMIZATION 1998年第4期8卷 956-972页

作者： Schweitzer, E Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

In this paper, an interior point algorithm for linear programs is adapted for solving multistage stochastic linear programs. The algorithm is based on Monteiro and Adler's path-following algorithm for deterministic linear programs. In practice, the complexity of the algorithm is linear with respect to the size of the sample space. The algorithm starts from a feasible solution of the problem and proceeds along a path of random vectors. The cubic polynomial complexity of the algorithm for deterministic linear programs is derived from the calculations of the Newton steps. In the algorithm developed in this paper, the probabilistic structure of the problem is taken into consideration while calculating a Newton step and the size of the sample space appears linearly in the complexity. The development of an algorithm that requires a relatively small number of arithmetic operations, in terms of the sample space size, allows the use of the algorithm for multistage stochastic linear programs with a very large number of scenarios.

关键词： stochastic programming multistage linear programs interior point methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：