Optimization Problems

Intro

Optimization is an important tool in mathematics and algorithms.

Gradients and Gradient Descent

Suppose the multivariable function $f(x_1, x_2, \dots, x_n)$ is differentiable in a neighborhood of point $P$. The column vector formed by all of its first-order partial derivatives at $P$,

$$\nabla f(P) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n} \right)^\top$$

is called the gradient of $f$ at $P$.

It points in the direction of the fastest increase in the function value, and its magnitude is the maximum rate of increase per unit distance in that direction.

Where does this definition come from? We first introduce the directional derivative, the rate at which a function changes near a point: $\boxed{D_u f(x_0) = \lim_{t \to 0} \frac{f(x_0 + t u) - f(x_0)}{t} = \left. \frac{d}{dt} f(x_0 + t u) \right|_{t=0}}$.

Here, $u$ is a unit vector. The derivative represents the instantaneous change when moving in that direction.

By the multivariable chain rule (see the appendix for a derivation): [ \frac{d}{dt} f(x(t)) = \sum_{i=1}^n \frac{\partial f}{\partial x_i} \cdot \frac{d x_i}{dt} ]

Since $\frac{d x_i}{dt}=u_i$, substitution gives: [ \frac{d}{dt} f(x_0 + t u) = \sum_{i=1}^n \frac{\partial f}{\partial x_i}(x_0 + t u) \cdot u_i ]

Taking the limit at $t=0$: [ D_u f(x_0) = \left. \frac{d}{dt} f(x_0 + t u) \right|{t=0} = \sum{i=1}^n \frac{\partial f}{\partial x_i}(x_0) \cdot u_i ]

The Method of Lagrange Multipliers

1. Objective

Find a local maximum or minimum of a multivariable objective function subject to one or more equality constraints.

• Without constraints, we can set every partial derivative to zero and solve the resulting equations.
• With constraints, the variables are restricted to a curve, surface, or higher-dimensional manifold and cannot move freely.
• The method of Lagrange multipliers aims to convert a constrained extremum problem into an unconstrained one.

---

2. Conditions for Use

Category	Requirement	Explanation
Problem form	Find extrema of $f(x_1,\dots,x_n)$ subject to equality constraints $g_k(x_1,\dots,x_n)=0$ ($k=1,\dots,m$)	Applies only to equality constraints; inequality constraints require the KKT conditions
Differentiability	$f$ and every $g_k$ are continuous and have first-order partial derivatives on the domain	The method relies on gradients and cannot be applied when they do not exist
Constraint regularity (LICQ)	At the extremum, all constraint gradients $\nabla g_k$ must be linearly independent and nonzero	Ensures that the Lagrange multipliers $\lambda_k$ exist and are unique; otherwise the method may fail or produce invalid candidates
Nature of the result	The solutions are only candidate extrema (necessary conditions) and require further verification	Use second-order conditions—checking definiteness of the Hessian on the constraint tangent space—or compare objective values directly

Note: if the problem is a convex optimization problem—$f$ is convex and the equality constraints are affine—then a point satisfying these conditions is automatically globally optimal, without second-order verification.

---

3. Procedure

Standard steps for one constraint (the extension to multiple constraints is analogous)

Step 1: Construct the Lagrangian.
Introduce one or more new variables called Lagrange multipliers, denoted by $\lambda$, and construct the auxiliary function: [ \mathcal{L}(x_1,\dots,x_n,\lambda) = f(x_1,\dots,x_n) + \lambda , g(x_1,\dots,x_n) ] (Some textbooks use a minus sign. This does not change the substance; it only reverses the sign of $\lambda$.)

Step 2: Take first-order partial derivatives with respect to every variable and $\lambda$, and set them to zero.
This yields the system: [ \begin{cases} \dfrac{\partial \mathcal{L}}{\partial x_i} = \dfrac{\partial f}{\partial x_i} + \lambda \dfrac{\partial g}{\partial x_i} = 0, & i=1,\dots,n \[10pt] \dfrac{\partial \mathcal{L}}{\partial \lambda} = g(x_1,\dots,x_n) = 0 \end{cases} ]

Step 3: Solve the system.
Find every candidate point $(x_1^*,\dots,x_n^*)$ and its corresponding $\lambda^*$.

Step 4: Verify whether each candidate is an actual extremum.

• For a convex optimization problem, the candidate is globally optimal.
• Otherwise, use the second-order sufficient conditions—check whether the Hessian of the Lagrangian is positive or negative definite on the constraint tangent space—or compare numerical values directly.

---

Extension to multiple constraints

For $m$ equality constraints $g_1=0,\dots,g_m=0$, construct: [ \mathcal{L} = f + \sum_{k=1}^m \lambda_k g_k ] Set the partial derivatives with respect to every $x_i$ and $\lambda_k$ to zero. This gives $n+m$ equations for $n+m$ unknowns.

---

4. Why It Works

Geometric intuition

• Without constraints, $\nabla f=0$ at an extremum: the function can no longer increase or decrease in any direction.
• With a constraint, variables can move only along the constraint surface $g=0$. At an extremum, moving in any tangent direction along that surface cannot change $f$.
• Therefore, $\nabla f$ must be perpendicular to the constraint surface, meaning its dot product with every tangent vector is zero.
• The normal direction of the constraint surface is exactly $\nabla g$.
  Thus $\nabla f$ must be parallel to $\nabla g$, so there is a real number $\lambda$ such that: [ \nabla f + \lambda \nabla g = 0 ] This is precisely the vector form obtained by setting the derivative of the Lagrangian with respect to $x$ to zero.

Short algebraic derivation

At an extremum $x^*$, make an infinitesimal feasible perturbation $dx$ to the constraint $g(x)=0$, where $\nabla g\cdot dx=0$. Since $f$ is extremal there, $\nabla f\cdot dx=0$ as well.
Thus $\nabla f$ and $\nabla g$ are both orthogonal to the same tangent space spanned by all feasible $dx$, so they must be collinear. Introducing the proportionality coefficient $\lambda$ gives the equation above.

Additional Meaning of $\lambda$: Sensitivity

$\lambda$ also has a practical interpretation: it represents the rate at which the optimal objective value changes when the right-hand-side constant of the constraint changes slightly.
In economics, $\lambda$ is called the “shadow price” and reflects the scarcity of the constrained resource.

---

5. Summary

Dimension	Key Point
Objective	Find extrema of a multivariable function subject to equality constraints
Conditions	Equality constraints, differentiability, and linearly independent constraint gradients (LICQ); solutions are candidates
Method	Construct $\mathcal{L}=f+\sum \lambda_k g_k$, set derivatives with respect to every variable and multiplier to zero, solve, and verify
Principle	At an extremum, $\nabla f$ is parallel to the constraint gradient $\nabla g$; geometrically, both align with the surface normal