The Karush–Kuhn–Tucker (KKT) Conditions and the Interior Point Method for Convex Optimization – Transcript

00:00in the previous video we have seen what duality means for convex sets and what duality means for convex functions in this video we will see what duality means for convex optimization problems and we will see how it can be helpful for designing efficient algorithms for solving these problems let's work with an example this time

00:27imagine you are the captain of a ship in the middle of the ocean using some sophisticated equipment you know that the rain is coming from some direction c for example c equals the vector 1 1. so you decide to steer the ship in the opposite direction as much as possible you also remember that the sea is infested with sharks

00:51except for a safe circular region of radius one unit this now becomes an optimization problem our decision variable is the two-dimensional vector x that represents the position of the ship our objective is c transpose x or in other words x one plus x and we have a single constraint which is that we need to pick x from the unit disk

01:18note that this is a convex optimization problem because the objective function is linear and in particular convex and the constraint is given by a convex function one thing we would love to do is somehow get rid of the constraint indeed if this constraint did not exist then we would just have an unconstrained convex optimization problem and we have discussed those in detail in the previous video and the nice way

01:46to visualize what is going on in that case is to imagine that the level of the c is tilted according to the objective function in such a way that low sea levels correspond to low objective values and high sea levels to high objective values it becomes visually clear that the answer would simply be to steer the ship in the direction of minus c which matches our intuition so keep this

02:12analogy in mind for later because it will be useful but life is unfair and you often need to deal with constraints otherwise you become a snack for some hungry sharks so one way to get rid of a constraint is to move it to the objective function via what is called a penalty function so what is a penalty function you ask well

02:38it is simply a function that penalizes you for not satisfying a constraint and a natural choice for this penalty function is a function that takes the value of 0 when its argument is negative and the value plus infinity when its argument is positive let's call this particular penalty function the zero infinity penalty for later references now if you pick an x that satisfies the constraint

03:05then the penalty term will evaluate to zero it is as if the penalty term simply was not there but if you pick an x that does not satisfy the constraint then the penalty term will evaluate to plus infinity which is really the worst possible outcome you can hope for as far as minimization problems are concerned visually this penalty function raises the sea level outside of our disk of safety to plus infinity so it makes it no

03:33longer desirable to steer the shape outside of this circle even if the original objective value was smaller there and this penalty term is almost perfect we generally get rid of the constraint without affecting the optimal value of the minimization problem the price we pay however is that our objective function now can take the value plus infinity and while we can just replace it with some really large value like

04:00a million we would still have the issue that our objective function has become discontinuous and it would no longer make sense to take the gradient of this function for example one thing we could try here is approximate this penalty function with another function that is smooth and does not take infinite values the simplest thing we could try here is to pick a linear function as our penalty function something like u times y where the slope

04:28u is a non-negative number visually you can see how this penalty is a smooth approximation of the zero infinity penalty function how does this linear penalty work well the idea is simple if you pick an x that does not satisfy the constraint this penalty term will evaluate not to infinity this time but to a quantity that is proportional to how much

04:54you violated the constraint and if you pick an x that satisfies the constraint believe it or not you actually get rewarded and as much as we like it when we get rewarded for doing the right thing and penalize for violating constraints it is less than ideal in this scenario because it affects the optimal value of our minimization problem and the amount by which it affects the

05:19optimal value depends on the value of the slope you clearly for any value of u this linear approximation is rather poor but notice that if you consider all of the u's and take the maximum of the corresponding linear penalties you can check by looking at the plot that you recover the original zero infinity penalty function

05:46which is pretty neat right so let's try to use this maximum as our penalty function and note that now we can take the maximum outside since x1 plus x2 does not depend on you what we have now is what is called a min max problem and a nice interpretation of what's going on here is to view the min max problem as a two persons game

06:12we have an x player and a u player the x player picks an x to try to make this quantity small while the u player will try to penalize us if we don't satisfy the constraints and pku that makes this term big and in games like these it is important to know who plays first indeed if given the choice you will always want to go second because the second player gets the benefit of knowing what the first player

06:41did so here naturally the x player might protest that it is not fair that he always goes first and wonders what happens if the other player you goes first for a change well if you goes first then the x player's job becomes much simpler he just needs to minimize this quantity and i emphasize here that this quantity is a convex function

07:06without any constraints so x can just take the gradient of this quantity set it to 0 and solve for x and now that we know what the response of x should be we can plug that back in maximize with respect to u and get the solution x 1 equals x 2

07:32equals minus square root of 2 over 2. it is important to note here that what we have just done is not solve the original problem but a variation of it the problem that we solved is actually called the dual problem while the original problem is called the primal problem and there are a lot of benefits to considering this dual problem but before we talk about that let's just take a step back from this example for a

07:59bit and see what the dual problem is for convex optimization problems in general let us now consider a general convex optimization problem and inspired by the example we just saw let's try to derive its dual the first step is to get rid of the constraints for that multiply each function in the constraints with a scalar that represents the slope of our penalty function

08:26and move these functions from the constraints to the objective function and similar to what we did in the example we are going to take the maximum over the scalars uis and vi's for inequality constraints like the ones we had in the example we really want the cost to be positive while for equality constraints where we want to penalize positive and negative values alike we will allow the slope to be positive

08:53or negative and now to get the dual problem we pull the maximum outside and we switch the order of the min and the max this quantity here is known in the literature as the lagrangian of the optimization problem and the dual problem is referred to as the lagrangian du and we will go back to the lagrangian in a second keywords are in order at this point

09:21first the dual problem has one variable for each constraint of the primer these can be interpreted as the cost or price for violating that constraint second the dual problem gives us a lower bound on the optimal value of the primal problem this is because in the dual problem and unlike in the primal problem the x player which tries to make our objective

09:46function small goes second and therefore has the advantage and finally and what is more interesting is that under some mild assumptions strong duality holds this means that the optimal value of the primal and the dual problem actually coincide so you can solve whichever you find easiest and you will find the right answer the assumptions i refer to are a bit technical so i won't list them here

10:15just know that they are usually satisfied and they are satisfied for our toe example for instance anyway we won't worry too much about that and we're just going to assume from now on that strong duality holds and now that we have derived the dual problem let's see how it can be useful for solving convex optimization problems and this will lead us to the next theme of this video which is the

10:40celebrated kkt conditions let's consider our friend the lagrangian again remember that the x player tries to minimize this quantity so at the optimal solution x the gradient with respect to x better be zero this is a necessary condition that any optimal solution to the optimization problem should satisfy think of it as a generalization of the condition that grad of f

11:07equals zero for any minimizer of an unconstrained optimization problem there is a nice geometric intuition behind this condition and let's see a visual explanation of what is happening here and for simplicity let's consider a case where we have only one inequality just like the example we saw before in which case this condition is saying that grad f and grad g are inversely

11:33proportional to each other let us delimit the feasible region given by g with a green line and consider an arbitrary point x inside this region at this point x let's draw the gradient of g and the gradient of f and remember what gradients represent when you follow the opposite direction to the gradient of a function the value of that function will decrease

12:02at least locally so we know that in this green rectangle the value of g will remain smaller than zero and therefore we can safely move x inside of this region without fear of violating the constraint similarly if you nudge x to fall in the yellow region you will reduce and hence improve the objective function f so if the yellow and green region intersect

12:29it means that you can nudge your x a bit stay feasible and improve the objective value so such an x cannot be optimal said differently if x were optimal then necessarily the two regions should not intersect which can only happen if the gradient of f and g are inversely proportional to each other at this point it is a good idea to recap

12:55what we have just seen we have seen that if x is an optimal solution then it should satisfy this gradient condition and you might wonder if this condition is also sufficient in the sense that if for some point x you succeeded in finding a scalar u that makes this condition hold then that makes x an optimal solution after all for unconstrained optimization problems