Constrained Optimization and the KKT Conditions
Optimization is ubiquitous in the realms of computer science, physics, mathematics, and economics. It stands as an essential tool for AI and machine learning (ML) professionals, applicable in diverse domains including decision-making, route planning, and learning parameters in ML models, such as Support Vector Machines (SVM) and neural networks. The most general form of optimization is finding a minimum/maximum of a function with respect to its independent variables, which can be achieved by applying basic concepts of differential calculus. Mathematically, at these extremities, the slope (first derivative) of a function is zero, referred to as stationary points. Determining whether such a point represents a maxima or a minima is done by evaluating the curvature (second derivative).
Taking this a step further, we can add constraints to the optimization problem that define a specific domain in space where the function is to be optimized. Consequently, instead of determining the maximum and minimum of a function in all of real (or complex) space, the optimization is now confined to this specific domain. The conventional approach of calculating stationary points is no longer a solution, as these points may fall outside the boundary set by the constraints. In the coming sections, we will analyze the intricacies of Constrained Optimization problems and explore strategies for their resolution.
Equality Constraints
Optimization problems with equality constraints are of the form
where f(x) is the function that we seek to minimize, and the constraint g(x) = 0 defines the domain within which the minimization is to be carried out. In these instances, the focus of minimization is inherently confined to the specific domain defined by the constraint. Nonetheless, as previously noted, the conventional application of differential calculus to determine stationary points does not account for the constraint, necessitating an alternative approach.
Lagrangian function
Given that this is a minimization problem, one approach to adapt to the conventional method is to assign a value of infinity to the function outside the specified domain. To achieve this, we introduce a new function f'(x) characterized by the following expression:
Such modification eliminates the possibility of minima occurring outside the domain, thereby ensuring that the optimal point occurs within it. Consequently, we can now reformulate the constrained optimization into an unconstrained optimization problem.
However, there is a challenge that comes with this approach. Using differential calculus to optimize the above problem is not possible, since the function f'(x) is not differentiable due to a sudden discontinuity at the at the boundary of the domain. Here is where Lagrangian comes into play. Rather than defining the function f'(x) as in (2), we formulate it as a maximization problem.
The expression on the RHS is called the Lagrangian function and the new variable
