Optimization for Learning and Control

Anders Hansson, PhD, is a Professor in the Department of Electrical Engineering at Linköping University, Sweden. His research interests include the fields of optimal control, stochastic control, linear systems, signal processing, applications of control, and telecommunications. Martin Andersen, PhD, is an Associate Professor in the Department of Applied Mathematics and Computer Science at the Technical University of Denmark. His research interests include optimization, numerical methods, signal and image processing, and systems and control.

• Preface xviiAcknowledgments xixGlossary xxiAcronyms xxvAbout the Companion Website xxviiPart I Introductory Part 11 Introduction 31.1 Optimization 31.2 Unsupervised Learning 31.3 Supervised Learning 41.4 System Identification 41.5 Control 51.6 Reinforcement Learning 51.7 Outline 52 Linear Algebra 72.1 Vectors and Matrices 72.2 Linear Maps and Subspaces 102.3 Norms 132.4 Algorithm Complexity 152.5 Matrices with Structure 162.6 Quadratic Forms and Definiteness 212.7 Spectral Decomposition 222.8 Singular Value Decomposition 232.9 Moore-Penrose Pseudoinverse 242.10 Systems of Linear Equations 252.11 Factorization Methods 262.12 Saddle-Point Systems 322.13 Vector and Matrix Calculus 333 Probability Theory 403.1 Probability Spaces 403.2 Conditional Probability 423.3 Independence 443.4 Random Variables 443.5 Conditional Distributions 473.6 Expectations 483.7 Conditional Expectations 503.8 Convergence of Random Variables 513.9 Random Processes 513.10 Markov Processes 533.11 Hidden Markov Models 533.12 Gaussian Processes 56Part II Optimization 614 Optimization Theory 634.1 Basic Concepts and Terminology 634.2 Convex Sets 664.3 Convex Functions 724.4 Subdifferentiability 804.5 Convex Optimization Problems 844.6 Duality 864.7 Optimality Conditions 905 Optimization Problems 945.1 Least-Squares Problems 945.2 Quadratic Programs 965.3 Conic Optimization 975.4 Rank Optimization 1035.5 Partially Separability 1065.6 Multiparametric Optimization 1095.7 Stochastic Optimization 1116 Optimization Methods 1186.1 Basic Principles 1186.2 Gradient Descent 1246.3 Newton’s Method 1286.4 Variable Metric Methods 1346.5 Proximal Gradient Method 1376.6 Sequential Convex Optimization 1416.7 Methods for Nonlinear Least-Squares 1426.8 Stochastic Optimization Methods 1446.9 Coordinate Descent Methods 1536.10 Interior-Point Methods 1556.11 Augmented Lagrangian Methods 161Part III Optimal Control 1737 Calculus of Variations 1757.1 Extremum of Functionals 1757.2 The Pontryagin Maximum Principle 1797.3 The Euler-Lagrange Equations 1837.4 Extensions 1857.5 Numerical Solutions 1888 Dynamic Programming 2068.1 Finite Horizon Optimal Control 2068.2 Parametric Approximations 2118.3 Infinite Horizon Optimal Control 2138.4 Value Iterations 2158.5 Policy Iterations 2168.6 Linear Programming Formulation 2208.7 Model Predictive Control 2218.8 Explicit MPC 2258.9 Markov Decision Processes 2268.10 Appendix 233Part IV Learning 2439 Unsupervised Learning 2459.1 Chebyshev Bounds 2459.2 Entropy 2469.3 Prediction 2549.4 The Viterbi Algorithm 2599.5 Kalman Filter on Innovation Form 2619.6 Viterbi Decoder 2649.7 Graphical Models 2669.8 Maximum Likelihood Estimation 2699.9 Relative Entropy and Cross Entropy 2719.10 The Expectation Maximization Algorithm 2739.11 Mixture Models 2749.12 Gibbs Sampling 2779.13 Boltzmann Machine 2789.14 Principal Component Analysis 2809.15 Mutual Information 2839.16 Cluster Analysis 28810 Supervised Learning 29710.1 Linear Regression 29710.2 Regression in Hilbert Spaces 30010.3 Gaussian Processes 30210.4 Classification 30410.5 Support Vector Machines 30610.6 Restricted Boltzmann Machine 31010.7 Artificial Neural Networks 31210.8 Implicit Regularization 31611 Reinforcement Learning 32711.1 Finite Horizon Value Iteration 32711.2 Infinite Horizon Value Iteration 33011.3 Policy Iteration 33211.4 Linear Programming Formulation 33711.5 Approximation in Policy Space 33811.6 Appendix - Root-Finding Algorithms 34212 System Identification 35012.1 Dynamical System Models 35012.2 Regression Problem 35112.3 Input-Output Models 35212.4 Missing Data 35512.5 Nuclear Norm system Identification 35712.6 Gaussian Processes for Identification 35812.7 Recurrent Neural Networks 36012.8 Temporal Convolutional Networks 36012.9 Experiment Design 361Appendix A 373A.1 Notation and Basic Definitions 373A.2 Software 374References 379Index 387