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

应用数学 2017年第2期30卷 337-343页

作者：马晓珏刘红卫西安电子科技大学数学与统计学院陕西西安710071 西安邮电大学理学院陕西西安710121

艾文宝(2004)的宽邻域算法弥补了内点法在理论和实践表现之间的差异.基于这个算法的优越性,将其推广到线性互补问题中.新算法在一次迭代中,采用两个方向的线性组合作为新方向,并以满步长到达下一个点.可以证明,该算法具有O(n^(1/2)L)的... 详细信息

艾文宝(2004)的宽邻域算法弥补了内点法在理论和实践表现之间的差异.基于这个算法的优越性,将其推广到线性互补问题中.新算法在一次迭代中,采用两个方向的线性组合作为新方向,并以满步长到达下一个点.可以证明,该算法具有O(n^(1/2)L)的理论复杂度,这是迄今为止最好的复杂度结果.同时,在假设线性互补问题存在严格互补解的前提下,证明算法具有局部二次收敛性.最后,数值实验说明算法是有效的.

关键词：原-对偶内点法宽邻域线性互补问题二次收敛

来源：评论

学校读者我要写书评

暂无评论

Notes on Numerical methods for Solving Optimal Control Problems

引用

IEEJ JOURNAL OF INDUSTRY APPLICATIONS 2016年第2期5卷 154-166页

作者： Biral, Francesco Bertolazzi, Enrico Bosetti, Paolo Univ Trento Dept Ind Engn Via Sommarive 9 I-38123 Povo Trento Italy

Recent advances in theory, algorithms, and computational power make it possible to solve complex, optimal control problems both for off-line and on-line industrial applications. This paper starts by reviewing the technical details of the solution methods pertaining to three general categories: dynamic programming, indirect methods, and direct methods. With the aid of a demonstration example, the advantages and disadvantages of each method are discussed, along with a brief review of available software. The main result that emerges is the indirect method being numerically competitive with the performance of direct ones based on non-linear programming solvers and interior point algorithms. The second part of the paper introduces an indirect method based on the Pontryagin Minimum Principle (PMP). It also presents a detailed procedure and software tools (named PINS) to formulate the problem, automatically generate the C + + code, and eventually obtain a numerical solution for several optimal control problems of practical relevance. The application of PMP relates to the analytical derivation of necessary conditions for optimality. This aspect-often regarded in the literature as a drawback-is here exploited to build a robust yet efficient numerical method that formally eliminates the controls from the resulting Boundary Value Problem, thus gaining robustness and a high convergence rate. The elimination of the control is obtained either via their explicit formulation function of state and Lagrange multipliers-when possible-or via an iterative numerical solution. The paper closes presenting a minimum time manoeuvre of a car using a fairly complex vehicle model which also includes tyre saturation.

关键词： optimal control direct methods indirect methods

来源：评论

学校读者我要写书评

暂无评论

Distributed Convex Optimization in Networks of Agents with Single-integrator Dynamics

Distributed Convex Optimization in Networks of Agents with S...

引用

Asian Control Conference

作者： Amir Adibzadeh Mohsen Zamani Amir A. Suratgar Mohammad B. Menhaj Electrical Engineering Department Amirkabir University of Technology Tehran Iran School of Electrical Engineering and Computer Science The University of Newcastle NSW Australia

ISBN: (纸本)9781509015740;9781509015733

In this paper, distributed convex optimization problem over undirected dynamical networks is studied. Here, networked agents are supposed to rendezvous at a point that is the solution of a global convex optimization problem with some local inequality constraints. To this end, all agents shall cooperate with their neighbors to seek the optimum point of the network's global objective function. A consensus-based distributed optimization algorithm is proposed, which combines an interior-point optimization algorithm with a nonlinear consensus protocol to find the optimum value of a convex objective function. We tackle this problem by addressing its subproblems, namely a consensus problem and a convex optimization problem. Firstly, we propose a saturation protocol for the consensus subproblem. Then, to solve the distributed optimization part, we implement an updating rule, which yields the optimum value of the global objective function, with the help of local estimators in a distributed way. Convergence analysis for the proposed protocol based on the Lyapunov stability theory for time-varying nonlinear systems is included. A simulation example is given at the end to illustrate the effectiveness of the proposed algorithm.

关键词： Optimization linear programming Convex functions Protocols Heuristic algorithms Australia Lyapunov methods

来源：评论

学校读者我要写书评

暂无评论

EXPLOITING SPARSITY FOR LARGE-SCALE QUADRATIC programming

EXPLOITING SPARSITY FOR LARGE-SCALE QUADRATIC PROGRAMMING

引用

作者： DUANGPEN JETPIPATTANAPONG THAMMASAT UNIVERSITY

学位级别：博士

Quadratic programming is a class of constrained optimization problems with quadratic objective function and linear constraints. It is an important optimization problem with applications in many areas and is also used to solve nonlinear optimization problems. Quadratic programs arisen in practice are often large, but sparse, and have a special Hessian structure which we can exploit. They usually cannot be solved efficiently without exploiting their structures. This thesis proposes methods for solving several classes of quadratic programming with structure. We show a heuristic method for the large-scale quadratic programs with block diagonal Hessian matrices and dense constraint matrices. Our method separates the problem into smaller problems, computes optimal solutions for the smaller problems, and uses them to construct the solution to the original problem. Computational results show that our method is highly efficient at computing approximate solutions for large-scale problems. The other method is an efficient method to compute the search directions for the primal-dual path-following interior- point method for the similar class of Hessian matrix structure and dense constraint matrices. The time complexity of the method is significantly smaller than that of using a sparse linear solver. The computational results also show that the proposed method is faster. This thesis also proposes a pivot selection algorithm for the factorization of the Karush-Kuhn-Tucker (KKT) matrix for the equality constrained quadratic programs whose constraint matrices are block diagonal. Such factorization should maintain both sparsity and numerical stability of the factors, both of which depend solely on the choices of the pivots. The proposed method maintains the sparsity and stability of the problem. The experiments show that the pivot selection algorithm appears to produce no fill-ins in the factorization of such matrices. In addition, we compare the method with MA57 and find that the fa

关键词： Large-scale Quadratic programming Block diagonal constraint Heuristic Algorithm Separable Quadratic Optimization interior-point method Primal-dual path following Symmetric indefinite factorization

来源：评论

学校读者我要写书评

暂无评论

Semidefinite programming: theory and Applications in Finance

Semidefinite Programming: Theory and Applications in Finance

引用

作者： Markus Gerald Alexander Gabl Universitat Wien

学位级别：硕士

This thesis deals with semidefinite programming, the basic theory and the respective algorithms, as well as with its many applications in finance, rang- ing from asset pricing to portfolio optimization. Semidefinite programming is a convex optimization technique, that seeks to optimize the a linear objective function over a convex set that is described via linear matrix inequalities or via intersections of affine sets with the cone of positive definite matrices. The power of this problem formulation arises not only from the fact, that it generalizes linear programming as well as second order cone programming and quadratic programming, but also from the fact, that many non-convex and combinatorial problems can be relaxed as semidefinite programs and solved approximately, where the so obtained bounds can often be shown to be comparatively tight. Though the concept is known at least since the 1980's (with the earliest ref- erence even dating back to 1961), interest only started to excel in the 1990's, when it became clear, that interior point methods (previously used to solve lin- ear and quadratic programs) could also be used to solve semidefinite programs efficiently. Since then a plethora of algorithms have been developed with ap- plications ranging from engineering, over statistics and logistics to, of course, finance. The Thesis will start out by briefly reviewing some important concepts from linear algebra and convex analysis. After that, there will be a more extensive discussion of the model itself, as well as of its properties, as far as they will be useful for the understanding of the applications and algorithms. The later will be discussed in the subsequent chapters, where the focus will be on Primal-Dual Potential Reduction methods. The theoretical part will close with a survey of basic ideas, that may guide the formulation of generic problems as semidefinite programs. Following that, there will be an extensive discussion of models, that are ad- dressing pro

关键词：

来源：评论

学校读者我要写书评

暂无评论

Lagrangian Transformation and interior Ellipsoid methods in Convex Optimization

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2015年第3期164卷 966-992页

作者： Polyak, Roman Technion Israel Inst Technol Dept Math IL-32000 Haifa Israel

The rediscovery of the affine scaling method in the late 1980s was one of the turning points which led to a new chapter in Modern Optimization-the interior point methods (IPMs). Simultaneously and independently, the theory of exterior point methods for convex optimization arose. The two seemingly unconnected fields turned out to be intrinsically connected. The purpose of this paper is to show the connections between primal exterior and dual IPMs. Our main tool is the Lagrangian transformation (LT), which for inequality constrained has the best features of the classical augmented Lagrangian. We show that the primal exterior LT method is equivalent to the dual interior ellipsoid method (IEM). Using the equivalence we prove convergence, estimate the convergence rate, and establish the complexity bound for the IEM assuming boundedness of both the primal and the dual optimal sets. We show that application of the LT method with modified barrier transformation for linear programming (LP) leads to Dikin's affine scaling method for the dual LP.

关键词： Lagrangian transformation interior point methods Duality Bregman distance Augmented lagrangian interior ellipsoid method

来源：评论

学校读者我要写书评

暂无评论

Solving the max-cut problem using semidefinite optimization

Solving the max-cut problem using semidefinite optimization

引用

Colloquium in Information Science and Technology (CIST)

作者： Derkaoui Orkia Lehireche Ahmed Computer Science Department University Djillali Liabes of Sidi Bel Abbes City Sidi Bel Abbes Algeria

ISBN: (纸本)9781509007523

Max-cut problem is one of many NP-hard graph theory problems which attracted many researchers over the years. Maximum cuts are useful items including theoretical physics and electronics. But they are best known for algorithmic problem of finding a maximum cutting, commonly called MAXCUT, a relatively well-studied problem, particularly in the context of the approximation. Various heuristics, or combination of optimization and heuristic methods have been developed to solve this problem. Among them is the efficient algorithm of Goemans and Williamson. Their algorithm combines Semidefinite programming and a rounding procedure to produce an approximate solution to the max-cut problem. Semidefinite programming (SDP) is currently the most sophisticated area of Conic programming that is polynomially solvable. The SDP problem is solved with interior point methods. In parallel, the development of efficient SDP solvers, based on interior point algorithms, also contributed to the success of this method. In this paper we use a new variant of the solver CSDP (C library for semidfinite programming) to resolve this problem. It is based on a Majorize-Minimize line search algorithm for barrier function optimization. A tangent majorant function is built to approximate a scalar criterion containing a barrier function. The comparison of the results obtained with the classic CSDP and our new variant is promising.

关键词： Symmetric matrices Approximation algorithms Prediction algorithms Optimization Algorithm design and analysis Convex functions linear programming

来源：评论

学校读者我要写书评

暂无评论

Projection methods for quantum channel construction

引用

QUANTUM INFORMATION PROCESSING 2015年第8期14卷 3075-3096页

作者： Drusvyatskiy, Dmitriy Li, Chi-Kwong Pelejo, Diane Christine Voronin, Yuen-Lam Wolkowicz, Henry Univ Washington Dept Math Seattle WA 98195 USA Coll William & Mary Dept Math Williamsburg VA 23185 USA Univ Colorado Dept Comp Sci Boulder CO 80309 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We consider the problem of constructing quantum channels, if they exist, that transform a given set of quantum states to another such set . In other words, we must find a completely positive linear map, if it exists, that maps a given set of density matrices to another given set of density matrices, possibly of different dimension. Using the theory of completely positive linear maps, one can formulate the problem as an instance of a positive semidefinite feasibility problem with highly structured constraints. The nature of the constraints makes projection-based algorithms very appealing when the number of variables is huge and standard interior-point methods for semidefinite programming are not applicable. We provide empirical evidence to this effect. We moreover present heuristics for finding both high-rank and low-rank solutions. Our experiments are based on the method of alternating projections and the Douglas-Rachford reflection method.

关键词： Quantum channels Completely positive linear maps Alternating projection methods Douglas-Rachford method Choi matrix Semidefinite feasibility problem Large scale

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems

引用

JOURNAL OF OPTIMIZATION theory AND APPLICATIONS 2015年第2期166卷 558-571页

作者： Park, Sungwoo O'Leary, Dianne P. KCG Holdings Jersey City NJ 07310 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction due to Potra and Sheng (1998) and can be applied whenever the data matrices are block diagonal. It thus solves as special cases any optimization problem that is a linear, convex quadratic, convex quadratically constrained, or second-order cone problem.

关键词： Semidefinite programming interior point methods Constraint reduction Primal dual infeasible Polynomial complexity

来源：评论

学校读者我要写书评

暂无评论

Sparse linear programming via Primal and Dual Augmented Coordinate Descent 29

Sparse Linear Programming via Primal and Dual Augmented Coor...

引用

29th Annual Conference on Neural Information Processing Systems (NIPS)

作者： Yen, Ian E. H. Zhong, Kai Hsieh, Cho-Jui Ravikumar, Pradeep Dhillon, Inderjit S. Univ Texas Austin Austin TX 78712 USA Univ Calif Davis Davis CA 95616 USA

Over the past decades, linear programming (LP) has been widely used in different areas and considered as one of the mature technologies in numerical optimization. However, the complexity offered by state-of-the-art algorithms (i.e. interior-point method and primal, dual simplex methods) is still unsatisfactory for problems in machine learning with huge number of variables and constraints. In this paper, we investigate a general LP algorithm based on the combination of Augmented Lagrangian and Coordinate Descent (AL-CD), giving an iteration complexity of O((log(1/epsilon))(2)) with O(nnz(A)) cost per iteration, where nnz(A) is the number of non-zeros in the m x n constraint matrix A, and in practice, one can further reduce cost per iteration to the order of non-zeros in columns (rows) corresponding to the active primal (dual) variables through an active-set strategy. The algorithm thus yields a tractable alternative to standard LP methods for large-scale problems of sparse solutions and nnz(A) << mn. We conduct experiments on large-scale LP instances from l(1)-regularized multi-class SVM, Sparse Inverse Covariance Estimation, and Nonnegative Matrix Factorization, where the proposed approach finds solutions of 10(-3) precision orders of magnitude faster than state-of-the-art implementations of interior-point and simplex methods.(1)

关键词： linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：