Memory-efficient optimization over positive semidefinite matrices
Abstract/Contents
- Abstract
- We present an extension of the conditional gradient method to problems whose feasible sets are convex cones which we call conic descent. We provide a convergence analysis for the method and for variants with non-convex objectives, and we extend the analysis to practical cases with effective line search strategies. For the specific case of the positive semidefinite cone, we present a memory-efficient version based on randomized matrix sketches and advocate a heuristic greedy step that greatly improves its practical performance. Numerical results on phase retrieval problems indicate that our method delivers results of a specified accuracy in approximately half as many iterations as required by the conditional gradient method. Building off this foundation, we next use the augmented Lagrangian technique to enable the incorporation of equality constraints. This immediately leads to applying the memory-efficient version of conic descent over the positive semidefinite cone to the solution of large scale semidefinite programs. Numerical results on solving graph maximum cut problems demonstrate its usefulness and advantages over traditional Burer-Monteiro approaches. In a sensor network localization (SNL) problem, we attempt to determine the two- or three-dimensional layout of a network of sensors from some of their pairwise distances. We present an efficient projected gradient method to approximately solve the SNL problem if a good initial guess of the sensor locations is available. When the sensors are not static, our method is an efficient way to update the estimate of their positions and so provides a way of tracking the sensors as they move. Along the way, we present an analysis of the projected gradient method for arbitrary feasible sets onto which we can project exactly, which is of independent interest. Numerical results demonstrate the practical efficacy and robustness of our method
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2020; ©2020 |
| Publication date | 2020; 2020 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Naber, Andrew Thomas |
|---|---|
| Degree supervisor | Duchi, John |
| Thesis advisor | Duchi, John |
| Thesis advisor | Lall, Sanjay |
| Thesis advisor | Ye, Yinyu |
| Degree committee member | Lall, Sanjay |
| Degree committee member | Ye, Yinyu |
| Associated with | Stanford University, Department of Electrical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Andrew Thomas Naber |
|---|---|
| Note | Submitted to the Department of Electrical Engineering |
| Thesis | Thesis Ph.D. Stanford University 2020 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2020 by Andrew Thomas Naber
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...