Continuous Optimization: Theory, Algorithms, and Duality

Optimization represents the pinnacle of applied mathematical analysis, providing the framework for decision-making in economics, engineering, and artificial intelligence. This lesson provides a rigorous treatment of extrema in ${\mathbb{R}}^n$, moving from unconstrained local analysis to constrained global optimization.

1. Extremum Problems in ${\mathbb{R}}^n$

Let $f:D\subseteq {\mathbb{R}}^n\to \mathbb{R}$ be a scalar field. We are interested in finding $x^{\ast }\in D$ such that $f(x^{\ast })$ is as small (or large) as possible.

Definition 1.1 (Local Extremum). A point $x^{\ast }\in D$ is a local minimum of $f$ if there exists an open neighborhood $U$ of $x^{\ast }$ such that $f(x^{\ast })\le f(x)$ for all $x\in U\cap D$. If the inequality is strict for $x\ne x^{\ast }$, it is a strict local minimum.

Definition 1.2 (Global Extremum). $x^{\ast }$ is a global minimum if $f(x^{\ast })\le f(x)$ for all $x\in D$.

The Extreme Value Theorem guarantees the existence of global extrema if $f$ is continuous and $D$ is compact (closed and bounded in ${\mathbb{R}}^n$). In non-compact domains, we must analyze the behavior of $f$ as $\Vert x\Vert \to \infty$.

2. First-Order Necessary Conditions (FONC)

For a function $f$ to have a local extremum at an interior point $x^{\ast }$, it must be “flat” in all directions.

Theorem 2.1 (Vanishing Gradient). If $f$ is differentiable at $x^{\ast }\in \text{int}(D)$ and $x^{\ast }\in \text{int}(D)$ is a local extremum, then: $\nabla f(x^{\ast })=0,$ where $\nabla f={\left[\frac{\partial f}{\partial x_1},\dots ,\frac{\partial f}{\partial x_n}\right]}^{\top }$.

Proof Sketch: Consider the one-dimensional functions $g_i(t)=f(x^{\ast }+t{e}_i)$, where $e_i$ is the $i$-th standard basis vector. Since $x^{\ast }$ is a local extremum of $f$, $t=0$ must be a local extremum of each $g_i(t)$. By single-variable calculus, $g_i^{\prime }(0)=0$. Since $g_i^{\prime }(0)=\frac{\partial f}{\partial x_i}(x^{\ast })$, all partial derivatives must vanish.

Points where $\nabla f(x^{\ast })=0$ are called stationary or critical points. Note that this condition is necessary but not sufficient (e.g., $f(x,y)=x^2-y^2$ at $(0,0)$).

3. Second-Order Conditions and Stability

To determine if a critical point is a minimum, maximum, or saddle point, we analyze the curvature using the Hessian matrix $\mathbf{H}(x)\in {\mathbb{R}}^{n\times n}$.

Definition 3.1 (The Hessian).

Theorem 3.2 (Second-Order Sufficiency). Let $\nabla f(x^{\ast })=0$ for a $C^2$ function $f$.

1. If $\mathbf{H}(x^{\ast })$ is positive definite ($v^{\top }Hv>0,\forall v\ne 0$), $x^{\ast }$ is a strict local minimum.
2. If $\mathbf{H}(x^{\ast })$ is negative definite ($v^{\top }Hv<0,\forall v\ne 0$), $x^{\ast }$ is a strict local maximum.
3. If $\mathbf{H}(x^{\ast })$ is indefinite (has both positive and negative eigenvalues), $x^{\ast }$ is a saddle point.

4. Convexity: The Bridge to Global Optimality

Convexity is arguably more important than differentiability in modern optimization.

Definition 4.1 (Convex Set). A set $C\subseteq {\mathbb{R}}^n$ is convex if for any $x,y\in C$, the line segment $\{\theta x+(1-\theta )y:\theta \in [0,1]\}$ is contained in $C$.

Definition 4.2 (Convex Function). $f:C\to \mathbb{R}$ is convex if $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$ for all $x,y\in C,\theta \in [0,1]$.

Fundamental Property: If $f$ is a convex function on a convex set $C$, then any local minimum is a global minimum. This property makes convex optimization problems (like Least Squares or Support Vector Machines) computationally tractable and allows for efficient numerical solvers.

5. Equality Constrained Optimization: Lagrange Multipliers

Consider the problem: ${\min }_{x\in {\mathbb{R}}^n}f(x)\text{subject to }{g}_i(x)=0,i=1,\dots ,m.$

Theorem 5.1 (Lagrange’s Theorem). Let $x^{\ast }$ be a local extremum and a regular point of the constraints (meaning $\{\nabla g_i(x^{\ast }){\}}_{i=1}^m$ are linearly independent). Then there exists a vector ${\lambda }^{\ast }\in {\mathbb{R}}^m$ of Lagrange Multipliers such that: $\nabla f(x^{\ast })+{\sum }_{i=1}^m{\lambda }_i^{\ast }\nabla g_i(x^{\ast })=0.$

We define the Lagrangian function: $\mathcal{L}(x,\lambda )=f(x)+{\sum }_{i=1}^m{\lambda }_i{g}_i(x).$ The necessary conditions for optimality are given by the system $\nabla \mathcal{L}(x,\lambda )=0$.

Geometric Intuition: At the optimum, the gradient of the objective $\nabla f$ must be orthogonal to the tangent space of the constraint manifold. Since the gradients of the constraints $\nabla g_i$ span the normal space at $x^{\ast }$, $\nabla f$ must be expressible as a linear combination of these normal vectors.

6. Inequality Constraints and KKT Conditions

When constraints include inequalities ($h_j(x)\le 0$), we extend Lagrange’s method to the Karush-Kuhn-Tucker (KKT) conditions.

For $x^{\ast }$ to be a local minimum, under a constraint qualification, there must exist ${\lambda }^{\ast }$ and ${\mu }^{\ast }$ such that:

1. Stationarity: $\nabla f(x^{\ast })+\sum {\lambda }_i^{\ast }\nabla g_i(x^{\ast })+\sum {\mu }_j^{\ast }\nabla h_j(x^{\ast })=0$
2. Primal Feasibility: $g_i(x^{\ast })=0,h_j(x^{\ast })\le 0$
3. Dual Feasibility: ${\mu }_j^{\ast }\ge 0$
4. Complementary Slackness: ${\mu }_j^{\ast }{h}_j(x^{\ast })=0$

Complementary slackness is the most critical KKT condition: it implies that if a constraint is “slack” ($h_j(x^{\ast })<0$), its multiplier must be zero (${\mu }_j=0$). If ${\mu }_j>0$, the constraint must be “active” ($h_j(x^{\ast })=0$).

7. Sensitivity and Shadow Prices

The multipliers provide a measure of the sensitivity of the optimal value to perturbations in the constraints. Suppose we relax a constraint to $g_i(x)=ϵ$. Let $V(ϵ)$ be the optimal objective value.

Theorem 7.1. Under regularity: $\frac{\partial V}{\partial {ϵ}_i}=-{\lambda }_i$ In economics, ${\lambda }_i$ is interpreted as the shadow price. It represents the marginal change in the objective function if the $i$-th constraint is relaxed by one unit. This is vital for resource allocation problems where one must decide whether the cost of increasing a resource is justified by the resulting improvement in the objective.

8. Computational Example: Constrained Optimization in Python

The following code uses scipy.optimize to solve a quadratic objective with a non-linear inequality constraint.

import numpy as np
from scipy.optimize import minimize

# Objective: Minimize f(x, y) = x^2 + y^2
def objective(x):
    return x[0]**2 + x[1]**2

# Constraint: x + y >= 1  => x + y - 1 >= 0
def constraint1(x):
    return x[0] + x[1] - 1

# Initial guess
x0 = [2, 2]

# Define the constraint dictionary
con1 = {'type': 'ineq', 'fun': constraint1}
cons = [con1]

# Perform optimization
sol = minimize(objective, x0, method='SLSQP', constraints=cons)

print(f"Optimal solution: x = {sol.x[0]:.4f}, y = {sol.x[1]:.4f}")
print(f"Minimum value: f(x,y) = {sol.fun:.4f}")

9. Advanced Quiz