What is duality in optimization, and how are primal and dual problems related?

Duality studies paired problems: the primal is the original minimization problem, and the dual is derived from the Lagrangian to provide bounds on the primal value. For minimization, the dual problem maximizes a lower bound to the primal value; the dual optimum is never greater than the primal optimum, and a zero duality gap (p* = d*) indicates strong duality under suitable conditions.

What is the Lagrangian and how is it used to derive the dual problem?

The Lagrangian is L(x, λ, μ) = f(x) + ∑ λ_i g_i(x) + ∑ μ_j h_j(x), with λ_i ≥ 0 for inequality constraints. The dual function is g(λ, μ) = inf_x L(x, λ, μ). The dual problem is to maximize g(λ, μ) subject to λ ≥ 0 (and any μ unconstrained). The dual provides bounds and connects primal and dual solutions.

What are the KKT conditions and what does each part mean?

For minimize f(x) subject to g_i(x) ≤ 0 and h_j(x) = 0, there exist multipliers λ_i ≥ 0 and μ_j such that: (1) Stationarity: ∇f(x*) + ∑ λ_i ∇g_i(x*) + ∑ μ_j ∇h_j(x*) = 0; (2) Primal feasibility: g_i(x*) ≤ 0, h_j(x*) = 0; (3) Dual feasibility: λ_i ≥ 0; (4) Complementary slackness: λ_i g_i(x*) = 0 for all i.

When do the KKT conditions guarantee optimality?

If the problem is convex and Slater's condition holds (there exists a strictly feasible point with g_i(x) < 0 and h_j(x) = 0), the KKT conditions are necessary and sufficient for optimality.

What is the duality gap and what does a zero duality gap imply?

The duality gap is p* − d* (primal optimum minus dual optimum). A zero duality gap (strong duality) means p* = d*, so solving the dual yields the primal optimum and the KKT conditions hold at optimality.