Lagrangian Duality

Posted on Edited on In

We consider an optimization problem over domain in standard form, i.e. which we do not assume to be convex. We assume the optimal value to be .

The Lagrangian associated with this problem is defined as where the vectors and are the dual variables. In fact, the primal problem is equivalent to solving as can be seen by noting that the supremum for feasible , and is for infeasible ones.

The dual function is defined as The dual function is always concave, even when the primal is not convex. We would refer to the set as , because restrictedly working on this set would not cause any loss of generality.

Proposition. , we have which means the dual function always yields lower bounds for the primal.

Proof. If is feasible, then , thus . Thus,

The dual problem is asking about the tightest of such lower bounds, i.e. the solution of which we denote which is primal with max/min inverted.

We have already shown:

Theorem (Weak Lagrangian Duality). which is in satisfying symmetric form. This in fact does not depend on any property of , because it’s an instance of the general max-min theorem.

Strong duality, however, does not hold in general. But if the primal problem is convex, with minimal additional condition, we do have strong duality. One of these is Slater’s condition:

Theorem (Strong Lagrangian Duality). For a standard form convex optimization problem, namely which satisfies Slater’s condition: such that and (i.e. at least one feasible point exists for all inequalities to hold strictly), we have .1 Further, the optimals can be attained by some primal and dual variables (so the / can be replaced by /).2

Proof. cf. Boyd, p235.

KKT Optimality Conditions

We still work without convexity assumptions. Suppose that the primal and dual optimal values are attained and equal (strong duality holds), with and respectively. We have so we must have . This condition is known as complementary slackness.

Further, if we assume the problem defining functions , ’s and ’s are all differentiable (and thus is open), then because minimizes over , its gradient must vanish, i.e.  These two conditions, together with the constraints themselves, are called the Karush-Kuhn-Tucker (KKT) conditions:

The next result states that, when the primal problem is convex, the KKT conditions are also sufficient for the points to be primal and dual optimal.

Theorem. For convex ’s and affine ’s, if satisfy the KKT conditions, then they are primal and dual optimal with zero duality gap.

Proof. Since , is convex in . The gradient condition states that minimizes it, so Corollary. For a convex optimization problem, if Slater’s condition holds (so strong duality holds), then are optimal iff KKT conditions hold.

Also worth noting is that, the usual Lagrangian multiplier method for solving conditional optimals falls happily into solving KKT, too.

Sensitivity

If we perturb the primal into and denote the new optimum , we have:

Theorem. Assume that strong duality holds and the dual optimum is attained (e.g. convex problem satisfying Slater’s condition). Then for all we have

Proof. Suppose is feasible to the perturbed primal. Then and the results follows.

  1. In fact, Slater’s condition can be further relaxed: if any of the ’s are in fact affine, the corresponding inequality also does not have to hold strictly.↩︎

  2. For a case where strong duality holds but cannot be attained, cf. Boyd Exercise 5.26, where Slater’s condition does not hold, and is a limit point.↩︎