Lagrangian Duality for Dummies - Stanford Computer Science

1 Lagrangian Duality for DummiesDavid KnowlesNovember 13, 2010We want to solve the following optimisation problem:minf0(x)(1)such thatfi(x) 0 i 1,..,m(2)For now we do not need to assume convexity. For simplicity we assume noequality constraints, but all these results extend straightforwardly in thatcase. An obvious (but foolish) approach would be to achieve this by min-imising the following function:J(x) ={f0(x),iffi(x) 0 i ,otherwise(3)=f0(x) + iI[fi(x)](4)whereI[u] is a infinite step function:I[u] ={0,ifu 0 ,otherwise(5)This functionIgives infinite penalty to a constraint being dissatisfied. Nowif we were able to minimiseJ(x) then we would have a way of solving ouroptimisation problem.}}

2 Unfortunately,J(x) is a pretty horrible function tooptimise becauseI[u] is both non-differentiable and discontinuous. Whatabout replacingI[u] with something nicer? A straight line, uis certainlyeasier to handle. This might seem like a pretty dumb choice, but for 0 thepenalty is at least in the correct direction (we are penalised for constraintsbeing dissatisfied), and uis a lower bound onI[u] (see Figure 1). If we1 (u)Figure 1: The infinite step functionI(u) and the linear relaxation u. For 0 note that uis a lower bound onI(u).replaceI[u] by uin the functionJ(x) we get a function ofxand knownas the Lagrangian :L(x, ) =f0(x) + i ifi(x)(6)Note that if we take the maximum with respect to of this function werecoverJ(x).

3 For a particular value ofx, if the constraints are all satisfied ( (x) 0 i) then the best we can do is to set i= 0 i, soL(x,0) =f0(x).If any of the constraints are not satisfied, thenfi(x) 0 for somei, and wecan makeL(x, ) infinite by taking i . So we have:max L(x, ) =J(x)(7)That s all well and good, but how does it help us solve our original optimi-sation problem? Remember that we want to minimiseJ(x), which we now2know means finding:minxmax L(x, )(8)This is a hard problem. But what would happen if we reversed the order ofmaximisation over and minimisation overx? Then we would be finding:max minxL(x, ) = max g( )(9)whereg( ) = minxL(x, ) is known as the dual function.

4 Maximising thedual functiong( ) is known as thedual problem, in the constrast the orig-inalprimal problem. Sinceg( ) is a pointwise minimum of affine functions(L(x, ) is affine, linear, in ), it is a concave function. The minimi-sation ofL(x, ) overxmight be hard. However sinceg( ) is concave and i 0 iare linear constraints, maximisingg( ) over is a convex optimi-sation problem, an easy problem. But does solving this problem relate tothe original problem? Recall that uis a lower bound onI(u). As a result,L(x, ) is a lower bound onJ(x) for all 0. ThusL(x, ) J(x) 0(10) minxL(x, ) =g( ) minxJ(x) =:p?

5 (11) d?= max g( ) p?(12)wherep?andd?are the optima of the primal and dual problems see that for any the dual functiong( ) gives a lower bound on theoptimal problem. We can then interpret the dual problem of maximisingover as finding the tightest possible lower bound onp?:max minxL(x, ) minxmax L(x, )(13)This property is known as weak Duality , and in fact holds in general forsmooth functionsL. The differencep? d?is known as the optimal dualitygap. Strong Duality means that we have equality, the optimal dualitygap is zero. Strong Duality holds if our optimisation problem is convex and astrictly feasible point exists ( a pointxwhere all constraints are strictlysatisfied).

6 In that case the solution of the primal and dual problems is equiv-alent, the optimalx?is given by minxL(x, ?), where ?is the maximiserofg( ).3 Duality gives us an option of trying to solve our original (potentiallynonconvex) constrained optimisation problem in another way. If minimisingthe Lagrangian overxhappens to be easy for our problem, then we know thatmaximising the resulting dual function over is easy. If strong Duality holdswe have found an easier approach to our original problem: if not then westill have a lower bound which may be of use. Duality also lets us formulateoptimality conditions for constrained optimisation KKT ConditionsFor an unconstrained convex optimisation problem we know we are at theglobal minimum if the gradient is zero.

7 The KKT conditions are the equiva-lent conditions for the global minimum of a constrained convex optimisationproblem. If strong Duality holds and (x?, ?) is optimal thenx?minimisesL(x, ?), giving us the first KKT condition: xL(x?, ?) = xf0(x?) + i ?i xfi(x?) = 0(14)We can interpret this condition by saying that the gradient of the objectivefunction and constraint function must be parallel (and opposite). This meansthat moving along the constraint surface cannot improve the objective func-tion. This concept is illustrated for a simple 2D optimisation problem withone inequality constraint in Figure , by definition we have:f0(x?)

8 =g( ?) = minxL(x, ?) f0(x?) + i ?ifi(x?) f0(x?)(15)where the last inequality holds because i ?ifi(x?) 0. We see that i ?ifi(x?) = 0(16)Since ?i 0 andfi(x?) 0 for alli, this gives the second KKT condition: ?ifi(x?) = 0 i(17)This condition is known as complementary slackness: either ?iorfi(x?) mustbe zero for alli. If the constraint is inactive then ?i= 0, andfi(x?) has some4 f0 f11 Figure 2: The first KKT condition, xf0(x?) + ?1 xf1(x?) = 0. The blackcontours are the objective function, the red line is the constraint the optimal solution the gradient of the objective and constraint mustbe parallel and opposing so that no direction along the constraint boundarycould give an improved objective value.

9 We can interpret ?i= 0 as meaning that we can disregardconstraintiin the first KKT condition since this constraint is not the constraint is active thenfi(x?) = 0 and ?ihas some positive that this condition means that the lower bound uonI(u) shown inFigure 1 is tight: if is zero anduthe functions match, and ifu= 0, thefunctions also match. The remaining KKT conditions are simply the primalconstraints and dual constraints ( that ?i 0).5