Constrained Optimization Fundamentals

While much of machine learning optimization focuses on minimizing a loss function without explicit restrictions on the parameters, many practical scenarios involve constraints. These are conditions that the solution must satisfy. Ignoring constraints can lead to solutions that are impractical, invalid, or fail to meet specific requirements of the problem.

This section introduces the fundamental concepts of constrained optimization, setting the stage for the techniques discussed later in this chapter.

Why Constraints?

Constraints arise naturally in various machine learning contexts:

Resource Limitations: Allocating a fixed budget across different features or models. Assigning tasks to workers with limited capacity.
Physical or Logical Requirements: Ensuring probabilities sum to 1, keeping parameters within physically meaningful bounds (e.g., positive variances), or enforcing specific relationships between variables.
Fairness and Bias Mitigation: Imposing constraints on model predictions to ensure parity across different demographic groups.
Interpretability and Sparsity: While often handled via L1 regularization, sparsity can be framed as a constraint on the number of non-zero parameters (though this specific constraint is non-convex and computationally hard). Relatedly, LASSO regression minimizes squared error subject to an L1-norm constraint on the weights.
Safety Guarantees: In reinforcement learning or control systems, ensuring actions stay within safe operating limits.

Mathematical Formulation

A general constrained optimization problem can be written in the following standard form:

\begin{aligned} \min_{x \in \mathbb{R}^n} & \quad f(x) \\ \text{subject to} & \quad g_i(x) \le 0, \quad i = 1, \dots, m \\ & \quad h_j(x) = 0, \quad j = 1, \dots, p \end{aligned}

Let's break down the components:

$x \in \mathbb{R}^n$ : This is the vector of decision variables we want to optimize. In machine learning, $x$ typically represents the model parameters (weights, biases).
$f(x): \mathbb{R}^n \to \mathbb{R}$ : This is the objective function that we aim to minimize. Usually, this is the loss function (e.g., mean squared error, cross-entropy).
$g_i(x) \le 0$ : These are the $m$ inequality constraints. Each $g_i(x)$ is a function $g_i: \mathbb{R}^n \to \mathbb{R}$ . These constraints define conditions that must be met in terms of "less than or equal to". Note that a constraint like $a(x) \ge b$ can be rewritten as $b - a(x) \le 0$ .
$h_j(x) = 0$ : These are the $p$ equality constraints. Each $h_j(x)$ is a function $h_j: \mathbb{R}^n \to \mathbb{R}$ . These specify exact conditions that must hold.

The set of all points $x$ that satisfy all the inequality and equality constraints is called the feasible region, often denoted by $\mathcal{F}$ :

\mathcal{F} = \{ x \in \mathbb{R}^n \mid g_i(x) \le 0 \text{ for all } i=1,\dots,m, \text{ and } h_j(x) = 0 \text{ for all } j=1,\dots,p \}

The goal of constrained optimization is to find a point $x^* \in \mathcal{F}$ such that $f(x^*) \le f(x)$ for all $x \in \mathcal{F}$ .

The Feasible Region

The nature of the feasible region is critically important. If the constraint functions $g_i$ and $h_j$ are simple (e.g., linear), the feasible region might be a geometrically simple shape like a polygon or polyhedron. If they are complex and non-linear, the feasible region can have a complicated structure.

Consider minimizing $f(x_1, x_2) = (x_1 - 2)^2 + (x_2 - 2)^2$ (whose unconstrained minimum is at $(2, 2)$ ) subject to $x_1 + x_2 \le 1$ , $x_1 \ge 0$ , and $x_2 \ge 0$ . The feasible region is a triangle.

The feasible region (shaded gray) is defined by the constraints $x_1 \ge 0$ , $x_2 \ge 0$ , and $x_1 + x_2 \le 1$ . The blue contours represent the objective function $f(x_1, x_2) = (x_1 - 2)^2 + (x_2 - 2)^2$ . The unconstrained minimum is at $(2, 2)$ (red 'x'), outside the feasible region. The constrained minimum occurs at $(0.5, 0.5)$ (green star), on the boundary of the feasible region.

Challenges Introduced by Constraints

Constraints fundamentally change the optimization process:

Optimality Conditions: In unconstrained optimization, a necessary condition for a local minimum (for differentiable functions) is that the gradient is zero ( $\nabla f(x) = 0$ ). This is no longer sufficient or even necessary for constrained problems. As seen in the plot above, the constrained minimum $(0.5, 0.5)$ occurs where the gradient is clearly non-zero. The optimal point might lie on the boundary of the feasible region.
Maintaining Feasibility: Standard iterative methods like gradient descent might generate steps that take the parameters outside the feasible region. Algorithms must incorporate mechanisms to handle constraints, either by projecting iterates back onto the feasible set or by modifying the search direction.

Understanding this basic setup is essential before exploring methods designed to solve these problems, such as those based on Lagrange multipliers (covered next) or projection techniques.

Was this section helpful?

References

Convex Optimization, Stephen Boyd and Lieven Vandenberghe, 2004 (Cambridge University Press) - A standard reference for convex optimization, presenting foundational theory for constrained problems, feasible regions, and optimality conditions.
Numerical Optimization, Jorge Nocedal and Stephen J. Wright, 2006 (Springer) DOI: 10.1007/978-0-387-40065-5 - A comprehensive text on numerical optimization, addressing theory and algorithms for both unconstrained and constrained problems.
Nonlinear Programming, Dimitri P. Bertsekas, 2016 (Athena Scientific) - A detailed textbook on nonlinear programming, providing rigorous analysis of constrained optimization theory and methods. 3rd edition.
CS229 Lecture Notes: Constrained Optimization, KKT conditions, Duality, Andrew Ng and Anqi Liu, 2018 (Stanford University) - Stanford CS229 lecture notes introducing constrained optimization basics, problem formulation, and leading into KKT conditions and duality, highly pertinent to machine learning.