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

Improved complexity using higher-order correctors for primal-dual Dikin affine scaling

MATHEMATICAL programming 1997年第1期76卷 117-130页

作者： Jansen, B Roos, C Terlaky, T Ye, Y DELFT UNIV TECHNOL FAC TECH MATH & INFORMATNL-2600 GA DELFTNETHERLANDS UNIV IOWA DEPT MANAGEMENT SCIIOWA CITYIA 52242

In this paper we show that the primal-dual Dikin affine scaling algorithm for linear programming of Jansen, Roos and Terlaky enhances an asymptotical O(root nL) complexity by using corrector steps, We also show that t... 详细信息

关键词： linear programming interior-point algorithm affine scaling complexity

来源：评论

学校读者我要写书评

暂无评论

interior point Algorithms: theory and Analysis 1

引用

丛书名： Wiley-Interscience Series in Discrete Mathematics and Optimization

1997年

作者： Yinyu Ye

ISBN: (数字)9781118032701

ISBN: (纸本)9780471174202

The first comprehensive review of the theory and practice of one of today's most powerful optimization techniques. The explosive growth of research into and development of interior point algorithms over the past two decades has significantly improved the complexity of linear programming and yielded some of today's most sophisticated computing techniques. This book offers a comprehensive and thorough treatment of the theory, analysis, and implementation of this powerful computational tool. interior point Algorithms provides detailed coverage of all basic and advanced aspects of the subject. Beginning with an overview of fundamental mathematical procedures, Professor Yinyu Ye moves swiftly on to in-depth explorations of numerous computational problems and the algorithms that have been developed to solve them. An indispensable text/reference for students and researchers in applied mathematics, computer science, operations research, management science, and engineering, interior point Algorithms: * Derives various complexity results for linear and convex programming * Emphasizes interior point geometry and potential theory * Covers state-of-the-art results for extension, implementation, and other cutting-edge computational techniques * Explores the hottest new research topics, including nonlinear programming and nonconvex optimization.

关键词： programming(Mathematics) linear programming

来源：评论

学校读者我要写书评

暂无评论

Strong duality for semidefinite programming

引用

SIAM JOURNAL ON OPTIMIZATION 1997年第3期7卷 641-662页

作者： Ramana, MV Tuncel, L Wolkowicz, H Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Waterloo Dept Combinator & Optimizat Fac Math Waterloo ON N2L 3G1 Canada

It is well known that the duality theory for linear programming (LP) is powerful and elegant and lies behind algorithms such as simplex and interior-point methods. However, the standard Lagrangian for nonlinear programs requires constraint qualifications to avoid duality gaps. Semidefinite linear programming (SDP) is a generalization of LP where the nonnegativity constraints are replaced by a semidefiniteness constraint on the matrix variables. There are many applications, e.g., in systems and control theory and combinatorial optimization. However, the Lagrangian dual for SDP can have a duality gap. We discuss the relationships among various duals and give a unified treatment for strong duality in semidefinite programming. These duals guarantee strong duality, i.e., a zero duality gap and dual attainment. This paper is motivated by the recent paper by Ramana where one of these duals is introduced.

关键词： semidefinite linear programming strong duality Lowner partial order symmetric positive semidefinite matrices

来源：评论

学校读者我要写书评

暂无评论

Fast convergence of the simplified largest step path following algorithm

引用

MATHEMATICAL programming 1997年第1期76卷 95-115页

作者： Gonzaga, CC Bonnans, JF INRIA ROCQUENCOURT F-78153 ROCQUENCOURT FRANCE TECH UNIV DELFT DELFT NETHERLANDS

Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation of p Newton steps: the first of these steps is exact, and the other are called ''simplified''. In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems, The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-order p + 1 in the number of master iterations, and with a complexity of O(root nL) iterations.

关键词： linear complementarity problem primal-dual interior-point algorithm convergence of algorithms simplified Newton method

来源：评论

学校读者我要写书评

暂无评论

Predictor-corrector algorithm for solving P*(kappa)-matrix LCP from arbitrary positive starting points

引用

MATHEMATICAL programming 1997年第1期76卷 223-244页

作者： Potra, FA Sheng, RQ Department of Mathematics University of Iowa Iowa City USA

A new predictor-corrector algorithm is proposed for solving P*(kappa)-matrix linear complementarity problems. If the problem is solvable, then the algorithm converges from an arbitrary positive starting point (x(0),s(0)). The computational complexity of the algorithm depends on the quality of the starting point. If the starting point is feasible or close to being feasible, it has O((1 + kappa) root n/rho(0)L)-iteration complexity, where rho(0) is the ratio of the smallest and average coordinate of X(0)s(0). With appropriate initialization, a modified version of the algorithm terminates in O((1 + kappa)(2)(n/rho(0))L) steps either by finding a solution or by determining that the problem has no solution in a predetermined, arbitrarily large, region, The algorithm is quadratically convergent for problems having a strictly complementary solution. We also propose an extension of a recent algorithm of Mizuno to P*(kappa)-matrix linear complementarity problems such that it can start from arbitrary positive points and has superlinear convergence without a strictly complementary condition.

关键词： linear complementarity problems P*-matrices interior-point algorithm superlinear convergence

来源：评论

学校读者我要写书评

暂无评论

Evaluation of the implementations of the Mehrotra type predictor-corrector method on MARKAL type energy models

Evaluation of the implementations of the Mehrotra type predi...

引用

1997 IEEE International Conference on Systems, Man, and Cybernetics - Computational Cybernetics and Simulation (SMC 97)

作者： Saeki, O Tsuji, K Osaka Univ Osaka Japan

ISBN: (纸本)078034054X

In this paper, we focus our attention on an infeasible interior point method and the effects of implementation techniques on computational speed are examined in detail. Infeasible methods can start from any interior point and are considered as one of the more effective methods than affine scaling methods which give a. good computational performance in practice. Here one of the infeasible methods which is referred to as the Mehrotra type predictor-corrector method is considered and the effects of its implementations on the computational efficiency are evaluated by numerical studies. For numerical studies, MARKAL type energy model. is used, which is a well known large scale linear programming problem in energy technology analysis area. In this paper, the algorithm is divided into three parts: i) Ordering which is used in order to keep the sparseness of matrices, ii) LU factorization which is used for obtaining a search direction, and iii) basis recovery. The most effective implementation at each part is suggested. By using the combination of the most effective implementations, a problem with 3,246 constraints has been solved about 70 times faster than by using a product form simplex method.

关键词： linear programming

来源：评论

学校读者我要写书评

暂无评论

Simplified method based on the deformation theory for structural limit analysis .1. theory and formulation

引用

INTERNATIONAL JOURNAL OF PRESSURE VESSELS AND PIPING 1997年第1期70卷 43-49页

作者： Tong, RC Wang, XC Department of Engineering Mechanics Tsinghua University Beijing 100084 P.R. China

Based on the deformation theory of linear hardening materials, a simplified finite element analysis method is proposed to calculate the limit load of structures. Compared with the general elasto-plastic incremental finite element analysis, the proposed method can avoid the incremental iteration of nodal displacements and the constitutive equation integration at each Gauss integral point. Compared with the mathematical programming method combined with finite element analysis, the proposed method shows theoretical simplicity and avoids bringing in complex mathematical theories. It is also easy to put into code. Compared with some current limit analysis methods, such as the GLOSS R-Node method and the elastic compensation method, the present method gives a remarkably accurate estimation of limit loads instead of just a simple lower or upper bound. Numerical examples have demonstrated that it is effective and the computational results are accurate enough to meet the need of engineering practice. Copyright (C) 1996 Elsevier Science Ltd.

关键词： Structural analysis

来源：评论

学校读者我要写书评

暂无评论

Lagrangian Relaxation / Dual Approaches For Solving Large-Scale linear programming Problems

Lagrangian Relaxation / Dual Approaches For Solving Large-Sc...

引用

作者： Madabushi, Ananth R. Virginia Tech | University

This research effort focuses on large-scale linear programming problems that arise in the context of solving various problems such as discrete linear or polynomial, and continuous nonlinear, nonconvex programming problems, using linearization and branch-and-cut algorithms for the discrete case, and using polyhedral outer-approximation methods for the continuous case. These problems arise in various applications in production planning, location-allocation, game theory, economics, and many engineering and systems design problems. During the solution process of discrete or continuous nonconvex problems using polyhedral approaches, one has to contend with repeatedly solving large-scale linear programming(LP) relaxations. Thus, it becomes imperative to employ an efficient method in solving these problems. It has been amply demonstrated that solving LP relaxations using a simplex-based algorithm, or even an interior-point type of procedure, can be inadequately slow ( especially in the presence of complicating constraints, dense coefficient matrices, and ill-conditioning ) in comparison with a Lagrangian Relaxation approach. With this motivation, we present a practical primal-dual subgradient algorithm that incorporates a dual ascent, a primal recovery, and a penalty function approach to recover a near optimal and feasible pair of primal and dual solutions. The proposed primal-dual approach is comprised of three stages. Stage I deals with solving the Lagrangian dual problem by using various subgradient deflection strategies such as the Modified Gradient Technique (MGT), the Average Direction Strategy (ADS), and a new direction strategy called the Modified Average Direction Strategy (M-ADS). In the latter, the deflection parameter is determined based on the process of projecting the unknown optimal direction onto the space spanned by the current subgradient direction and the previous direction. This projected direction approximates the desired optimal direction as closely

关键词： lagrangian relaxation subgradient line search primal recovery penalty function Thesis

来源：评论

学校读者我要写书评

暂无评论

Evaluation of the implementations of the Mehrotra type predictor-corrector method on MARKAL type energy models

Evaluation of the implementations of the Mehrotra type predi...

引用

IEEE International Conference on Systems, Man and Cybernetics

作者： O. Saeki K. Tsuji Department of Electrical Engineering Faculty of Engineering OSAKA University Suita Osaka Japan

In this paper, we focus our attention on an infeasible interior point method and the effects of implementation techniques on computational speed are examined in detail. Infeasible methods can start from any interior point and are considered as one of the more effective methods than affine scaling methods which give a good computational performance in practice. Here one of the infeasible methods which is referred to as the Mehrotra type predictor-corrector method (1992) is considered and the effects of its implementations on the computational efficiency are evaluated by numerical studies. For numerical studies, MARKAL type energy model is used, which is a well known large-scale linear programming problem in energy technology analysis area. In this paper, the algorithm is divided into three parts: i) ordering which is used in order to keep the sparseness of matrices, ii) LU factorization which is used for obtaining a search direction, and iii) basis recovery. The most effective implementation at each part is suggested. By using the combination of the most effective implementations, a problem with 3,246 constraints has been solved about 70 times faster than by using a product form simplex method.

关键词： linear systems Computational efficiency Large-scale systems Polynomials linear programming Predictive models Power engineering and energy Time measurement

来源：评论

学校读者我要写书评

暂无评论

Semidefinite programming

引用

SIAM REVIEW 1996年第1期38卷 49-95页

作者： Vandenberghe, L Boyd, S STANFORD UNIV DEPT ELECT ENGNINFORMAT SYST LABSTANFORDCA 94305

In semidefinite programming, one minimizes a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programs are convex optimization problems. Semidefinite programming unifies several standard problems (e.g., linear and quadratic programming) and finds many applications in engineering and combinatorial optimization. Although semidefinite programs are much more general than linear programs, they are not much harder to solve. Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity and perform very well in practice. This paper gives a survey of the theory and applications of semidefinite programs and an introduction to primal-dual interior-point methods for their solution.

关键词： semidefinite programming convex optimization interior-point methods eigenvalue optimization combinatorial optimization system and control theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：