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

Fastest mixing Markov chain on a graph

SIAM REVIEW 2004年第4期46卷 667-689页

作者： Boyd, S Diaconis, P Xiao, L Stanford Univ Dept Elect Engn Informat Syst Lab Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA Stanford Univ Dept Math Stanford CA 94305 USA

We consider a symmetric random walk on a connected graph, where each edge is labeled with the probability of transition between the two adjacent vertices. The associated Markov chain has a uniform equilibrium distribution;the rate of convergence to this distribution, i.e., the mixing rate of the Markov chain, is determined by the second largest eigenvalue modulus (SLEM) of the transition probability matrix. In this paper we address the problem of assigning probabilities to the edges of the graph in such a way as to minimize the SLEM, i.e., the problem of finding the fastest mixing Markov chain on the graph. We show that this problem can be formulated as a convex optimization problem, which can in turn be expressed as a semidefinite program (SDP). This allows us to easily compute the (globally) fastest mixing Markov chain for any graph with a modest number of edges (say, 1000) using standard numerical methods for SDPs. Larger problems can be solved by exploiting various types of symmetry and structure in the problem, and far larger problems (say, 100,000 edges) can be solved using a subgradient method we describe. We compare the fastest mixing Markov chain to those obtained using two commonly used heuristics: the maximum-degree method, and the Metropolis-Hastings algorithm. For many of the examples considered, the fastest mixing Markov chain is substantially faster than those obtained using these heuristic methods. We derive the Lagrange dual of the fastest mixing Markov chain problem, which gives a sophisticated method for obtaining (arbitrarily good) bounds on the optimal mixing rate, as well as the optimality conditions. Finally, we describe various extensions of the method, including a solution of the problem of finding the fastest mixing reversible Markov chain, on a fixed graph, with a given equilibrium distribution.

关键词： Markov chains second largest eigenvalue modulus fast mixing semidefinite programming subgradient method

来源：评论

学校读者我要写书评

暂无评论

An existence result for polynomial solutions of parameter-dependent LMIs

引用

SYSTEMS & CONTROL LETTERS 2004年第3-4期51卷 165-169页

作者： Bliman, PA Inst Natl Rech Informat & Automat F-78153 Le Chesnay France

We show in this paper that any system of linear matrix inequalities depending continuously upon scalar parameters and solvable for any value of the latter in a fixed compact set, admits a branch of solutions polynomial with respect to the parameters. This result is useful for studying, e.g. parametric robustness or gain-scheduling issues. (C) 2003 Elsevier B.V. All rights reserved.

关键词： linear matrix inequalities semidefinite programming polynomial dependence parametric robustness gain-scheduling

来源：评论

学校读者我要写书评

暂无评论

Optimal detection of symmetric mixed quantum states

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2004年第6期50卷 1198-1207页

作者： Eldar, YC Megretski, A Verghese, GC MIT Res Lab Elect Cambridge MA 02139 USA MIT Lab Informat & Decis Syst Cambridge MA 02139 USA MIT Lab Electromagnet & Elect Syst Cambridge MA 02139 USA

We develop a sufficient condition for the least-squares measurement (LSM), or the square-root measurement, to minimize the probability of a detection error when distinguishing between a collection of mixed quantum states. Using this condition we derive the optimal measurement for state sets with a broad class of symmetries. We first consider geometrically uniform (GU) state sets with a possibly non-Abelian generating group, and show that if the generator satisfies a weighted norm constraint, then the LSM is optimal. In particular, for pure-state GU ensembles, the LSM is shown to be optimal. For arbitrary GU state sets we show that the optimal measurement operators are GU with generator that can be computed very efficiently in polynomial time, within any desired accuracy. We then consider compound GU (CGU) state sets which consist of subsets that are GU. When the generators satisfy a certain constraint, the LSM is again optimal. For arbitrary CGU state sets, the optimal measurement operators are shown to be CGU with generators that can be computed efficiently in polynomial time.

关键词： compound geometrically uniform (CGU) quantum states geometrically uniform quantum states least-squares measurement (LSM) mixed quantum states quantum detection semidefinite programming square-root measurement

来源：评论

学校读者我要写书评

暂无评论

Best ellipsoidal relaxation to solve a nonconvex problem

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2004年第1期162卷 183-191页

作者： El Bernoussi, S Univ Mohammed 5 Fac Sci Dept Math & Comp Rabat Morocco

We present a new ellipsoidal relaxation of 0-1 quadratic optimization problems. The relaxation and the dual problem are derived. Both these problems are strictly feasible;so strong duality holds, and they can be solved numerically using primal-dual interior-point methods. Numerical results are presented which indicate that the described relaxation is efficient. (C) 2003 Published by Elsevier B.V.

关键词： quadratic boolean programming quadratic programming ellipsoidal relaxation semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Cardinality constrained minimum cut problems: complexity and algorithms

引用

DISCRETE APPLIED MATHEMATICS 2004年第3期137卷 311-341页

作者： Bruglieri, M Maffioli, F Ehrgott, M Politecn Milan Dipartimento Elettr & Informat I-20133 Milan Italy Univ Auckland Dept Engn Sci Auckland New Zealand

In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a fixed number of elements. So far the family of (COP) with cardinality constraints has been little investigated. The present work tackles a new problem of this class: the k-cardinality minimum cut problem (k-card cut). For a number of variants of this problem we show complexity results in the most significant graph classes. Moreover, we develop several heuristic algorithms for the k-card cut problem for complete, complete bipartite, and general graphs. Lower bounds are obtained through an SDP formulation, and used to show the quality of the heuristics. Finally, we present a randomized SDP heuristic and numerical results. (C) 2003 Elsevier B.V. All rights reserved.

关键词： cut problems k-cardinality minimum cut cardinality constrained combinatorial optimization computational complexity semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

semidefinite relaxation based multiuser detection for M-ary PSK multiuser systems

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2004年第10期52卷 2862-2872页

作者： Ma, WK Ching, PC Ding, Z Chinese Univ Hong Kong Dept Elect Engn Shatin Hong Kong Peoples R China Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

Because of the powerful symbol error performance of multiuser maximum-likelihood (ML) detection, recently, there has been much interest in seeking effective ways of approximating multiuser ML detection (MLD) with affordable computational costs. It has been illustrated that for the synchronous code division multiple access (CDMA) scenario, the so-called semidefinite relaxation (SDR) algorithm can accurately and efficiently approximate multiuser MLD. This SDR-MLD algorithm, however, can only handle binary and quadratic phase shift keying (PSK) symbol constellations. In this sequel, we propose an extended SDR algorithm for MLD with M-ary PSK (MPSK) constellations. For the synchronous CDMA scenario, the proposed SDR algorithm provides an attractive polynomial-time complexity order of K-3.5, where K is the number of users. Simulation results indicate that the proposed detector provides improved symbol error performance compared with several commonly used multiuser detectors.

关键词： M-ary phase shift keying maximum likelihood detection multiuser detection relaxation methods semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems

引用

SIAM JOURNAL ON OPTIMIZATION 2004年第3期14卷 783-806页

作者： Sun, J Sun, DF Qi, LQ Natl Univ Singapore Sch Business Singapore 117548 Singapore Natl Univ Singapore Singapore MIT Alliance Singapore 117548 Singapore Natl Univ Singapore Dept Math Singapore 117548 Singapore Hong Kong Polytech Univ Dept Appl Math Hong Kong Hong Kong Peoples R China

We study a smoothing Newton method for solving a nonsmooth matrix equation that includes semidefinite programming and the semidefinite complementarity problem as special cases. This method, if specialized for solving semidefinite programs, needs to solve only one linear system per iteration and achieves quadratic convergence under strict complementarity and nondegeneracy. We also establish quadratic convergence of this method applied to the semidefinite complementarity problem under the assumption that the Jacobian of the problem is positive definite on the affine hull of the critical cone at the solution. These results are based on the strong semismoothness and complete characterization of the B-subdifferential of a corresponding squared smoothing matrix function, which are of general theoretical interest.

关键词： matrix equations Newton's method nonsmooth optimization semidefinite complementarity problem semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Improving the most general methodology to create a valid correlation matrix

Improving the most general methodology to create a valid cor...

引用

4th International Conference on Computer Simulation in Risk Analysis and Hazard Mitigation

作者： Schöttle, K Werner, R Tech Univ Munich HVB Stiftungsinst Finanzmath D-8000 Munich Germany

ISBN: (纸本)1853127361

Jaeckel and Rebonato [1] develop two different methods of creating valid correlation matrices: construction by hypersphere decomposition and by singular value (i.e. spectral) decomposition. Although both methods yield satisfactory results in practice, from a mathematical point of view they both share some theoretical drawbacks. Using results from semidefinite programming (SDP) we give the most general problem formulation to compute valid correlation matrices. We present numerical results which prove that these SDPs are rather easily solvable with efficient solvers for SDP problems (e.g. PENNON, see [3]). In contrast to Higham [2] we do not find numerical difficulties in solving the stated SDP problems. We close the article with two more very important features which have been neglected in literature so far. First, regularity and second, control of the condition number of the resulting correlation matrix are easily guaranteed by linear SDP-constraints. Numerical experiments show that these additional constraints do not harm the efficient numerical solution.

关键词： correlation matrix semidefinite programming risk management

来源：评论

学校读者我要写书评

暂无评论

Analysis of nonlinear time-delay systems using the sum of squares decomposition

Analysis of nonlinear time-delay systems using the sum of sq...

引用

American Control Conference

作者： Papachristodoulou, A CALTECH Control & Dynam Syst Pasadena CA 91125 USA

ISBN: (纸本)0780383354

The use of the sum of squares decomposition and semidefinite programming have provided an efficient methodology for analysis of nonlinear systems described by ODES by algorithmically constructing Lyapunov functions. Based on the same methodology we present an algorithmic procedure for constructing Lyapunov-Krasovskii functionals for nonlinear time delay systems described by Functional Differential Equations (FDEs) both for delay-dependent and delay-independent stability analysis. Robust stability analysis of these systems under parametric uncertainty can be treated in a unified way. We illustrate the results with an example from population dynamics.

关键词： nonlinear systems delays Lyapunov methods differential equations stability control system analysis nonlinear time-delay systems sum of squares decomposition semidefinite programming Lyapunov functions Lyapunov-Krasovskii functional functional differential equations delay-dependent stability analysis delay-independent stability analysis parametric uncertainty

来源：评论

学校读者我要写书评

暂无评论

Control design for topology-independent stability of interconnected systems

Control design for topology-independent stability of interco...

引用

American Control Conference

作者： Cogill, R Lall, S Stanford Univ Dept Elect Engn Stanford CA 94305 USA

ISBN: (纸本)0780383354

In this paper we present a method for synthesis of decentralized controllers for multiple identical systems interconnected on a graph. We develop a synthesis procedure for controllers which will stabilize the system for any graph topology satisfying given degree bounds, independent of the size of the graph. The methods reduce to computation via semidefinite programming, and the size of the resulting optimization problem does not grow with the size of the graph. We also show how these results may be extended to construct partially decentralized controllers which receive measurements from their neighbors. We illustrate the results via an example of a power distribution network.

关键词： interconnected systems control system synthesis decentralised control stability graph theory optimisation control system design topology independent stability decentralized controller synthesis multiple identical systems graph topology semidefinite programming optimization problem partially decentralized controllers power distribution network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：