Optimization Algorithms on Matrix Manifolds

所需积分/C币:50 2018-09-01 21:00:39 4.98MB PDF
收藏 收藏

作为一个研究领域,约束优化已经非常成熟,并且存在一些解决该领域一般问题的强大技术。 在本书中,考虑了一类特殊约束,称为几何约束,它表示优化问题的解决方案存在于多方面。 这是最近的研究领域,为更一般的约束优化方法提供了强有力的替代方案。 经典约束优化技术在嵌入空间中工作,该嵌入空间的尺寸可以比歧管的尺寸大得多。 因此,在歧管上工作的优化算法具有较低的复杂性并且通常还具有更好的数值特性(例如,参见保持诸如能量的不变量的数值积分方案)。 作者将此称为约束搜索空间中的无约束优化。
Optimization Algorithms on Matrix manifolds P-A. Abs R. Mahony R. Sepulchre PRINCETON UNIVERSITY PRESS PRINCETON AND OXFORD Copyright 2008 by Princeton University Press Published by princeton University Pros 41 William Street, Princeton, New Jersey 08540 In the Unitcd Kingdom: Princeton University Press 3 Market Place. Woodstock. Oxfordshire OX20 1SY All Rights reserved Library of Congress Control Number: 2007927538 ISBN:978-0-691-13298-3 British Library Cataloging-in-Publication Data is available This book has been composed in Computer Modern in LATEX The publisher would like to acknowledge the authors of this volume for providing the camera-ready copy from which this book was printed Printed on acid-free paper oo press. princeton. cdu Printed in the United States of America 10987654321 0 our parents Contents List of algorithms Foreword, by Paul Van Dooren Notation Conventions 1. Introduction 2. Motivation and Applications 2.1 A case study: the eigenvalue problem 2.1.1 The eigenvalue problem as an optimization problem 2.1.2 Some benefits of an optimization framework 2.2R 2.2.1 Singular value problem 2.2.2 Matrix approximations 2.2.3 Independent component analysis 2.2.4 Pose estimation and motion recovery 2.3 Notes a id references 3. Matrix Manifolds: First-Order Geometry 3.1 Manifolds 3.1. 1 Definitions: charts. atlases, manifolds 3. 1.2 The topology of a manifold* 20 3.1.3 How to recognize a manifold 3.1.4 Vector spaces as manifolds 3.1.5 The manifolds rnxp and rrxe 3.1.6 Product manifolds 3.2 Differentiable functions 3.2.1 Immersions and submersions 3.3 Embedded submanifolds 3.3. 1 General theory 3.3.2 The Stiefel manifold 2 3.4 Quotient manifolds 3.4.1 Theory of quotient manifolds 3.4.2 Functions on quotient manifolds 3.4.3 The real projective space RP 3.4.4 The Grassmann manifold Grass(p, n) 3.5 Tangent vectors and diffcrcntial maps CONTENTS 3.5.1 Tangent vectors 3.5.2 Tangent vectors to a vector space 3.5.3 Tangent bundle 3.5.4 Vector fields 3.5.5 Tangent vectors as derivations 3.5.6 Differential of a mapping 6780 3.5.7 Tangent vectors to embedded submanifold 8.5.8 Tangent vectors to quotient manifolds 3.6 Riemannian metric, distance, and gradients 3.6.1 Riemannian submanifolds 3.6.2 Riemannian quotient manifolds 3.7 Notes and reference 4. Line-Search Algorithms on Manifolds 4.1 Retractions 4.1.1 Retractions on embedded submanifolds 4.1.2 Retractions on quotient manifolds 4.1.3 Retractions and local coordinates* 4.2 Line-search methods 4.3 Convergence analysis 1.3.1 Convergence on manifolds 4.3.2 A topological curiosity 64 4.3.3 Convergence of line-search methods 4.4 Stability of fixe 4.5 Speed of convergence 4.5.1 Order of convergence 4.5.2 Rate of convergence of line-search methods* 4.6 Rayleigh quotient minimization on the sphere 4.6.1 Cost function and gradient calculation 4.6.2 Critical points of the Rayleigh quotient 4.6.3 Armijo li. 4.6.4 Exact line search 4.6.5 Accelerated line search: locally optimal conjugate gradient 4.66.6 Links with the power method and inverse iteration 4.7 Refining 4.8 Brockett cost function on the Stiefel manl 4.8.1 Cost function and search direction 4.8.2 Critical points 4.9 Rayleigh quotient minimization on the Grassmann manifold 4.9.1 Cost function and gradient calculation 4.9.2 Line-search algorith 4.10 Notes and rcfcrcnccs 5. Matrix Manifolds: Second-Order Geometry 5.1 Newto 5.2 Affinc connections CONTENTS 5.3 Riemannian connection 5. 3. 1 Symmetric connections 96 5.3.2 Dcfinition of the ricr 5.3.3 Riemannian connection on Riemannian submanifolds 5.3.4 Riemannian connection on quotient manifolds 5.4 Geodesics, exponential Napping, and parallel translation 5.5 Riemannian Hessian operator 5.6 Second covariant derivative 5.7 Note d referen 6. Newton's Method 6.1 Newton's method on manifolds 6.2 Riemannian Newton method for real-valued functions 6.3 Local convergence 6.3.1 Calculus approach to local convergence analysis 6.4 Rayleigh quotient algorith 6. 4. 1 Rayleigh quotient on the sphere 11 6.4.2 Rayleigh quotient on the Grassmann manifold 6.4.3 Generalized eigenvalue problem 121 6.4.4 The nonsymmetric eigenvalue problem 12 6.4.5 Newton with su bspacc accelcration: Jacobi-Davidson 6.5 Analysis of Rayleigh quotient algorithms 12 6.5.1 Convergence analysis 128 6.5.2 Numerical implementation 129 6.6 Notes and references 131 7 Trust -R Methods 7.1 Models 137 7.1.1 Models in r 137 7.1.2 Models in genera.I Euclidean spaces 137 7. 1.3 Models on Riemannian manifolds 13 7.2 Trust-region method 7.2.1 Trust-region methods in R 140 7.2.2 Trust-region methods on Riemannian manifolds 40 7. 3 Computing a trust-region step 141 7.3.1 Computing a nearly exact solution 142 7.3.2 Improving on the Cauchy point 7.4 Convergence analysis 7.4.1 Global convergence 45 7.4.2 Local convergence 15 7. 4.3 Discussion 7.5 Applications 7.5. 1 Checkli 7.5.2 Symmetric eigenvalue decomposition 7.5.3 Computing an extreme eigenspace 7.6 Notes and references 8. A Constellation of Superlinear Algorithms 168 CONTENTS 8.1 Vector transport 8.1.1 Vector transport and affine connections 17 8.1.2 Vector tr 8.1.3 Vector transport on Ricmannian submanifolds 174 8.1.4 Vector transport on quotient manifolds 8.2 Approximate Ne 8.2.1 Finite difference approximations 176 8.3 Conjugate gradients 8.3.1 Application: Rayleigh quotient, minimization 8.4 Least-square method 184 8.4.1 Gauss-Newton methods 8.1.2 Levenberg-Marquardt methods 8.5 Notes and references A. Elements of Linear Algebra, Topology, and calculus A 1 Linear algebr A 2 Topology A 3 Functions 193 A 4A 194 A.5 Derivatives 195 A 6 Taylor's formula Bibliography List of algorithms 1 Accclcratcd Linc Scarch (ALS 2 Armijo line search for the Rayleigh quotient on Sm-T 3 Armijo line search for the Rayleigh quotient on Grass(p, n) 456 Geometric Newton method for vector fields Riemannian newton method for real-valued functions Riemannian Newton method for the Rayleigh quotient on 7 Ricmannian Nowton mcthod for the Rayleigh quotient on Grass(p, n 8 Riemannian Newton method for the Rayleigh quotient or Grass(p, n) 9 Jacobi-Davidson 2 10 Riemannian trust-region(RTR) meta-algorithm 142 11 Truncated CG(tCG) method for the trust-region subprob- 12 Truncated CG method for the generalized eigenvalue prob- lem 13 Geometric CG method 182 14 Riemannian Gauss-Newton method 186

试读 127P Optimization Algorithms on Matrix Manifolds
立即下载 低至0.43元/次 身份认证VIP会员低至7折
Optimization Algorithms on Matrix Manifolds 50积分/C币 立即下载
Optimization Algorithms on Matrix Manifolds第1页
Optimization Algorithms on Matrix Manifolds第2页
Optimization Algorithms on Matrix Manifolds第3页
Optimization Algorithms on Matrix Manifolds第4页
Optimization Algorithms on Matrix Manifolds第5页
Optimization Algorithms on Matrix Manifolds第6页
Optimization Algorithms on Matrix Manifolds第7页
Optimization Algorithms on Matrix Manifolds第8页
Optimization Algorithms on Matrix Manifolds第9页
Optimization Algorithms on Matrix Manifolds第10页
Optimization Algorithms on Matrix Manifolds第11页
Optimization Algorithms on Matrix Manifolds第12页
Optimization Algorithms on Matrix Manifolds第13页
Optimization Algorithms on Matrix Manifolds第14页
Optimization Algorithms on Matrix Manifolds第15页
Optimization Algorithms on Matrix Manifolds第16页
Optimization Algorithms on Matrix Manifolds第17页
Optimization Algorithms on Matrix Manifolds第18页
Optimization Algorithms on Matrix Manifolds第19页
Optimization Algorithms on Matrix Manifolds第20页

试读结束, 可继续阅读

50积分/C币 立即下载 >