Title: Tractable approximations and algorithmic aspects of optimization under uncertainty

Date: April 26th, 2022

Time: 2:00 pm – 4:00 pm

Location: https://bluejeans.com/881337911/9280  (BlueJeans meeting link) 

Meeting ID: 881337911

Student NameL Georgios Kotsalis

Operations Research PhD Student

H. Milton Stewart School of Industrial and Systems Engineering

Georgia Institute of Technology

Advisor: 

Dr. Guanghui Lan (Advisor), School of Industrial and Systems Engineering, Georgia Tech

Dr. Arkadi Nemirovski (Co-advisor), School of Industrial and Systems Engineering, Georgia Tech

Thesis Committee:

Dr. Grigoriy Blekherman, School of Mathematics, Georgia Tech

Dr. David Goldsman, School of Industrial and Systems Engineering, Georgia Tech

Dr. Anatoli Juditsky, Laboratoire Jean Kuntzmann, Universite´ Grenoble Alpes

Dr. Alexander Shapiro, School of Industrial and Systems Engineering, Georgia Tech

Abstract

This thesis has two themes. In chapters 1 and 2 we investigate tractable approximations to specific classes of computationally hard problems as they relate to the areas 

of signal estimation, system identification and control. In chapters 3 and 4 we focus on the algorithmic development for the solution of variational inequalities and stochastic versions thereof, a topic of interest in many areas including reinforcement learning.

Chapter 1 addresses the finite-horizon robust covariance control problem for discrete-time, partially observable, linear systems affected by random zero mean noise and 

deterministic, uncertain-but-bounded disturbances restricted to lie in what is called ellitopic uncertainty set (e.g., finite intersection of centered at the origin ellipsoids/elliptic cylinders). Performance specifications are imposed on the random state-control trajectory via averaged convex quadratic inequalities, linear inequalities on the mean, chance constrained linear inequalities as well as convex monotone constraints on the covariance matrix. For this problem we develop a computationally tractable procedure for designing affine control policies, in the sense that the parameters of the policy that guarantees the performance specifications are obtained as the solutions to an explicit convex program.

In chapter 2 we address the problems of computing operator norms of matrices induced by given norms on the argument and the image space. It is known that aside of a fistful of ``solvable cases,'' most notably, the case when both given norms are Euclidean, computing operator norm of a matrix is NP-hard. We specify rather general families of norms on the argument and the images space (``ellitopic'' and ``co-ellitopic,'' respectively) allowing for reasonably tight computationally efficient upper bounds of the associated operator norms. We extend these results to bounding ``robust operator norm of uncertain matrix with box uncertainty,'' that is, the maximum of operator norms of matrices representable as a linear combination, with coefficients of magnitude $\leq1$, of a collection of given matrices. Finally, we consider some applications of norm bounding, in particular, (1) computationally efficient synthesis of affine non-anticipative finite-horizon control of discrete time linear dynamical systems under bounds on the peak-to-peak gains, (2) signal recovery with uncertainties in sensing matrix, and (3) identification of parameters of time invariant discrete time linear dynamical systems via noisy observations of states and inputs on a given time horizon, in the case of ``uncertain-but-bounded'' noise varying in a box.

In chapter 3 we first present a novel operator extrapolation (OE) method for solving deterministic variational inequality (VI) problems.  OE updates one single search sequence by solving a single projection subproblem in each iteration. We show that OE can achieve the optimal rate of convergence for solving a variety of VI problems in a much simpler way than existing approaches. We then introduce the stochastic operator extrapolation (SOE) method and establish its optimal convergence behavior for solving different stochastic VI problems. SOE achieves the optimal complexity for solving a fundamental problem, i.e., stochastic smooth and strongly monotone VI, for the first time in the literature. We also present a stochastic block operator extrapolations (SBOE) method to further reduce the iteration cost for the OE method applied to large-scale deterministic VIs with a certain block structure. Numerical experiments have been conducted to demonstrate the potential advantages of the proposed algorithms. In fact, all these algorithms are applied to solve generalized monotone variational inequality (GMVI) problems whose operator is not necessarily monotone.

In chapter 4 the focus is on stochastic variational inequalities (VI) under Markovian noise. A prominent application of our algorithmic developments is the stochastic policy evaluation problem in reinforcement learning. Prior investigations in the literature focused on temporal difference (TD) learning by employing non-smooth finite time analysis motivated by stochastic sub-gradient descent leading to certain limitations.  These limitations encompass the requirement of analyzing a modified TD algorithm that involves projection to an a-priori defined Euclidean ball, achieving a non-optimal convergence rate and no clear way of deriving the beneficial effects of parallel implementation. Our approach remedies these shortcomings in the broader context of stochastic VIs and in the specific case of stochastic policy evaluation. We developed a variety of simple TD learning type algorithms motivated by its original version that maintain its simplicity, while offering distinct advantages from a non-asymptotic analysis point of view. We first provide an improved analysis of the standard TD algorithm that can benefit from parallel implementation. Then we present versions of a conditional TD algorithm (CTD), that involves periodic updates of the stochastic iterates, which reduce the bias and therefore exhibit improved iteration complexity. This brings us to the fast TD (FTD) algorithm which combines elements of CTD and the stochastic operator extrapolation method of chapter 3. For a novel index resetting step-size policy FTD exhibits the best, to our knowledge, convergence rate. We also devised a robust version of the algorithm that is particularly suitable for discounting factors close to 1.