5. Constrained optimization#
Previous chapters have focused on unconstrained problems, where the domain of each variable is the space of real numbers. However, many optimization problems also come with some auxiliary “restrictions” that the optimal solution must satisfy. Such restrictions are called constraints and define a subset of feasible points among which the optimal solution must be found. This leads to the mathematical problem of finding a minimum of the function \(J({\bf w})\) on the feasible set \(\mathcal{C}\subset \mathbb{R}^N\), formally denoted as
The above statement calls for finding a point of \(\mathcal{C}\) that yields the smallest value of the function \(J({\bf w})\). This is referred to as constrained optimization.
Contents: This chapter presents the projected gradient method, one of the simplest yet efficient algorithms for finding the minimum of a differentiable function subject to constraints. As the name suggests, this approach solves constrained optimization problems by relying both on the gradient of the cost function and the orthogonal projection onto the feasible set.
You will learn the constrained optimality conditions.
You will understand the notion of orthogonal projection onto a closed subset.
You will study the projected gradient method, along with the assumptions required for its convergence.
You will see what types of constraints can be dealt with projected gradient descent.
Acknowledgement: Part of this chapter is based on the lecture notes entitled “Fragments d’optimisation différentiable” by Jean Charles Gilbert.