Relevant Degree Programs
Graduate Student Supervision
Doctoral Student Supervision (Jan 2008 - Nov 2019)
The emergence of compressed sensing and its impact on various applications in signal processing and machine learning has sparked an interest in generalizing its concepts and techniques to inverse problems that involve quadratic measurements. Important recent developments borrow ideas from matrix lifting techniques in combinatorial optimization and result in convex optimization problems characterized by solutions with very low rank, and by linear operators that are best treated with matrix-free approaches. Typical applications give rise to enormous optimization problems that challenge even the very best workhorse algorithms and numerical solvers for semidefinite programming.The work presented in this thesis focuses on the class of low-rank spectral optimization problems and its connection with a theoretical duality framework for gauge functions introduced in a seminal paper by Freund (1987). Through this connection, we formulate a related eigenvalue optimization problem more amenable to the design of specialized algorithms that scale well and can be used in practical applications.We begin by exploring the theory of gauge duality focusing on a slightly specialized structure often encountered in the motivating inverse problems. These developments are still made in a rather abstract form, thus allowing for its application to different problem classes.What follows is a connection of this framework with two important classes of spectral optimization problems commonly found in the literature: trace minimization in the cone of positive semidefinite matrices and affine nuclear norm minimization. This leads us to a convex eigenvalue optimization problem with rather simple constraints, and involving a number of variables equal to the number of measurements, thus with dimension far smaller than the primal.The last part of this thesis exploits a sense of strong duality between the primal-dual pair of gauge problems to characterize their solutions and to devise a method for retrieving a primal minimizer from a dual one. This allows us to design and implement a proof of concept solver which compares favorably against solvers designed specifically for the PhaseLift formulation of the celebrated phase recovery problem and a scenario of blind image deconvolution.
No abstract available.
Master's Student Supervision (2010 - 2018)
This thesis proposes a new active-set method for large-scale nonlinearly constrained optimization. The method solves a sequence of linear programs togenerate search directions. The typical approach for globalization is based ondamping the search directions with a trust-region constraint; our proposed approach is instead based on using a 2-norm regularization term in the objective.Numerical evidence is presented which demonstrates scaling inefficienciesin current sequential linear programming algorithms that use a trust-regionconstraint. Specifically, we show that the trust-region constraints in the trustregionsubproblems significantly reduce the warm-start efficiency of these subproblemsolves, and also unnecessarily induce infeasible subproblems. We alsoshow that the use of a regularized linear programming (RLP) step largely eliminates these inefficiencies and, additionally, that the dual problem to RLP isa bound-constrained least-squares problem, which may allow for very efficientsubproblem solves using gradient-projection-type algorithms.Two new algorithms were implemented and are presented in this thesis,based on solving sequences of RLPs and trust-region constrained LPs. Thesealgorithms are used to demonstrate the effectiveness of each type of subproblem,which we extrapolate onto the effectiveness of an RLP-based algorithm with theaddition of Newton-like steps.All of the source code needed to reproduce the figures and tables presentedin this thesis is available online athttp: //www.cs.ubc.ca/labs/scl/thesis/lOcrowe/