Optimization for Learning and Control

5Optimization Problems

Applications in learning and control give rise to a wide range of optimization problems, and we will now discuss different classes of such optimization problems. Our starting point will be the classes of linear and nonlinear least‐squares problems, instances of which occur frequently in, e.g. supervised learning. It was studied already by Carl Friedrich Gauss in the eighteenth century in order to calculate the orbits of celestial bodies. We then discuss quadratic programs, which are often encountered as local surrogate models of general optimization problems and are a component of many optimization methods. Another important class of problems is the class of conic optimization problems, and we will see that any convex optimization problem can, in principle, be cast as a conic optimization problem.

Problems that involve the rank of some matrix variable as part of the objective function or a constraint function are called rank optimization problems. We will see that some special cases of these can be solved to global optimality using techniques from linear algebra. However, in general, rank optimization problems are difficult nonlinear optimization problems, and we will introduce some heuristics that often produce good approximate solutions. We will also discuss partially separable optimization problems, which are problems with a special kind of structure that can be exploited computationally. Several examples of such problems appear later in the book, ...