Lagrangian Duality, Dual Problem & Slater's Condition
“Lagrange dual function g(lambda, nu), concavity of dual, weak duality, strong duality, and Slater's condition.”
1.The Philosophy & Mechanics of Lagrangian Duality
§ 3.1.Duality transforms a difficult constrained optimization problem in primal space into an alternative optimization problem in dual multiplier space.
The Lagrange Dual Function:
g(lambda, nu) = inf_{x in D} L(x, lambda, nu) = inf_{x in D} [ f_0(x) + Sum lambda_i f_i(x) + Sum nu_j h_j(x) ].
Because g(lambda, nu) is the pointwise infimum of affine functions in (lambda, nu), the dual function is always concave, regardless of whether the primal problem is convex.
Weak vs Strong Duality:
- Weak Duality: d <= p (always true for any optimization problem).
- Strong Duality: d = p (zero duality gap).
Slater's Condition:
Guarantees strong duality for convex optimization problems if there exists at least one interior strictly feasible point: f_i(x) < 0 for all inequality constraints.
2. Worked Practice Problem: Deriving Dual Function & Verifying Duality
Minimize the Lagrangian over x analytically before setting up the dual maximization.
Problem: Consider the primal problem: minimize f(x) = (1/2) * x^2 subject to x >= 2 (rewritten as 2 - x <= 0). (a) Derive the Lagrange dual function g(lambda). (b) Solve the dual problem and verify strong duality.
Step 1: Formulate Lagrangian with multiplier lambda >= 0:
L(x, lambda) = (1/2) x^2 + lambda (2 - x).
Step 2: Find dual function g(lambda) = inf_x L(x, lambda):
dL/dx = x - lambda = 0 => x*(lambda) = lambda.
Substitute x* = lambda into L:
g(lambda) = (1/2) lambda^2 + lambda (2 - lambda)
g(lambda) = (1/2) lambda^2 + 2lambda - lambda^2 = 2lambda - (1/2) lambda^2.
Notice: g(lambda) is strictly concave (d^2 g / dlambda^2 = -1 < 0).
Step 3: Solve the dual problem: maximize g(lambda) subject to lambda >= 0:
dg/dlambda = 2 - lambda = 0 => lambda* = 2.
Check feasibility: lambda* = 2 >= 0 (Feasible!).
Dual optimal value: d = g(2) = 2(2) - (1/2)(2^2) = 4 - 2 = 2.
Step 4: Solve the primal problem directly:
f(x) = (1/2) * x^2 increases for x >= 0.
Subject to x >= 2, the minimum occurs at boundary x* = 2.
Primal optimal value: p = f(2) = (1/2) (2^2) = 2.
Step 5: Compare primal and dual values:
p = 2, d = 2 => p - d = 0 (Zero Duality Gap).
Conclusion: Strong duality holds with optimal primal value p = 2 and dual multiplier lambda = 2.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.