Convex Optimization & Euclidean Distance Geometry
I thought I'd use this book as a reference since the unusually large Index is a good place to locate the definitions. Dattorro starts from the basic premises and works through the algebra with many examples and many good illustrations.
I've found that Dattorro's perspective on each subject (optimization and distance geometry) is both algebraic and geometric. He bridges those unexpectedly well. His approach to rank minimization, for example, is how I would have thought of doing it, in terms of eigenvalues. It feels right to me.
Dattorro's notation is "progressive." A vector is represented by a single letter, say x, with no embellishment to distingush it from a real variable. That makes the presentation simple, but takes some getting used to as does his style of "missing articles" (e.g. the) and replacement everywhere of "i.e." with latin "id est."
The book is organized by convex optimzation first then distance geometry second,
three chapters devoted to each. The appendices support seven chapters total and take half the book! It's a big book.
Dattorro's treatment of distance geometry is the book's main strength. The main result is a new expression for the relationship between the semidefinite positive and Euclidean distance cones, and takes a long time to get there. Along the way, he goes back to 1935 and integrates the results of Schoenberg (before modern linear algebra), Cayley and Menger, Critchley, Gower, then augments that with some later results like Hayden, Wells, Liu, & Tarazaga, and then more contemporary results like Deza & Laurent, Wolkowicz, Saul and Weinberger to name only a few. Then, of course he shows how that all relates to optimization. I particularly liked the geographical map reconstruction examples where only distance ordering was known.
I recommend this book to anyone who wants both a good introduction to convex optimization and a reference to some latest techniques, a few of which Dattorro may have invented. There is a good review of semidefinite programming, and what he writes about distance geometry refreshes old math with new.
Author(s): Jon Dattorro
Publisher: Meboo Publishing
Year: 2008
Language: English
Pages: 812
front cover......Page 1
binding......Page 2
title......Page 3
© copyright......Page 4
Prelude......Page 7
Contents......Page 9
List of Figures......Page 13
List of Tables......Page 19
1 Overview......Page 21
2 Convex geometry......Page 35
2.1 Convex set......Page 36
2.2 Vectorized-matrix inner product......Page 49
2.3 Hulls......Page 59
2.4 Halfspace, Hyperplane......Page 71
2.5 Subspace representations......Page 83
2.6 Extreme, Exposed......Page 88
2.7 Cones......Page 93
2.8 Cone boundary......Page 102
2.9 Positive semidefinite (PSD) cone......Page 109
2.10 Conic independence (c.i.)......Page 132
2.12 Convex polyhedra......Page 138
2.13 Dual cone & generalized inequality......Page 147
3 Geometry of convex functions......Page 209
3.1 Convex function......Page 210
3.3 Practical norm functions, absolute value......Page 214
3.4 Inverted functions and roots......Page 223
3.5 Affine function......Page 226
3.6 Epigraph, Sublevel set......Page 230
3.7 Gradient......Page 238
3.8 Matrix-valued convex function......Page 250
3.9 Quasiconvex......Page 256
3.10 Salient properties......Page 259
4 Semidefinite programming......Page 261
4.1 Conic problem......Page 262
4.2 Framework......Page 271
4.3 Rank reduction......Page 285
4.4 Rank-constrained semidefinite program......Page 294
4.5 Constraining cardinality......Page 315
4.6 Cardinality and rank constraint examples......Page 332
4.7 Convex Iteration rank-1......Page 367
5 Euclidean Distance Matrix......Page 373
5.1 EDM......Page 374
5.3 fifth Euclidean metric property......Page 375
5.4 EDM definition......Page 380
5.5 Invariance......Page 412
5.6 Injectivity of D & unique reconstruction......Page 417
5.7 Embedding in affine hull......Page 423
5.8 Euclidean metric versus matrix criteria......Page 428
5.9 Bridge: Convex polyhedra to EDMs......Page 436
5.10 EDM-entry composition......Page 443
5.11 EDM indefiniteness......Page 446
5.12 List reconstruction......Page 454
5.13 Reconstruction examples......Page 458
5.14 Fifth property of Euclidean metric......Page 464
6 Cone of distance matrices......Page 475
6.1 Defining EDM cone......Page 477
6.2 Polyhedral bounds......Page 479
6.3 EDM cone is not convex......Page 481
6.4 A geometry of completion......Page 482
6.5 EDM definition in 11T......Page 488
6.6 Correspondence to PSD cone S+N-1......Page 496
6.7 Vectorization & projection interpretation......Page 502
6.8 Dual EDM cone......Page 507
6.9 Theorem of the alternative......Page 521
6.10 Postscript......Page 523
7 Proximity problems......Page 525
7.1 First prevalent problem:......Page 533
7.2 Second prevalent problem:......Page 544
7.3 Third prevalent problem:......Page 555
7.4 Conclusion......Page 566
A.1 Main-diagonal operator, , trace, vec......Page 569
A.2 Semidefiniteness: domain of test......Page 574
A.3 Proper statements......Page 577
A.4 Schur complement......Page 589
A.5 Eigen decomposition......Page 594
A.6 Singular value decomposition, SVD......Page 597
A.7 Zeros......Page 602
B Simple matrices......Page 609
B.1 Rank-one matrix (dyad)......Page 610
B.2 Doublet......Page 615
B.3 Elementary matrix......Page 616
B.4 Auxiliary V-matrices......Page 618
B.5 Orthogonal matrix......Page 623
C.1 Properties of infima......Page 627
C.2 Trace, singular and eigen values......Page 628
C.3 Orthogonal Procrustes problem......Page 634
C.4 Two-sided orthogonal Procrustes......Page 636
D.1 Directional derivative, Taylor series......Page 641
D.2 Tables of gradients and derivatives......Page 662
E Projection......Page 671
E.1 Idempotent matrices......Page 675
E.2 I---P, Projection on algebraic complement......Page 680
E.3 Symmetric idempotent matrices......Page 681
E.4 Algebra of projection on affine subsets......Page 686
E.5 Projection examples......Page 687
E.6 Vectorization interpretation,......Page 693
E.7 Projection on matrix subspaces......Page 701
E.9 Projection on convex set......Page 705
E.10 Alternating projection......Page 719
F Notation and a few definitions......Page 739
Bibliography......Page 755
Index......Page 783
back cover......Page 812
