Mathematical background and formulation of numerical minimization process are described in terms of gradient-based methods, whose ingredients include gradient, Hessian, directional derivatives, optimality conditions for minimization, Hessian eigensystem, conjugate number of Hessian, and conjugate vectors. Various minimization algorithms, such as the steepest descent method, Newton’s method, conjugate gradient method, and quasi-Newton’s method, are introduced along with practical examples.

Here, we define subgradients and subdifferentials of nonsmooth functions. These are a generalization of the concept of gradients for smooth functions, that can be used as the basis of algorithms. We relate subgradients to directional derivatives and to the normal cones associated with convex sets. We introduce composite nonsmooth functions that arise in regularized optimization formulations of data analysis problems and describe optimality conditions for minimizers of these functions. Finally, we describe proximal operators and the Moreau envelope, objects associated with nonsmooth functions that are the basis of algorithms for nonsmooth optimization described in the next chapter.