Convex Optimization Euclidean Distance Geometry 2 PDF

14d ago
1 Views
0 Downloads
208.91 KB
9 Pages
Transcription

Convex OptimizationEuclidean Distance Geometry 2ε1 Overview2 Convex geometry2.1 Convex set . . . . . . . . . . . . .2.2 Vectorized-matrix inner product .2.3 Hulls . . . . . . . . . . . . . . . . .2.4 Halfspace, Hyperplane . . . . . . .2.5 Subspace representations . . . . . .2.6 Extreme, Exposed . . . . . . . . .2.7 Cones . . . . . . . . . . . . . . . .2.8 Cone boundary . . . . . . . . . . .2.9 Positive semidefinite (PSD) cone .2.10 Conic independence (c.i.) . . . . .2.11 When extreme means exposed . . .2.12 Convex polyhedra . . . . . . . . .2.13 Dual cone & generalized inequality19.313142505869747785901111151161223 Geometry of convex functions3.1 Convex real and vector-valued function . . . . . .3.2 Practical norm functions, absolute value . . . . .3.3 Powers, roots, and inverted functions . . . . . . .3.4 Affine function . . . . . . . . . . . . . . . . . . .3.5 Epigraph, Sublevel set . . . . . . . . . . . . . . .3.6 Gradient . . . . . . . . . . . . . . . . . . . . . . .3.7 First-order convexity condition, real function . .3.8 First-order convexity condition, vector-valued . .3.9 Second-order convexity condition, vector-valued .3.10 Convex matrix-valued function . . . . . . . . . .3.11 First-order convexity condition, matrix-valued . .3.12 Epigraph of matrix-valued function, sublevel sets3.13 Second-order convexity condition, matrix-valued3.14 Quasiconvex . . . . . . . . . . . . . . . . . . . . .3.15 Salient properties . . . . . . . . . . . . . . . . . 4 Semidefinite programming4.1 Conic problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3 Rank reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9223. 224. 230. 240

10EUCLIDEAN DISTANCE GEOMETRY 2εCONVEX OPTIMIZATION4.44.54.64.74.84.94.10Cardinality reduction . . . . . . . . . . . .Rank constraint by Convex Iteration . . .Constraining cardinality . . . . . . . . . .Cardinality and rank constraint examplesQuantum optimization . . . . . . . . . . .Constraining rank of indefinite matrices .Convex Iteration rank -1 . . . . . . . . . 3893943974014054096 Cone of distance matrices6.1 Defining EDM cone . . . . . . . . . . . . .6.2 Polyhedral bounds . . . . . . . . . . . . .6.3EDM cone is not convex . . . . . . . . .6.4 EDM definition in 11T . . . . . . . . . . . 16.5 Correspondence to PSD cone SN. . . . 6.6 Vectorization & projection interpretation6.7 A geometry of completion . . . . . . . . .6.8 Dual EDM cone . . . . . . . . . . . . . . .6.9 Theorem of the alternative . . . . . . . .6.10 Postscript . . . . . . . . . . . . . . . . . .4174184204214214284324384434554557 Proximity problems7.1 First prevalent problem: .7.2 Second prevalent problem:7.3 Third prevalent problem:7.4 Conclusion . . . . . . . .457462470478485.487. 487. 490. 493. 501. 505. 508. 5125 Euclidean Distance Matrix5.1 EDM . . . . . . . . . . . . . . . . . . . .5.2 First metric properties . . . . . . . . . .5.3 fifth Euclidean metric property . . . .5.4 EDM definition . . . . . . . . . . . . . .5.5 Invariance . . . . . . . . . . . . . . . . .5.6 Injectivity of D & unique reconstruction5.7 Embedding in affine hull . . . . . . . . .5.8 Euclidean metric versus matrix criteria5.9 Bridge: Convex polyhedra to EDMs . .5.10 EDM-entry composition . . . . . . . . .5.11 EDM indefiniteness . . . . . . . . . . . .5.12 List reconstruction . . . . . . . . . . . .5.13 Reconstruction examples . . . . . . . . .5.14 Fifth property of Euclidean metric . . .A Linear algebraA.1 Main-diagonal δ operator, λ , tr , vec , , A.2 Semidefiniteness: domain of test . . . . . . . .A.3 Proper statements of positive semidefiniteness .A.4 Schur complement . . . . . . . . . . . . . . . .A.5 Eigenvalue decomposition . . . . . . . . . . . .A.6 Singular value decomposition, SVD . . . . . . .A.7 Zeros . . . . . . . . . . . . . . . . . . . . . . . .

EUCLIDEAN DISTANCE GEOMETRY 2εCONVEX OPTIMIZATIONB Simple matricesB.1 Rank-1 matrix (dyad)B.2 Doublet . . . . . . . .B.3 Elementary matrix . .B.4 Auxiliary V -matrices .B.5 Orthomatrices . . . . .B.6 Arrow matrix . . . . .11.517517521522524527532C Some analytical optimal resultsC.1 Properties of infima . . . . . . .C.2 Trace, singular and eigen values .C.3 Orthogonal Procrustes problem .C.4 Two-sided orthogonal ProcrustesC.5 Quadratics . . . . . . . . . . . .535535536541543546.D Matrix calculus549D.1 Gradient, Directional derivative, Taylor series . . . . . . . . . . . . . . . . . 549D.2 Tables of gradients and derivatives . . . . . . . . . . . . . . . . . . . . . . . 564E ProjectionE.1 Idempotent matrices . . . . . . . . . . . . .E.2 I P , Projection on algebraic complementE.3 Symmetric idempotent matrices . . . . . . .E.4 Algebra of projection on affine subsets . . .E.5 Projection examples . . . . . . . . . . . . .E.6 Vectorization interpretation . . . . . . . . .E.7 Projection on matrix subspaces . . . . . . .E.8 Range, Rowspace interpretation . . . . . . .E.9 Projection on convex set . . . . . . . . . . .E.10 Alternating projection . . . . . . . . . . . .573577580581585586593598600601612F Notation, Definitions, Glossary629Bibliography645Index667

List of Tables2 Convex geometryTable 2.9.2.3.1, rank versus dimension of S3 faces97Table 2.10.0.0.1, maximum number of c.i. directions111Cone Table 1151Cone Table S152Cone Table A153Cone Table 1*1574 Semidefinite programming3Faces of S3 corresponding to faces of S 228Quantum impulse328Quantum step330Quantum and function3305 Euclidean Distance MatrixPrécis 5.7.2: affine dimension in terms of rank383B Simple matricesAuxiliary V -matrix Table B.4.4526D Matrix calculusTable D.2.1, algebraic gradients and derivatives565Table D.2.2, trace Kronecker gradients566Table D.2.3, trace gradients and derivatives567Table D.2.4, logarithmic determinant gradients, derivatives569Table D.2.5, determinant gradients and derivatives570Table D.2.6, logarithmic derivatives570Table D.2.7, exponential gradients and derivatives571Dattorro, Convex Optimization Euclidean Distance Geometry 2ε, Mεβoo, v2018.09.21.12

List of Figures1 Overview1Sigma delta quantizer . . . . . . . . . . . . . . . . . .2Room geometry estimation by first acoustic reflections3Orion nebula . . . . . . . . . . . . . . . . . . . . . . .4Application of trilateration is localization . . . . . . .5Molecular conformation . . . . . . . . . . . . . . . . .6Facial recognition . . . . . . . . . . . . . . . . . . . . .7Swiss roll . . . . . . . . . . . . . . . . . . . . . . . . .8USA map reconstruction . . . . . . . . . . . . . . . . .9Honeycomb, Hexabenzocoronene molecule . . . . . . .10 Robotic vehicles . . . . . . . . . . . . . . . . . . . . .11 Reconstruction of David . . . . . . . . . . . . . . . . .12 David by distance geometry . . . . . . . . . . . . . . .192020212223242526272829292 Convex geometry13 Slab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 Open, closed, convex sets . . . . . . . . . . . . . . . . . . . . . .15 Intersection of line with boundary . . . . . . . . . . . . . . . . .16 Tangentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 Inverse image . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 Inverse image under linear map . . . . . . . . . . . . . . . . . . .19 Tesseract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 Linear injective mapping of Euclidean body . . . . . . . . . . . .21 Linear noninjective mapping of Euclidean body . . . . . . . . . .22 Convex hull of a random list of points . . . . . . . . . . . . . . .23 Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24 Two Fantopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 Nuclear Norm Ball . . . . . . . . . . . . . . . . . . . . . . . . . .26 Convex hull of rank-1 matrices . . . . . . . . . . . . . . . . . . .27 A simplicial cone . . . . . . . . . . . . . . . . . . . . . . . . . . .28 Hyperplane illustrated H is a partially bounding line . . . . . .29 Hyperplanes in R2 . . . . . . . . . . . . . . . . . . . . . . . . . .30 Affine independence . . . . . . . . . . . . . . . . . . . . . . . . .31 {z C aTz κi } . . . . . . . . . . . . . . . . . . . . . . . . . . .32 Hyperplane supporting closed set . . . . . . . . . . . . . . . . . .33 Minimizing hyperplane over affine subset in nonnegative orthant34 Maximizing hyperplane over convex set . . . . . . . . . . . . . .35 Closed convex set illustrating exposed and extreme points . . . 3.

14LIST OF 75859606162636465666768697071Two-dimensional nonconvex cone . . . . . . . . . . .Nonconvex cone made from lines . . . . . . . . . . .Nonconvex cone is convex cone boundary . . . . . .Union of convex cones is nonconvex cone . . . . . . .Truncated nonconvex cone X . . . . . . . . . . . . .Cone exterior is convex cone . . . . . . . . . . . . . .Not a cone . . . . . . . . . . . . . . . . . . . . . . . .Minimum element, Minimal element . . . . . . . . .K is a pointed polyhedral cone not full-dimensional .Exposed and extreme directions . . . . . . . . . . . .Positive semidefinite cone . . . . . . . . . . . . . . .Convex Schur-form set . . . . . . . . . . . . . . . . .Projection of truncated PSD cone . . . . . . . . . . .Circular cone showing axis of revolution . . . . . . .Circular section . . . . . . . . . . . . . . . . . . . . .Polyhedral inscription . . . . . . . . . . . . . . . . .Conically (in)dependent vectors . . . . . . . . . . . .Pointed six-faceted polyhedral cone and its dual . . .Minimal set of generators for halfspace about originVenn diagram for cones and polyhedra . . . . . . . .Range form polyhedron . . . . . . . . . . . . . . . .Simplex . . . . . . . . . . . . . . . . . . . . . . . . .Two views of a simplicial cone and its dual . . . . .Two equivalent constructions of dual cone . . . . . .Dual polyhedral cone construction by right angle . .Orthogonal cones . . . . . . . . . . . . . . . . . . . .Blades K and K . . . . . . . . . . . . . . . . . . . .K is a halfspace about the origin . . . . . . . . . . .Iconic primal and dual objective functions . . . . . .Membership w.r.t K and orthant . . . . . . . . . . .Shrouded polyhedral cone . . . . . . . . . . . . . . .Simplicial cone K in R2 and its dual . . . . . . . . .Monotone nonnegative cone KM and its dual . . .Monotone cone KM and its dual . . . . . . . . . . .Two views of monotone cone KM and its dual . . . .First-order optimality condition . . . . . . . . . . . 81201211231241261271281291371421461541551561593 Geometry of convex functions16972 Convex functions having unique minimizer . . . . . . . . . . . . . . . . . . . 17073 Minimum/Minimal element, dual cone characterization . . . . . . . . . . . . 17274 Norm balls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17375 1-norm ball B1 from compressed sensing/compressive sampling . . . . . . . 17676 Cardinality minimization, phase transition, signed versus unsigned variable 17777 1-norm variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17778 Affine function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18479 Supremum of affine functions . . . . . . . . . . . . . . . . . . . . . . . . . . 18580 Epigraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18681 Log function constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19282 Quadratic bowl and 1-norm gradients in R2 evaluated on grid . . . . . . . . 19383 Quadratic function convexity in terms of its gradient . . . . . . . . . . . . . 19984 Contour plot of convex real function at selected levels . . . . . . . . . . . . 200

LIST OF FIGURES85868788899091929315Tangent hyperplane to nonconvex surface . . . . . . . . . . . . . . . . . . .Taxicab distance on nonuniform rectangular grid . . . . . . . . . . . . . . .Iconic quasiconvex function . . . . . . . . . . . . . . . . . . . . . . . . . . .Quasiconcave monotonic function xu . . . . . . . . . . . . . . . . . . . . . .Operational Amplifier implementation of third-order filter having a zero . .Mason flowgraph for operational amplifier arbitrary m

List of Tables 2 Convex geometry Table 2.9.2.3.1, rank versus dimension of S3 + faces 97 Table 2.10.0.0.1, maximum number of c.i. directions 111 Cone Table 1 151