矩阵流形上的优化算法

需积分: 50 141 浏览量更新于2024-07-18 收藏 4.98MB PDF 举报

"Optimization Algorithms on Matrix Manifolds" 是一本书，由 P.-A. Absil、R. Mahony 和 R. Sepulchre 合著，探讨了在矩阵流形上的优化算法。这本书关注的是在几何约束条件下进行优化的问题，特别是那些解决方案局限于多面体的优化问题。矩阵流形优化算法相比传统的约束优化技术，具有更低的计算复杂性和更好的数值稳定性，因为它们直接在流形的低维度空间中操作，而不是在高维嵌入空间。优化算法是计算机科学和数学中的一个重要分支，用于寻找函数的最小值或最大值。在传统的约束优化中，解决方案需要满足一系列条件，这可能导致在高维空间中搜索，增加了计算的复杂性。然而，矩阵流形上的优化方法提供了一种新的视角，将问题限制在特定的几何结构上，如对称矩阵、正定矩阵或正交矩阵等，这些结构有自然的低维表示。书中的内容可能包括： 1. **矩阵流形基础**：介绍矩阵流形的基本概念，如欧氏空间中的子集，以及如何定义和操作这些流形。 2. **几何约束**：详细解释几何约束如何定义优化问题的解决方案空间，以及它们如何简化问题的结构。 3. **优化算法**：讨论在矩阵流形上运行的无约束优化算法，可能包括梯度下降法、牛顿法、拟牛顿法等，并解释它们如何适应流形的几何特性。 4. **应用实例**：展示这些算法在实际问题中的应用，可能包括控制系统、机器学习、信号处理、图像处理等领域。 5. **数值稳定性与效率**：分析在矩阵流形上优化算法的数值稳定性优势，以及如何减少计算复杂性。 6. **算法实现与代码示例**：可能包含实际实现这些算法的代码片段，帮助读者理解和应用理论知识。 7. **数学工具**：介绍必要的数学背景，如微分几何、线性代数和泛函分析，以便读者能够深入理解优化过程。 8. **未来研究方向**：探讨矩阵流形优化算法的最新进展和潜在的未来研究方向。通过这本书，读者可以学习到如何在特定的几何结构上设计和分析优化算法，这对于解决实际工程问题和理论研究都具有重要的价值。此外，作者们为能够提供最终的印刷版书籍而被特别提及，表明他们在出版过程中扮演了积极的角色。

3 INTRODUCTION

step in developing eﬃcient numerical algorithms on matrix manifolds. The

later

chapters on algorithms provide the core results of the book: the devel-

opment of Newton-based methods in Chapter 6 and of trust-region methods

in Chapter 7, and a survey of other superlinear methods such as conjugate

gradients in Chapter 8. We attempt to provide a generic development of

each of these methods, building upon the material of the geometric chap-

ters. The

methodology is then developed into concrete numerical algorithms

speciﬁc examples. In the analysis of superlinear and second-order meth-

ods, the concept of vector transport (introduced in Chapter 8) is used to

provide an eﬃcient implementation of methods such as conjugate gradient

and other quasi-Newton

methods. The algorithms obtained in these sections

of the

book are competitive with state-of-the-art numerical linear algebra

algorithms for certain problems.

The running example used throughout the book is the calculation of in-

variant subspaces of a matrix (and the many variants of this problem). This

example is

by far, for variants of algorithms developed within the proposed

framework, the problem with the broadest scope of applications and the

highest degree of

achievement to date. Numerical algorithms, based on a ge-

ometric

formulation, have been developed that compete with the best avail-

able algorithms for certain classes of

invariant subspace problems. These

algorithms are explicitly

described in the later chapters of the book and,

in part,

motivate the whole project. Because of the important role of this

class of problems within the book, the ﬁrst part of Chapter 2 provides a

detailed description of the invariant subspace problem, explaining why and

how this problem leads naturally to an optimization problem on a matrix

manifold. The second part of Chapter 2 presents other applications that can

be recast as problems of the same nature. These problems are the subject

of ongoing

research, and the brief exposition given is primarily an invitation

for

interested researchers to join with us in investigating these problems and

expanding the range of applications considered.

The book should primarily be considered a research monograph, as it

reports on recently published results in an active research area that is ex-

pected to develop signiﬁcantly beyond the material presented here. At the

same time,

every possible eﬀort has been made to make the book accessible

to the broadest audience, including applied mathematicians, engineers, and

computer

scientists with little or no background in diﬀerential geometry. It

could equally

well qualify as a graduate textbook for a one-semester course in

advanced optimization. More advanced sections that can be readily skipped

at a ﬁrst reading are indicated with a star.

Moreover, readers are encouraged

to visit the

book home page

where supplementary material is available.

The book is an extension of the ﬁrst author’s Ph.D. thesis [Abs03], itself a

project that drew heavily on the material of the second author’s Ph.D. the-

sis [Mah94]. It would not have been possible without the many contributions

of a quickly expanding research community that has been working in the area

http://press.princeton.edu/titles/8586.html

00˙AMS September 23, 2007

Chapter Two

Motivation and Applications

The problem of optimizing a real-valued function on a matrix manifold ap-

pears in a wide variety of computational problems in science and engineering.

In this chapter we discuss several examples that provide motivation for the

material presented in later chapters. In the ﬁrst part of the chapter, we focus

on the eigenvalue problem. This application receives special treatment be-

cause it serves as a running example throughout the book. It is a problem of

unquestionable importance that has been, and still is, extensively researched.

It falls naturally into the geometric framework proposed in this book as an

optimization problem whose natural domain is a matrix manifold—the un-

derlying symmetry is related to the fact that the notion of an eigenvector is

scale-invariant. Moreover, there are a wide range of related problems (eigen-

value decompositions, principal component analysis, generalized eigenvalue

problems, etc.) that provide a rich collection of illustrative examples that

we will use to demonstrate and compare the techniques proposed in later

chapters.

Later in this chapter, we describe several research problems exhibiting

promising symmetry to which the techniques proposed in this book have not

yet been applied in a systematic way. The list is far from exhaustive and is

very much the subject of ongoing research. It is meant as an invitation to

the reader to consider the broad scope of computational problems that can

be cast as optimization problems on manifolds.

2.1 A CASE STUDY: THE EIGENVALUE PROBLEM

The problem of computing eigenspaces and eigenvalues of matrices is ubiq-

uitous in engineering and physical sciences. The general principle of comput-

ing an eigenspace is to reduce the complexity of a problem by focusing on a

few relevant quantities and dismissing the others. Eigenspace computation

is involved in areas as diverse as structural dynamics [GR97], control the-

ory [PLV94], signal processing [CG90], and data mining [BDJ99]. Consider-

ing the importance of the eigenproblem in so many engineering applications,

it is not surprising that it has been, and still is, a very active ﬁeld of research.

Let F stand for the ﬁeld of real or complex numbers. Let A be an n × n

matrix with entries in F. Any nonvanishing vector v ∈ C

that satisﬁes

Av = λv

for some λ ∈ C is called an eigenvector of A; λ is the associated eigen-

00˙AMS September 23, 2007

6 CHAPTER 2

value, and the couple (λ, v) is called an eigenpair. The set of eigenvalues

of A is called the spectrum of A. The eigenvalues of A are the zeros of the

characteristic polynomial of A,

(z) ≡ det(A − zI),

and their algebraic multiplicity is their multiplicity as zeros of P

. If T

is an invertible matrix and (λ, v) is an eigenpair of A, then (λ, T v) is an

eigenpair of T AT

−1

. The transformation A 7→ T AT

−1

is called a similarity

transformation of A.

A (linear) subspace S of F

is a subset of F

that is closed under linear

combinations, i.e.,

∀x, y ∈ S, ∀a, b ∈ F : (ax + by) ∈ S.

A set {y

, . . . , y

} of elements of S such that every element of S can be

written as a linear combination of y

, . . . , y

is called a spanning set of S;

we say that S is the column space or simply the span of the n × p matrix

= [y

, . . . , y

] and that Y spans S. This is written as

S = span(Y ) = {Y x : x ∈ F

} = Y F

The matrix Y is said to have full (column) rank when the columns of Y are

linearly independent, i.e., Y x = 0 implies x = 0. If Y spans S and has full

rank, then the columns of Y form a basis of S. Any two bases of S have

the same number of elements, called the dimension of S. The set of all p-

dimensional subspaces of F

, denoted by Grass(p, n), plays an important role

in this book. We will see in Section 3.4 that Grass(p, n) admits a structure

of manifold called the Grassmann manifold.

The kernel ker(B) of a matrix B is the subspace formed by the vectors x

such that Bx = 0. A scalar λ is an eigenvalue of a matrix A if and only if

the dimension of the kernel of (A − λI) is greater than zero, in which case

ker(A − λI) is called the eigenspace of A related to λ.

An n × n matrix A naturally induces a mapping on Grass(p, n) deﬁned by

S ∈ Grass(p, n) 7→ AS := {Ay : y ∈ S}.

A subspace S is said to be an invariant subspace or eigenspace of A if AS ⊆

S. The restriction A|

of A to an invariant subspace S is the operator

7→ Ax whose domain is S. An invariant subspace S of A is called spectral

if, for every eigenvalue λ of A

, the multiplicities of λ as an eigenvalue of A

| |

and as an eigenvalue of A are identical; equivalently, X

AX and X

⊥

have no eigenvalue in common when [X|X

⊥

] satisﬁes [X|X

⊥

]

[X|X

⊥

] = I

and span(X) = S.

In many (arguably the majority of) eigenproblems of interest, the matrix

is real and symmetric (A = A

). The eigenvalues of an n × n symmetric

matrix A are reals λ

≤ ··· ≤ λ

, and the associated eigenvectors v

, . . . , v

are real and can be chosen orthonormal, i.e.,

(

1 if i = j,

0 if i = j.

00˙AMS September 23, 2007

7 MOTIVATION AND APPLICATIONS

Equivalently, for every symmetric matrix A, there is an orthonormal matrix

(whose columns are eigenvectors of A) and a diagonal matrix Λ such that

A = V

ΛV

. The eigenvalue λ

is called the leftmost eigenvalue of A, and

an eigenpair (λ

, v

) is called a leftmost eigenpair. A p-dimensional leftmost

invariant subspace is an invariant subspace associated with λ

, . . . , λ

. Sim-

ilarly, a p-dimensional rightmost invariant subspace is an invariant subspace

associated with λ

n−p+1

, . . . , λ

. Finally, extreme eigenspaces refer collec-

tively to leftmost and rightmost eigenspaces.

Given two n × n matrices A and B, we say that (λ, v) is an eigenpair of

the pencil (A, B) if

Av = λBv.

Finding eigenpairs of a matrix pencil is known as the generalized eigen-

value problem. The generalized eigenvalue problem is said to be symmetric /

positive-deﬁnite when A is symmetric and B is symmetric positive-deﬁnite

(i.e., x

Bx > 0 for all nonvanishing x). In this case, the eigenvalues of

the pencil are all real and the eigenvectors can be chosen to form a B-

orthonormal basis. A subspace Y is called a (generalized) invariant subspace

(or a deﬂating subspace) of the symmetric / positive-deﬁnite pencil (A, B)

if B

−1

Ay ∈ Y for all y ∈ Y, which can also be written B

−1

AY ⊆ Y or

AY ⊆ BY. The simplest example is when Y is spanned by a single eigen-

vector of (A, B), i.e., a nonvanishing vector y such that Ay = λBy for some

eigenvalue λ. More generally, every eigenspace of a symmetric / positive-

deﬁnite pencil is spanned by eigenvectors of (A, B). Obviously, the general-

ized eigenvalue problem reduces to the standard eigenvalue problem when

B =

2.1.1 The eigenvalue problem as an optimization problem

The following result is instrumental in formulating extreme eigenspace com-

putation as an optimization problem. (Recall that tr(A), the trace of A,

denotes the sum of the diagonal elements of A.)

Proposition 2.1.1 Let A and B be symmetric n × n matrices and let B be

positive-deﬁnite. Let λ

≤ ··· ≤ λ

be the eigenvalues of the pencil (A, B).

Consider the generalized Rayleigh quotient

f(Y ) = tr(Y

AY (Y

BY )

−1

) (2.1)

deﬁned on the set of all n × p full-rank matrices. Then the following state-

ments are equivalent:

(i) span(Y

∗

) is a leftmost invariant subspace of (A, B);

(ii) Y

∗

is a global minimizer of (2.1) over all n × p full-rank matrices;

(iii) f(Y

∗

) =

i=1

Proof. For simplicity of the development we will assume that λ

< λ

p+1

but

the result also holds without this hypothesis. Let V be an n × n matrix

for which V

BV = I

and V

AV = diag(λ

, . . . , λ

), where λ

≤ ··· ≤ λ

剩余236页未读，继续阅读

季秋暖阳

粉丝: 0
资源: 1

矩阵流形上的优化算法

Convex Optimization Algorithms

proximal policy optimization algorithms

an overview of gradient descent optimization algorithms

evolutionary optimization algorithms by dan simon 中文版

from torch import optim

r语言画model parameter optimization based on 10-fold cross validation

Genetic Algorithms in Search, Optimization and Machine Learning

ConvergenceWarning: Maximum Likelihood optimization failed to converge

combinatorial optimization: algorithms pan.baidu.com

最新资源