noc18-ee31 Lecture 66-Karush-Kuhn-Tucker(KKT) condition

[Music] [Music] hello welcome to another module in this massive open online course so in this module you want to start looking at the KKT condition so the kirusha kuhn tucker conditions which are convenient for solving any optimization problem all right so what we want to start looking at is an important uh player aspect of optimization also termed as KKT conditions also termed as the KKT conditions and these I'm sorry these are the KKT conditions which are also termed which basically short for the Kurush Kern or Kuhn Tucker the Kuhn Tucker conditions and these are convenient these are convenient for solving an optimization problem so now consider again the original or the primal optimization problem consider the original problem what we have is remember we have minimize G naught of X bar subject to G of X bar equal to 0 I equals 1 to up to M + GJ tilde X bar equals 0 I'm sorry I equals 1 to up to l GJ tilde X bar equal to 0 J equals 1 to up to M and in addition assume that strong DR duality holds let us assume that strong duality holds which implies that P star is equal to D star now we know what is the we know what we what we mean by strong duality strong duality employs that p star which is the optimal value of the original that is the primal optimization problem equals d star which is the optimal value of the dual optimization problem all right we have the dual cost function the dual objective function G D lambda bar nu bar maximizes subject to constraint lambda bar is greater than or equal to 0 you get the dual optimal value D star and the strong duality holds then P star equals D star ok so P star is optimal value of primal problem and D star is basically your optimal value of the diva optimal value of the dual optimization okay now let X star now in addition let X bar star equals primal optimal problem or the primal optimal solution and that is where the optimal values achieved for the primal optimization work that is x-bar is the solution of the primal optimization problem similarly let lambda bar star nu bar star equals the optimal value and not the optimal value that is the solution of the the dual optimal problem that is where the dual optimal is achieved okay then by strong duality then by duality or rather strong duality so we have so basically what this means is that is if you look at the objective value G naught at X star that is equal to P star and if you look at the value of the optimization the dual objective function at lambda bar star and nu bar star this will be the dual optimal value that is disturb this optimal value of the dual optimization problem all right so we have P star and D star and now from strong duality we have we have already said this implies P star equals T star which implies that G naught of X bar star equals the dual function GD of lambda bar star mu bar star now G naught now if you look at this GD of lambda bar star now dual function remember the dual function is the infimum of the Lagrangian all right so the dual function G D is nothing but the infimum with the Lagrangian over the set of all feasible points X bar all right so this is basically or infimum or basically the minimum okay and this is now the minimum over X bar of G naught X bar plus summation I equal to 1 to L lambda I star GI of X bar plus summation j equals 1 to M nu J star G G tilde of X bar okay so GD of lambda bar star nu bar star is nothing but the infimum of the lagrangian over all x bar at lambda bar star and u bar stock okay so that is the key argument here this transition now once you realize that the last of the argument is very simple now if you look at this this is the minimum over all X bar which means this is less than or equal to so remember the optimal value of this is the minimum or all X bar which means it is less than or equal to the H value corresponding to X bar star okay so this is less because X bar star is one particular X bar that belongs to the feasible set okay so therefore this is less than or equal to G naught of X bar star plus summation I equals 1 to L summation I equals 1 to L lambda I star G I of X bar star plus summation G was 1 to M you just GJ tilde X bar star which is less than or equal to G not and now if you look at this quantity now look at this again X bar star is the optimal value belongs to the feasible set satisfies the constraint implies this is equal to zero which implies this is equal to zero so this is equal to zero now this again lambda I star remember is greater than or equal to zero gix bar star X bar belongs to feasible set X bar star belongs to the feasible set so this is less than or equal to zero so this is less than or equal to zero so this is less than or equal to G note X bar star and therefore now you have a very interesting observation you have started from G note X bar star you ended with G naught X bar star which are indeed equal this implies all the intermediate quantities so you have the left G naught X bar star less than equal to write G naught X bar which are nothing but one and the same which means all the intermediate quantities which are sandwiched in between must be also equal to G naught X bar star okay so which means that all intermediate quantities must equal this is very simple for instance if you have the inequality 5 less than or equal to X less than equal to y less than equal to 5 now remember the end we have 5 5 and X 5 less or equal to X X less than equal to 5 there is only one possibility that is x equals 5 y equals 5 so all the intermediate points so similarly if you follow this chain of arguments towards both ends your G naught X bar star which means all the intermediate quantities must be G naught X bar star and therefore this implies in particular in particular in particular we must have summation I equals 1 to L lambda i star eix bar star plus equals 1 to m new ice new j star GJ tilde X bar star this is equal to G naught X bar star which implies that now if you cancel these things G note X bar star G note X bar star we know this is 0 anyway so this implies that the only remaining term that is summation i equals 1 to l lambda i GI x bar in this is equal to 0 now remember each of this quantity is lambda igix bar is less than or equal to 0 the sum of several non positive quantities is equal to 0 which means each of these quantities is equal to you remember each of this code is less than equal to 0 but their sum is equal to 0 which means each of these quantity is equal to 0 this implies lambda I into gix bar equal to zero or each I for I equals 1 2 up 2 and this is a very interesting property this is termed as complementary slackness and I am going to explain this in a moment this is termed interesting name the meaning of this is following this memorize lambda I into GX bar is 0 it implies either so we have lambda I J X bar equal to 0 so this implies two things either lambda I equals 0 correct which means GI of X bar can be less than 0 or lambda I is greater than 0 and J of X bar equal to 0 so in this case now let us look at this in this case the constraint is tight it is met with equality and Lagrange multiplier L M equals slack okay that is greater than now in this case the constraint is slide GX bar is less than zero so there is some slack or a J X bar is less than zero which means whatever is GI X bar minus 0 that is the slack so the constraint is slack and the LM Lagrange multiplier equals tight because the Lagrange multiplier equals zero so this is the meaning of the complement complementary slackness that is either the Lagrange multiplier is slack or the constraint is slug it cannot happen that both the Lagrange multiplier and constraint are slack that is it cannot happen that lambda I is greater strictly greater than 0 and GI of X bar is strictly less than 0 this cannot happen because lambda I into J of X bar must equal 0 okay so it cannot happen that lambda I is greater than 0 GJ or GI of X bar is strictly less than 0 this is not possible which means either constraint or Lagrange multiplier has to be slacked this terminus complimentary slackness so this compliment each other either Lagrange multiplier or constraint okay this is termed this term as complimentary this property is termed as complementary slackness and this is a unique aspect of the KKT conditions that is that is both cannot be and both cannot be that it cannot happen that the Lagrange multiplier is strictly greater than zero the constraint inequality constraint is strictly less than zero it can hardly happen only that only one of them is slack all right the other is zero so the Lagrange multiplier is zero the constraint is slack as the constraint is zero the Lagrange multiplier is like okay and this is known as complementary slackness only one or the other can be slack okay termed only either Lagrange multiplier or constraint can be slack not has to be slack can be slack only one or other can be slack only one or the other can be slack that is basically your complementary slackness and the KKT conditions can be finally stated as follows the kirusha kuhn tucker conditions these are your curse the Kirsch could Tucker and the KKT conditions are basically if X bar lambda bar nu bar are optimal that is X bar for obviously the primal problem this is for the primal and this is for the doer and strong duality holds and strong duality holds this implies that your G naught of X bar equal G D of lambda bar nu bar then it must be that then first we have the primal constraints these must hold the primal constraints are basically GI of X bar less than equal to zero for Ike was one two up to l GJ tilde of X bar equals zero G equals 1 2 up to M the dual constraints must hold what are the dual constraints remember lambda bar is component-wise greater than equal to zero which implies each lambda I is greater than equal to 0 for I equals 1 to up to L that is the Lagrange multipliers associated with the inequality constraints are greater than or equal to zero all right complementary slackness this is the third condition complementary slackness what happens in complementary slackness we have with respect the Lagrangian with respect to the gradient with respect to the Lagrangian equals zero this implies that the gradient of the Lagrangian vanishes that this implies basically the gradient with respect to X because remember at X bar this is the infimum of the of the Lagrangian correct at this optimal value X bar we have the infimum of the Lagrangian which means the gradient we have the minimum of the Lagrangian function therefore the gradient with respect to X bar of the Lagrangian has to vanish at X bar okay Plus I'm sorry this is not complementary slackness complementary slackness let me just mention the complementary slackness aspect this will come later so the complementary slackness we have already seen that that is lambda I into GI of X bar equals 0 i equals 1 to up to L that is either lambda equals 0 or GI X bar equals either lambda ik either lambda greater than 0 or GI X bar less than 0 that is either is slack but not both either is slack but not both and finally since X bar is the infimum or at X bar you have the minimum of the Lagrangian of the Lagrangian function Lagrangian of X bar lambda or nu bar the gradient with respect to X bar of the Lagrangian must vanish at this point X bar that is we must have Delta gradient of respect to X bar G note X bar plus summation I equal to 1 to L gradient with respect to I G of X bar plus summation J goes 1 2 m nu J the gradient with respect to X of G J tilde X bar this must be equal to C alright and these are the KKT conditions and if these are X bar lambda bar nu bar are optimal solutions of the primal and the dual optimization problems x-bar lambda and strong duality holds X bar lambda bar nu bar must satisfy must satisfy the KKT conditions okay so these are the four KKT conditions that must be satisfied by the solution solutions X bar of the X bar of the primal optimization problem and lambda bar in you bar of the duo optimization alright so let us stop here and continue in the subsequent modules thank you very much [Music] [Music]