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

Primal-dual first-order methods with O(1/ε) iteration-complexity for cone programming

MATHEMATICAL programming 2011年第1期126卷 1-29页

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

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov's optimal method (Nesterov in Doklady AN SSSR 269:543-547, 1983;Math Program 103:127-152, 2005), Nesterov's smooth approximation scheme (Nesterov in Math Program 103: 127-152, 2005), and Nemirovski's prox-method (Nemirovski in SIAM J Opt 15: 229-251, 2005), and propose a variant of Nesterov's optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov's optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95: 329-357, 2003;Math Program 103:427-444, 2005) for solving a set of randomly generated SDP instances.

关键词： Cone programming Primal-dual first-order methods Smooth optimal method Nonsmooth method Prox-method Linear programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Dynamical System Characterization of the Central Path and Its Variants-A Revisit

引用

SIAM JOURNAL ON APPLIED DYNAMICAL SYSTEMS 2011年第3期10卷 887-905页

作者： Chu, Moody T. Lin, Matthew M. N Carolina State Univ Dept Math Raleigh NC 27695 USA Natl Chung Cheng Univ Dept Math Chiayi 621 Taiwan

The notion of central path plays a fundamental role in the development of interior point methods which, in turn, have become important tools for solving various optimization problems. The central path equation is algebraic in nature and is derived from the KKT optimality conditions of a certain logarithmic barrier problem;meanwhile, the primal variable portion of the very same central path can also be cast precisely as the integral curve, known as the affine scaling trajectory, of a certain gradient-type dynamical system. The justification is easy to establish in the context of linear programming. Though expected, the generalization of such a concept to semidefinite programming is not quite as obvious due to the difficulty of addressing noncommutativity in matrix multiplication. This paper revisits the dynamical system characterization of these flows and addresses the needed details for extension to semidefinite programming by means of a simple notion of operators and a specially defined inner product. From a dynamical systems point of view, numerical ODE techniques might help us to develop some novel interior point methods.

关键词： linear programming semidefinite programming central path interior point method projected gradient dynamical system affine scaling trajectory

来源：评论

学校读者我要写书评

暂无评论

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer programming with PSD Objectives

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Sc...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Guruswami, Venkatesan Sinop, Ali Kemal Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9780769545714

We present an approximation scheme for optimizing certain Quadratic Integer programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time n(O(tau/epsilon 2)) with approximation ratio 1+epsilon/min{1,lambda(tau)}, where lambda(tau) is the r'th smallest eigenvalue of the normalized graph Laplacian L. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply (1 + O(epsilon)) factor approximation in time n(O(*r/epsilon 2)) where r* is the number of eigenvalues of L smaller than 1 - epsilon. This perhaps gives some indication as to why even showing mere APX-hardness for these problems has been elusive, since the reduction must produce graphs with a slowly growing spectrum (and classes like planar graphs which are known to have such a spectral property often admit good algorithms owing to their nice structure). For Unique Games, we give a factor (1 vertical bar 2+epsilon/lambda(r)) approximation for minimizing the number of unsatisfied constraints in n(O(r/epsilon 2)) time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have

关键词： Approximation algorithms graph partitioning unique games semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial programming

引用

15th International Conference on Integer programming and Combinatorial Optimization (IPCO)

作者： Ghaddar, Bissan Vera, Juan C. Anjos, Miguel F. Univ Waterloo Dept Management Sci Waterloo ON N2L 3G1 Canada Tilburg Univ Tilburg Sch Econ & Management Tilburg Netherlands Ecole Polytech Dept Math & Genie Ind Montreal PQ H3T 1J4 Canada Ecole Polytech Gerad Montreal PQ H3T 1J4 Canada

ISBN: (纸本)9783642208072

semidefinite programming has been used successfully to build hierarchies of convex relaxations to approximate polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small sizes. We propose an iterative scheme that improves the semidefinite relaxations without incurring exponential growth in their size. The key ingredient is a dynamic scheme for generating valid polynomial inequalities for general polynomial programs. These valid inequalities are then used to construct better approximations of the original problem. As a result, the proposed scheme is in principle scalable to large general combinatorial optimization problems. For binary polynomial programs, we prove that the proposed scheme converges to the global optimal solution for interesting cases of the initial approximation of the problem. We also present examples illustrating the computational behaviour of the scheme and compare it to other methods in the literature.

关键词： Binary Polynomial programming Binary Quadratic programming Valid Inequality Generation semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A new scheme to learn a kernel in regularization networks

引用

NEUROCOMPUTING 2011年第12-13期74卷 2222-2227页

作者： Chen, Jie Ma, Fei Chen, Jian Yibin Univ Dept Math Yibin 644000 Peoples R China Xinhu Futures Co Ltd InterContinental Bussiness Ctr Shanghai 200070 Peoples R China Foshan Univ Dept Math Foshan 528000 Peoples R China

In this paper, we propose a new scheme to learn a kernel function from the convex combination of finite given kernels in regularization networks. We show that the corresponding variational problem is convex and under certain conditions, the variational problem can be approximated by a semidefinite programming problem which coincides with the Micchelli and Pontil's (MP's) Model (Micchelli and Pontil, 2005 [10]). (C) 2011 Elsevier B.V. All rights reserved.

关键词： Regularization networks Optimal kernel Convexity semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs

引用

APPLIED MATHEMATICAL MODELLING 2011年第5期35卷 2425-2442页

作者： Zhu, Yuntao Ariyawansa, K. A. Washington State Univ Dept Math Pullman WA 99164 USA Arizona State Univ Div Math & Nat Sci Phoenix AZ 85069 USA

Ariyawansa and Zhu have recently introduced (two-stage) stochastic semidefinite programs (with recourse) (SSDPs) [1] and chance-constrained semidefinite programs (CCSDPs) [2] as paradigms for dealing with uncertainty in applications leading to semidefinite programs. semidefinite programs have been the subject of intense research during the past 15 years, and one of the reasons for this research activity is the novelty and variety of applications of semidefinite programs. This research activity has produced, among other things, efficient interior point algorithms for semidefinite programs. semidefinite programs however are defined using deterministic data while uncertainty is naturally present in applications. The definitions of SSDPs and CCSDPs in [1.2] were formulated with the expectation that they would enhance optimization modeling in applications that lead to semidefinite programs by providing ways to handle uncertainty in data. In this paper, we present results of our attempts to create SSDP and CCSDP models in four such applications. Our results are promising and we hope that the applications presented in this paper would encourage researchers to consider SSDP and CCSDP as new paradigms for stochastic optimization when they formulate optimization models. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Linear programming Stochastic programming semidefinite programming Chance-constraints Optimization models

来源：评论

学校读者我要写书评

暂无评论

Reduced Complexity semidefinite Relaxation Algorithms for Source Localization Based on Time Difference of Arrival

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2011年第9期10卷 1276-1282页

作者： Xu, Enyang Ding, Zhi Dasgupta, Soura Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA Univ Iowa Dept Elect & Comp Engn Seamans Ctr Engn Arts & Sci 5322 Iowa City IA 52242 USA

We investigate the problem of source localization based on measuring time difference of signal arrivals (TDOA) from the source emitter. Taking into account the colored measurement noise, we adopt a min-max principle to develop two lower complexity semidefinite relaxation algorithms that can be reliably solved using semidefinite programming. The reduction of algorithm complexity is achieved through a simple, but effective method to select a reference node among participating measurement nodes such that only selective time differences of signal arrival are exploited. Our estimation methods are insensitive to the source locations and can be used either as the final location estimate or as the initial point for more traditional search algorithms.

关键词： Source localization time difference of arrival semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A convex optimisation framework for the unequal-areas facility layout problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2011年第2期214卷 199-215页

作者： Jankovits, Ibolya Luo, Chaomin Anjos, Miguel F. Vannelli, Anthony Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada Univ Waterloo Dept Management Sci Waterloo ON N2L 3G1 Canada Univ Guelph Sch Engn Guelph ON N1G 2W1 Canada

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present a convex-optimisation-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical programming models. The first model is a convex relaxation of the layout problem that establishes the relative position of the departments within the facility, and the second model uses semidefinite optimisation to determine the final layout. Aspect ratio constraints, frequently used in facility layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are taken into account by both models. We present computational results showing that the proposed framework consistently produces competitive, and often improved, layouts for well-known large instances when compared with other approaches in the literature. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Facility layout semidefinite programming Convex programming Global optimisation

来源：评论

学校读者我要写书评

暂无评论

Obtaining certificates for complete synchronisation of coupled oscillators

引用

PHYSICA D-NONLINEAR PHENOMENA 2011年第8期240卷 795-803页

作者： August, Elias Barahona, Mauricio ETH Dept Elect Engn CH-8092 Zurich Switzerland Univ London Imperial Coll Sci Technol & Med Dept Bioengn London SW7 2AZ England Univ London Imperial Coll Sci Technol & Med Inst Math Sci London SW7 2AZ England

In this paper, we provide a novel reformulation of sufficient conditions that guarantee global complete synchronisation of coupled identical oscillators to make them computationally implementable. To this end, we use semidefinite programming techniques. For the first time, we can efficiently search for and obtain certificates for synchronisability and, additionally, also optimise associated cost functions. In this paper, a Lyapunov-like function (certificate) is used to certify that all trajectories of a networked system consisting of coupled dynamical systems will eventually converge towards a common one, which implies synchronisation. Moreover, we establish new conditions for complete synchronisation, which are based on the so called Bendixson's Criterion for higher dimensional systems. This leads to major improvements on the lower bound of the coupling constant that guarantees global complete synchronisation. Importantly, the certificates are obtained by analysing the connection network and the model representing an individual system only. In order to illustrate the strength of our method we apply it to a system of coupled identical Lorenz oscillators and to coupled van der Pol oscillators. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Lyapunov theory Contraction theory Bendixson's Criterion for higher dimensions semidefinite programming Sum of squares decomposition Synchronisation of coupled oscillators

来源：评论

学校读者我要写书评

暂无评论

POSITIVE POLYNOMIALS AND PROJECTIONS OF SPECTRAHEDRA

引用

SIAM JOURNAL ON OPTIMIZATION 2011年第3期21卷 960-976页

作者： Gouveia, Joao Netzer, Tim Univ Washington Dept Math Seattle WA 98195 USA Univ Coimbra CMUC Dept Math P-3001454 Coimbra Portugal Univ Leipzig Falkultat Math & Informat D-04009 Leipzig Germany

This article is concerned with different aspects of spectrahedra and their projections, sets that are important in semidefinite optimization. We prove results on the limitations of so-called Lasserre and theta body relaxation methods for semialgebraic sets and varieties. As a special case we obtain the main result of Netzer, Plaumann, and Schweighofer [SIAM J. Optim., 20 (2010), pp. 1944-1955] on nonexposed faces. We also solve the open problems from that work. We further give a unified account of several results on convex hulls of curves and images of polynomial maps. We finally prove a Positivstellensatz for projections of spectrahedra, which exceeds the known results that only work for basic closed semialgebraic sets.

关键词： semidefinite programming spectrahedra convex sets sums of squares linear matrix inequalities

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：