Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01vt150n65n
Title: Algebraic Methods in Convex Geometry, Nonlinear Optimization, and Learning Dynamical Systems
Authors: Chaudhry, Abraar
Advisors: Ahmadi, Amir Ali
Rebrova, Elizaveta
Contributors: Operations Research and Financial Engineering Department
Keywords: Algbraic Geometry
Control
Convex Geometry
Data Science
Dynamical Systems
Optimization
Subjects: Operations research
Mathematics
Applied mathematics
Issue Date: 2024
Publisher: Princeton, NJ : Princeton University
Abstract: In this thesis, we bring to bear tools from optimization over convex cones with an algebraic structure to address problems in convex geometry, nonlinear optimization, and safe learning. First, we introduce a family of symmetric convex bodies called generalized ellipsoids.These sets are defined by polynomial matrices, with degree-zero matrices corresponding to ellipsoids. As the degree increases, these sets become more complex, but they nevertheless retain desirable properties of ellipsoids. We show that several problems involving these sets can be solved via semidefinite programming. We show that these sets include all finite intersection of co-centered ellipsoids and all symmetric polytopes. From this, it follows that all symmetric convex sets can be approximated arbitrarily well by generalized ellipsoids. We present several applications. Second, we present generalizations of Newton's method that incorporate derivatives of an arbitrary order but maintain a polynomial dependence on dimension in their cost per iteration. This answers in the affirmative an open question of Nesterov et al. Our method uses semidefinite programming to construct and minimize a convex approximation to the Taylor expansion of the function we wish to minimize. We prove that our method has local convergence of order equal to the degree of Taylor expansions used. This results in faster convergence compared to the classical Newton method. We show with examples that our method may have a larger basin of attraction. We present a modified algorithm which converges globally under additional assumptions. In another chapter, We study how to find a nonnegative matrix factorization from compressed measurements.The classical nonnegative matrix factorization problem involves the constrained minimization of a nonconvex quartic polynomial. We produce alternative objective functions which also take the form of quartic polynomials, but which can be evaluated without the need to store the original full problem input in memory. We show that optimizers to our alternative problems are approximately also optimal to the original problem. We also derive iterative updates which can be used to minimize our proposed objectives. We validate our methods on real and synthetic examples. In another chapter, we tackle the problem of learning an unknown dynamical system by making measurements while maintaining safety. We formulate a mathematical definition of safe learning in terms of sequentially deciding where to initialize the next trajectory. The structure and difficulty of this problem highly dependent on the length of the trajectory whose safety we must ensure. We deal with the three cases where the trajectory has length one, two, or if the trajectory may be infinite. We place some focus on the case of autonomous linear dynamics, but we also give extensions to nonlinear systems and controlled systems. In the last chapter, we focus on two types of matrices (Schur and Hurwitz) which are both sometimes called stable matrices due to their connection to the asymptotic stability of associated linear dynamical systems.We show that it is strongly NP-hard to check if there is a stable matrix in a given general affine subspace. Conversely, we show that one can check via semidefinite programming if there is a stable matrix in an affine subspace which corresponds to noiseless trajectory measurements from an associated linear dynamical system. We also show that the corresponding problem for noisy measurements in NP-hard.
URI: http://arks.princeton.edu/ark:/88435/dsp01vt150n65n
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Chaudhry_princeton_0181D_15242.pdf3.43 MBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.