Active Set Methods: From Lagrange Multipliers to Constrained Optimization

Introduction

In control, machine learning, economics, and engineering, we constantly face optimization problems with constraints. We want to minimize a cost, but we can't just go anywhere — there are limits on what's allowed.

For example:

• MPC: Minimize control effort, but actuators have limits
• Portfolio optimization: Maximize returns, but you can't invest more than 100%
• Robot motion: Minimize energy, but joints have angle limits

The Active Set Method is one of the most elegant algorithms for solving these constrained optimization problems. But to understand it deeply, we need to first understand Lagrange multipliers — a beautiful mathematical tool that transforms constrained problems into unconstrained ones.

Let's build this understanding from the ground up.

Starting Point: Unconstrained Optimization

Before adding constraints, let's recall unconstrained optimization. Given a function $f(x)$ where $x \in \mathbb{R}^n$, we want to find:

The Gradient Condition

At a minimum, the function must be "flat" — moving in any direction doesn't immediately decrease the cost. Mathematically, the gradient must be zero:

The gradient $\nabla f = \begin{bmatrix} \frac{\partial f}{\partial x_1} & \cdots & \frac{\partial f}{\partial x_n} \end{bmatrix}^T$ points in the direction of steepest increase. At a minimum, there's no direction of increase (or decrease) — hence zero gradient.

For unconstrained problems, we just solve $\nabla f = 0$. But what happens when we add constraints?

The Problem: Constraints Change Everything

Now consider minimizing $f(x)$ subject to a constraint $g(x) = 0$:

The constraint $g(x) = 0$ defines a surface (or curve, or hyperplane) in the space. We can only move along this surface — the solution must lie on it.

Why $\nabla f = 0$ No Longer Works

The unconstrained minimum (where $\nabla f = 0$) might violate the constraint! We need a new condition.

The Key Geometric Insight

At the constrained minimum, we're on the constraint surface. If we could improve (decrease $f$) by moving along the constraint, we would — so we're not at the minimum yet.

At the true constrained minimum, the gradient $\nabla f$ must point perpendicular to the constraint. Why? Because if $\nabla f$ had any component along the constraint, we could move in that direction (staying on the constraint) and decrease $f$.

"Parallel" means one is a scalar multiple of the other:

The scalar $\lambda$ is the Lagrange multiplier. It tells us how much the gradients are "aligned."

Deriving Lagrange Multipliers Rigorously

Let's derive this more carefully. We'll see where the Lagrangian comes from and why it works.

The Lagrangian Function

Define the Lagrangian:

This combines the objective and constraint into one function with an extra variable $\lambda$.

Stationary Points of the Lagrangian

Now we find where the Lagrangian has zero gradient with respect to both $x$ and $\lambda$:

Look at what these equations say:

• First equation: $\nabla f = \lambda \nabla g$ — the gradients are parallel (our geometric condition!)
• Second equation: $g(x) = 0$ — the constraint is satisfied

By finding stationary points of $\mathcal{L}$, we automatically get both conditions!

What Does $\lambda$ Mean?

The Lagrange multiplier $\lambda$ has a beautiful interpretation: it measures the sensitivity of the optimal cost to the constraint.

If we slightly relax the constraint from $g(x) = 0$ to $g(x) = \epsilon$, how much does the optimal cost change?

So $\lambda$ tells us the "price" or "shadow cost" of the constraint:

• $\lambda > 0$: The constraint is "expensive" — relaxing it would help
• $\lambda < 0$: The constraint is helping us (unusual for minimization)
• $\lambda = 0$: The constraint doesn't matter at this point

Inequality Constraints and KKT Conditions

In practice, most constraints are inequalities: $g(x) \leq 0$ rather than $g(x) = 0$. This changes things significantly.

The Key Difference: Active vs. Inactive

An inequality constraint can be in two states:

• Active (binding): $g(x^*) = 0$ — we're right on the boundary
• Inactive: $g(x^*) < 0$ — we have "slack," the constraint doesn't affect us

If a constraint is inactive at the solution, it's as if it doesn't exist — we could remove it and get the same answer.

If a constraint is active, it becomes an equality constraint, and Lagrange multipliers apply.

The KKT Conditions

For optimization with inequality constraints, the generalization of Lagrange conditions is called the Karush-Kuhn-Tucker (KKT) conditions.

Consider: $\min_x f(x)$ subject to $g_i(x) \leq 0$ for $i = 1, \ldots, m$.

The KKT conditions are:

Understanding Complementary Slackness

Condition 4 is the crucial one. It says: for each constraint, at least one of $\lambda_i$ or $g_i$ must be zero.

• If $g_i(x^*) < 0$ (constraint inactive, we have slack), then $\lambda_i = 0$ (no "cost" to the constraint)
• If $\lambda_i > 0$ (constraint has positive cost), then $g_i(x^*) = 0$ (constraint is active/binding)

This makes intuitive sense: why would a constraint that isn't binding have any influence on the solution?

The Active Set Method

Now we have all the ingredients. The Active Set Method is an algorithm that solves inequality-constrained optimization by cleverly managing which constraints are active.

The Core Idea

If we knew exactly which constraints were active at the solution, we could:

1. Treat active constraints as equalities
2. Ignore inactive constraints entirely
3. Solve the resulting equality-constrained problem using Lagrange multipliers

But we don't know which constraints are active! The active set method guesses and refines:

Solving the Equality Subproblem

At each iteration, we solve an equality-constrained problem. For quadratic objectives (like in QP/MPC), this is a linear system.

Given objective $f(x) = \frac{1}{2}x^T H x + c^T x$ and active constraints $A_{eq} x = b_{eq}$:

The Lagrangian is:

Setting gradients to zero:

This gives the KKT system:

This is a linear system! Standard linear algebra (LU decomposition, etc.) solves it efficiently.

Geometric Interpretation

Picture the cost function as a bowl. You're trying to roll a ball to the bottom, but there are walls (constraint boundaries). The active set method:

1. Rolls the ball downhill
2. When it hits a wall, slides along the wall (constraint becomes active)
3. If it reaches a corner, checks if it can leave any wall (remove from active set)
4. Stops when at the lowest point that doesn't go through any wall

Detailed Iterative Examples

Now let's work through the Active Set Method step-by-step with concrete numbers, showing every calculation. First a simple 2D example, then an MPC problem.

Example 1: Simple 2D Quadratic Program

Setup: Matrices and Gradients

First, let's identify the quadratic structure. Our objective is:

where:

The gradient of $f$ is:

The constraint gradients are:

Find the Unconstrained Minimum

Setting $\nabla f = 0$:

Unconstrained minimum: $x^{unc} = (2, 1.5)$

Check feasibility:

• $g_1(2, 1.5) = 2 + 1.5 - 2 = 1.5 > 0$ ❌ Violated!
• $g_2(2, 1.5) = -2 < 0$ ✓
• $g_3(2, 1.5) = -1.5 < 0$ ✓

The unconstrained minimum violates $g_1$, so we need the Active Set Method.

Iteration 1: Initialize

Starting point: $x^{(0)} = (0.5, 0.5)$ (feasible)

Working set: $\mathcal{W} = \emptyset$ (empty - no constraints assumed active)

Iteration 2: Solve Unconstrained Subproblem

With $\mathcal{W} = \emptyset$, we solve the unconstrained problem:

Check feasibility from $x^{(0)}$ to $x^*$:

We move along the line from $(0.5, 0.5)$ to $(2, 1.5)$:

Check when we hit $g_1 = 0$ (the constraint $x_1 + x_2 = 2$):

At $t = 0.4$:

Update working set: $\mathcal{W} = \{g_1\}$

Iteration 3: Solve with $g_1$ Active

Now we minimize $f$ subject to $g_1(x) = 0$, i.e., $x_1 + x_2 = 2$.

Form the KKT system:

Here $A = \nabla g_1^T = [1, 1]$ and $b = 2$ (from $x_1 + x_2 = 2$):

Solve the system:

From row 1: $x_1 = 2 + \lambda_1$

From row 2: $2x_2 = 3 + \lambda_1 \implies x_2 = \frac{3 + \lambda_1}{2}$

From row 3: $x_1 + x_2 = 2$

Substituting:

Therefore:

Candidate solution: $x^* = (1, 1)$ with $\lambda_1 = -1$

Iteration 3: Check Multiplier Sign

We found $\lambda_1 = -1 < 0$. This is a problem!

Wait - this seems wrong. Let's reconsider. Actually, let me recalculate more carefully...

The issue is that I need to be more careful about the sign conventions. Let me redo this with the Lagrangian:

Taking derivatives:

Using constraint $x_1 + x_2 = 2$:

Therefore:

Correct solution: $x^* = (1, 1)$ with $\lambda_1 = 1 > 0$ ✓

Iteration 3: Check Feasibility

Check all constraints at $x^* = (1, 1)$:

• $g_1(1, 1) = 1 + 1 - 2 = 0$ ✓ (active, by construction)
• $g_2(1, 1) = -1 < 0$ ✓ (satisfied with slack)
• $g_3(1, 1) = -1 < 0$ ✓ (satisfied with slack)

All constraints satisfied!

Optimality Check

We have:

• $\lambda_1 = 1 > 0$ ✓ (multiplier non-negative)
• All constraints satisfied ✓
• KKT stationarity satisfied ✓

Example 2: MPC for a Simple System

Now let's see how Active Set applies to Model Predictive Control. We'll control a simple first-order system with input constraints.

Step 1: Write States in Terms of Inputs

Using the dynamics recursively:

Step 2: Write Cost in Terms of Inputs Only

Substituting into $J$:

Expanding (I'll spare the algebra):

where $\mathbf{u} = [u_0, u_1]^T$ and:

(Let me recalculate this more carefully...)

Actually, let's expand directly:

First term: $(2.4 + 0.5u_0)^2 = 5.76 + 2.4u_0 + 0.25u_0^2$

Second term: $(1.92 + 0.4u_0 + 0.5u_1)^2 = 3.69 + 1.536u_0 + 1.92u_1 + 0.16u_0^2 + 0.4u_0u_1 + 0.25u_1^2$

Collecting:

In matrix form:

Step 3: Write Constraints in Standard Form

Input constraints $-1 \leq u_k \leq 1$ become:

• $u_0 \leq 1 \implies g_1: u_0 - 1 \leq 0$
• $-u_0 \leq 1 \implies g_2: -u_0 - 1 \leq 0$
• $u_1 \leq 1 \implies g_3: u_1 - 1 \leq 0$
• $-u_1 \leq 1 \implies g_4: -u_1 - 1 \leq 0$

Step 4: Find Unconstrained Minimum

Solve $H\mathbf{u} = -f$:

Using Cramer's rule or substitution:

$\det(H) = 1.02 \times 0.7 - 0.4 \times 0.4 = 0.714 - 0.16 = 0.554$

Unconstrained solution: $(u_0, u_1) = (-3.59, -0.69)$

Check constraints:

• $g_1: -3.59 - 1 = -4.59 < 0$ ✓
• $g_2: -(-3.59) - 1 = 2.59 > 0$ ❌ Violated! (means $u_0 < -1$)
• $g_3: -0.69 - 1 = -1.69 < 0$ ✓
• $g_4: -(-0.69) - 1 = -0.31 < 0$ ✓

The unconstrained $u_0 = -3.59$ violates the lower bound $u_0 \geq -1$.

Iteration 1: Add $g_2$ to Working Set

Set $u_0 = -1$ (constraint $g_2$ active) and minimize over $u_1$:

With $u_0 = -1$ fixed:

Minimize: $\frac{dJ}{du_1} = 0.7u_1 + 1.52 = 0 \implies u_1 = -2.17$

Check constraints on $u_1$:

• $u_1 = -2.17 < -1$ ❌ Violated!

Iteration 2: Add $g_4$ to Working Set

Now both $u_0 = -1$ and $u_1 = -1$ (both at lower bounds).

Solution: $\mathbf{u}^* = (-1, -1)$

Check Multipliers

At $\mathbf{u}^* = (-1, -1)$, compute $\nabla J$:

For the active constraints $g_2: -u_0 - 1 \leq 0$ and $g_4: -u_1 - 1 \leq 0$:

KKT stationarity: $\nabla J = \lambda_2 \nabla g_2 + \lambda_4 \nabla g_4$

This gives: $\lambda_2 = -2.516$ and $\lambda_4 = -0.82$

Both multipliers are negative! This means both constraints are active but... wait, let me reconsider the sign convention.

Actually, for constraints of the form $g_i(x) \leq 0$, the KKT condition is:

So:

This gives: $\lambda_2 = 2.516 > 0$ ✓ and $\lambda_4 = 0.82 > 0$ ✓

Verify: Predicted Trajectory

The state decreases: $3 \to 1.9 \to 1.02$. In real MPC, we'd apply only $u_0^* = -1$, measure the new state, and re-solve.

Key Takeaways from the Examples

• The algorithm is systematic: Start unconstrained, hit boundaries, solve constrained subproblems, check multiplier signs, repeat.
• Multipliers tell you if constraints belong: $\lambda_i \geq 0$ means constraint is legitimately active; $\lambda_i < 0$ means remove it.
• MPC naturally leads to QPs: Linear dynamics + quadratic cost + linear constraints = Quadratic Program.
• Saturation is common: When you want aggressive control, actuator limits often become active.

Summary