Many of the preceding chapters involved optimization formulations: linear least squares, Procrustes, low-rank approximation, multidimensional scaling. All these have analytical solutions, like the pseudoinverse for minimum-norm least squares problems and the truncated singular value decomposition for low-rank approximation. But often we need iterative optimization algorithms, for example if no closed-form minimizer exists, or if the analytical solution requires too much computation and/or memory (e.g., singular value decomposition for large problems. To solve an optimization problem via an iterative method, we start with some initial guess and then the algorithm produces a sequence that hopefully converges to a minimizer. This chapter describes the basics of gradient-based iterative optimization algorithms, including preconditioned gradient descent (PGD) for the linear LS problem. PGD uses a fixed step size, whereas preconditioned steepest descent uses a line search to determine the step size. The chapter then considers gradient descent and accelerated versions for general smooth convex functions. It applies gradient descent to the machine learning application of binary classification via logistic regression. Finally, it summarizes stochastic gradient descent.

This chapter serves two purposes: it introduces several essential concepts of linear and nonlinear functional analysis that will be used in subsequent chapters and, as an illustration of them, studies the problem of unconstrained minimization of a convex functional. All the necessary notions of existence, uniqueness, and optimality conditions are presented and analyzed. Preconditioned gradient descent methods for strongly convex, locally Lipschitz smooth objectives in infinite dimensions are then presented and analyzed. A general framework to show linear convergence in this setting is then presented. The preconditioned steepest descent with exact and approximate line searches are then analyzed using the same framework. Finally, the application of Newton’s method to the Euler equations is discussed. The local convergence is shown, and how to achieve global convergence is briefly discussed.