Convex Optimization - Lagrange Multipliers

Lagrange Multipliers

Consider a convex minimization problem given in standard form by a cost function and inequality constraints, where . Then the domain is:

The Lagrangian function for the problem is

L(x,λ₀,...,λ_m) = λ₀f(x) + λ₁g₁(x) + ... + λ_mg_m(x).

For each point x in X that minimizes f over X, there exist real numbers λ₀, ..., λ_m, called Lagrange multipliers, that satisfy these conditions simultaneously:

1. x minimizes L(y, λ₀, λ₁, ..., λ_m) over all y in X,
2. λ₀ ≥ 0, λ₁ ≥ 0, ..., λ_m ≥ 0, with at least one λ_k>0,
3. λ₁g₁(x) = 0, ..., λ_mg_m(x) = 0 (complementary slackness).

If there exists a "strictly feasible point", i.e., a point z satisfying

g₁(z) < 0,...,g_m(z) < 0,

then the statement above can be upgraded to assert that λ₀=1.

Conversely, if some x in X satisfies 1-3 for scalars λ₀, ..., λ_m with λ₀ = 1, then x is certain to minimize f over X.