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

线性规划的一个宽邻域预估-矫正内点算法

引用

平顶山学院学报 2014年第2期29卷 6-9页

作者：刘长河任建林河南科技大学数学与统计学院河南洛阳471023 信阳工业学校河南信阳465150

在线性规划的内点算法中,宽邻域算法比窄邻域算法的数值效果好,但宽邻域算法的复杂性比窄邻域差.提出了求解线性规划问题的一个宽邻域预估-矫正内点算法,证明了该算法的迭代复杂性是O(n L),这是线性规划的内点算法中最好的复杂性结果.

关键词：线性规划内点方法预估-矫正算法宽邻域算法多项式复杂性

来源：评论

学校读者我要写书评

暂无评论

Nonlinear programming: theory and Algorithms

引用

2013年

作者： Mokhtar S Bazaraa

ISBN: (纸本)9781118857564

COMPREHENSIVE COVERAGE OF NONlinear programming theory AND ALGORITHMS, THOROUGHLY REVISED AND EXPANDED"Nonlinear programming: theory and Algorithms"--now in an extensively updated Third Edition--addresses the problem of optimizing an objective function in the presence of equality and inequality constraints. Many realistic problems cannot be adequately represented as a linear program owing to the nature of the nonlinearity of the objective function and/or the nonlinearity of any constraints. The "Third Edition" begins with a general introduction to nonlinear programming with illustrative examples and guidelines for model *** on the three major parts of nonlinear programming is provided: Convex analysis with discussion of topological properties of convex sets, separation and support of convex sets, polyhedral sets, extreme points and extreme directions of polyhedral sets, and linear programmingOptimality conditions and duality with coverage of the nature, interpretation, and value of the classical Fritz John (FJ) and the Karush-Kuhn-Tucker (KKT) optimality conditions; the interrelationships between various proposed constraint qualifications; and Lagrangian duality and saddle point optimality conditionsAlgorithms and their convergence, with a presentation of algorithms for solving both unconstrained and constrained nonlinear programming problemsImportant features of the "Third Edition" include: New topics such as second interior point methods, nonconvex optimization, nondifferentiable optimization, and moreUpdated discussion and new applications in each chapterDetailed numerical examples and graphical illustrationsEssential coverage of modeling and formulating nonlinear programsSimple numerical problemsAdvanced theoretical exercisesThe book is a solid reference for professionals as well as a useful text for students in the fields of operations research, management science, industrial engineering, applied mathematics, and also in engineering disci

关键词：

来源：评论

学校读者我要写书评

暂无评论

Infeasible constraint-reduced interior-point methods for linear optimization

引用

OPTIMIZATION methods & SOFTWARE 2012年第4-5期27卷 801-825页

作者： He, Meiyun Y. Tits, Andre L. Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA

Constraint-reduction schemes have been proposed for the solution by means of interior-point methods of linear programs with many more inequality constraints than variables in the standard dual form. Such schemes have been shown to be provably convergent and highly efficient in practice. A critical requirement of these schemes is the availability of an initial dual-feasible point. In this paper, building on a general framework (which encompasses several previously proposed approaches) for dual-feasible constraint-reduced interior-point optimization, for which we prove convergence to a single point of the sequence of dual iterates, we propose a framework for 'infeasible' constraint-reduced interior-point optimization. Central to this framework is an exact (l(1) or l(infinity)) penalty function scheme endowed with a mechanism for iterative adjustment of the penalty parameter, which aims at yielding, after a finite number of iterations, a value that guarantees feasibility (for the original problem) of the minimizers. Finiteness of the sequence of penalty parameter adjustments is proved under mild assumptions for all algorithms that fit within the framework, including 'infeasible' extensions of a 'dual' algorithm proposed in the early 1990s (Dantzig and Ye, A build-up interior-point method for linear programming: Affine scaling form, Working paper, Department of Management Science, University of Iowa, 1991) and of two recently proposed 'primal-dual' algorithms (Tits, Absil, and Woessner, Constraint reduction for linear programs with many inequality constraints, SIAM J. Optim. 17 (2006), pp. 119-146;Winternitz, Nicholls, Tits, and O'Leary, A constraint-reduced variant of Mehrotra's predictor-corrector algorithm, Comput. Optim. Appl. (published on-line as of January 2011), DOI: 10.1007/s10589-010-9389-4). The last one, a constraint-reduced variant of Mehrotra's Predictor-Corrector algorithm, is then more specifically considered: further convergence results are proved, and

关键词： constraint reduction infeasible initial points interior-point methods linear programming many constraints

来源：评论

学校读者我要写书评

暂无评论

Tight polyhedral approximation for mixed-integer linear programming unit commitment formulations

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2012年第11期6卷 1104-1111页

作者： Jabr, R. A. Amer Univ Beirut Dept Elect & Comp Engn Beirut 11072020 Lebanon

The perspective reformulation has been recently proposed for constructing tight relaxations of the unit commitment (UC) problem with quadratic cost functions. In this case, it has been shown that the perspective reformulation can be cast as a second-order cone program. Conic quadratic programming is based on interior-point methods and does not benefit from the warm-start capabilities of the simplex method available in commercial mixed-integer linear programming software. It is known that the perspective formulation can be approximated with arbitrary accuracy by dynamically adding gradient-type inequalities. This study presents a higher dimensional polyhedral approximation of the perspective reformulation. The proposed approximation is not based on gradient information and can be easily implemented in a modelling language;in addition, it requires defining additional variables and constraints whose number grows moderately with increasing levels of accuracy. Extensive numerical comparisons show that the polyhedral approximation of the perspective reformulation yields a tight UC formulation, which is competitive with currently known ones.

关键词： approximation theory interior-point methods perspective reformulation Power system management, operation and economics linear programming Optimisation techniques tight polyhedral approximation modelling language integer programming power generation scheduling commercial mixed-integer linear programming software second-order cone program power generation dispatch quadratic programming mixed-integer linear programming unit commitment formulations warm-start capabilities gradient-type inequalities simplex method Interpolation and function approximation (numerical analysis) conic quadratic programming gradient information higher dimensional polyhedral approximation quadratic cost functions

来源：评论

学校读者我要写书评

暂无评论

Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression

引用

MATHEMATICAL programming 2012年第1-2期131卷 163-194页

作者： Lu, Zhaosong Monteiro, Renato D. C. Yuan, Ming Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

In this paper, we study convex optimization methods for computing the nuclear (or, trace) norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection method, recently proposed by Yuan et al. (J Royal Stat Soc Ser B (Statistical Methodology) 69(3):329-346, 2007) conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and finite samples. To compute the estimates, however, can be very challenging in practice because of the high dimensionality and the nuclear norm constraint. In this paper, we explore a variant due to Tseng of Nesterov's smooth method and interior point methods for computing the penalized least squares estimate. The performance of these methods is then compared using a set of randomly generated instances. We show that the variant of Nesterov's smooth method generally outperforms the interior point method implemented in SDPT3 version 4.0 (beta) (Toh et al. On the implementation and usage of sdpt3-a matlab software package for semidefinite-quadratic-linear programming, version 4.0. Manuscript, Department of Mathematics, National University of Singapore (2006)) substantially. Moreover, the former method is much more memory efficient.

关键词： Cone programming Smooth saddle point problem First-order method Multivariate linear regression Nuclear or trace norm Dimension reduction

来源：评论

学校读者我要写书评

暂无评论

Strong duality and minimal representations for cone optimization

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第2期53卷 619-648页

作者： Tuncel, Levent Wolkowicz, Henry Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility. We include results and examples on the surprising theoretical connection between duality gaps in the original primal-dual pair and lack of strict complementarity in their homogeneous counterpart. Our emphasis is on results that deal with Semidefinite programming, SDP.

关键词： Cone optimization Duality Preprocessing Constraint qualification Duality gap Semidefinite programming Strict complementarity Nice cones Devious cones Facially dual complete cones

来源：评论

学校读者我要写书评

暂无评论

Algorithms, Graph theory, and the Solution of Laplacian linear Equations

Algorithms, Graph Theory, and the Solution of Laplacian Line...

引用

39th International Colloquium on Automata, Languages, and programming (ICALP)

作者： Spielman, Daniel A. Yale Univ Program Appl Math Dept Comp Sci New Haven CT 06520 USA

ISBN: (纸本)9783642315855

In this talk, we survey major developments in the design of algorithms for solving Laplacian linear equations, by which we mean systems of linear equations in the Laplacian matrices of graphs and their submatrices. We begin with a few examples of where such equations arise, including the analysis of networks of resistors, the analysis of networks of springs, and the solution of maximum flow problems by interior point methods.

关键词： linear equations

来源：评论

学校读者我要写书评

暂无评论

Strong duality and minimal representations for cone optimization

Strong duality and minimal representations for cone optimiza...

引用

Workshop on Non linear Optimization, Variational Inequalities and Equilibrium Problems

作者： Tuncel, Levent Wolkowicz, Henry Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

关键词： Cone optimization Duality Preprocessing Constraint qualification Duality gap Semidefinite programming Strict complementarity Nice cones Devious cones Facially dual complete cones

来源：评论

学校读者我要写书评

暂无评论

Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric Cones

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2012年第3期154卷 949-965页

作者： Liu, Changhe Liu, Hongwei Liu, Xinze Xidian Univ Dept Math Xian 710071 Peoples R China Henan Univ Sci & Technol Dept Appl Math Luoyang Peoples R China Lincang Teachers Coll Dept Math & Sci Lincang Peoples R China

This paper presents an extension of the variant of Mehrotra's predictor-corrector algorithm which was proposed by Salahi and Mahdavi-Amiri (Appl. Math. Comput. 183:646-658, 2006) for linear programming to symmetric cones. This algorithm incorporates a safeguard in Mehrotra's original predictor-corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. In our algorithm, the safeguard strategy is not necessarily used when the affine scaling step behaves poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We slightly modify the maximum step size in the affine scaling step and extend the algorithm to symmetric cones using the machinery of Euclidean Jordan algebras. Based on the Nesterov-Todd direction, we show that the iteration-complexity bound of the proposed algorithm is , where r is the rank of the associated Euclidean Jordan algebras and epsilon > 0 is the required precision.

关键词： Symmetric cone Euclidean Jordan algebra interior-point methods Second-order methods Mehrotra-type algorithm Polynomial complexity

来源：评论

学校读者我要写书评

暂无评论

AN INEXACT SPECTRAL BUNDLE METHOD AND ERROR BOUNDS FOR CONVEX QUADRATIC SYMMETRIC CONE programming

AN INEXACT SPECTRAL BUNDLE METHOD AND ERROR BOUNDS FOR CONVE...

引用

作者： LIN HUILING Nanyang Technological University

学位级别：博士

In this dissertation, we apply the main technical tools from the theory of Jordan algebras to explore a conic programming problem that minimizes a convex quadratic function over the intersection of a symmetric cone with an affine subspace. Our adaptation is called convex quadratic symmetric cone programming (CQSCP). This optimization problem subsumes linear programming, quadratic programming, second- order cone programming and semidefinite programming as special cases. Under a mild assumption, we reformulate this problem as the problem of mini- mizing the maximum eigenvalue of an affine function. We present an inexact spectral bundle method for solving this eigenvalue minimization problem. This method is a first-order method, hence it requires much less computational cost in each iteration than second-order approaches such as interior-point methods. While sometimes pro- viding solutions of low accuracy, such method can attack large scale problems. In each iteration of our method, we compute the largest eigenvalue inexactly, and solve a small convex quadratic symmetric cone program as a subproblem. We give a proof of the global convergence of this method using techniques from the analysis of the standard bundle method, and provide a Lipschitzian error bound under a Slater type condition for the reformulation of the problem under consideration. Another purpose of this dissertation is to investigate a Lipschitzian error bound for the CQSCP problem. We start by considering a sequence of strictly feasible solutions within a wide neighborhood of the central trajectory for the monotone symmetric cone linear complementarity problem (SCLCP). Under assumptions of strict complemen- tarity and Slater's condition, we derive a necessary condition of a Lipschitzian error bound for the monotone SCLCP in general Euclidean Jordan algebras, and provide four different characterizations of such error bound in the setting of Euclidean Jordan algebras embedded in associative algebras. Und

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：