# Symbolic Minimization Using the Karush-Kuhn-Tucker Conditions

Posted 8 years ago
7805 Views
|
1 Reply
|
3 Total Likes
|
 The following code does symbolic minimization using Reduce to solve the Karush-Kuhn-Tucker conditions.  No sign conditions are placed on the Lagrange multipliers, so it gives all maxima and minima.  The subscripts of the multipliers are the constraint they are multiplying. consconvrule = {    x_ >= y_ -> y - x,    x_ == y_ -> x - y ,    x_ <= y_ -> x - y,    lb_ <= x_ <= ub_ -> (x - lb) (x - ub),    ub_ >= x_ >= lb_ -> (x - lb) (x - ub)    };  KKT[obj_, cons_List, vars_List] := Module[  {convcons, gradobj, gradcons, \[CapitalLambda]},  convcons = (cons /. consconvrule);  {gradobj, gradcons} = D[{obj, convcons}, {vars}];  \[CapitalLambda] = Subscript[\[Lambda], #] & /@ cons;  LogicalExpand @ Reduce[    Flatten[{      Thread[gradobj == \[CapitalLambda].gradcons],      Thread[\[CapitalLambda]*convcons == 0] /.        Subscript[\[Lambda], Equal[a_, b_]] -> 0,      cons,      {objval == obj}      }],    Join[{objval}, vars, \[CapitalLambda]],    Reals,    Backsubstitution -> True    ]  ]Here's an example applicationKKT[x + 2 y + 3 z, {x^2 + y^2 + z^2 == 1, 3 x + 2 y + z <= 1}, {x, y,   z}] (objval == -Sqrt[14] && x == -(1/Sqrt[14]) && y == -Sqrt[(2/7)] &&     z == -(3/Sqrt[14]) &&     Subscript[\[Lambda], x^2 + y^2 + z^2 == 1] == -Sqrt[(7/2)] &&     Subscript[\[Lambda], 3 x + 2 y + z <= 1] == 0) ||  (objval ==      1/7 (5 - 2 Sqrt[78]) && x == 1/42 (9 + 2 Sqrt[78]) &&     y == 1/42 (6 - Sqrt[78]) && z == 1/42 (3 - 4 Sqrt[78]) &&     Subscript[\[Lambda], x^2 + y^2 + z^2 == 1] == -2 Sqrt[6/13] &&     Subscript[\[Lambda], 3 x + 2 y + z <= 1] ==     1/91 (65 + 2 Sqrt[78])) || (objval == 1/7 (5 + 2 Sqrt[78]) &&    x == 1/42 (9 - 2 Sqrt[78]) && y == 1/42 (6 + Sqrt[78]) &&    z == 1/42 (3 + 4 Sqrt[78]) &&    Subscript[\[Lambda], x^2 + y^2 + z^2 == 1] == 2 Sqrt[6/13] &&    Subscript[\[Lambda], 3 x + 2 y + z <= 1] == 1/91 (65 - 2 Sqrt[78]))
Answer
1 Reply
Sort By:
Posted 8 years ago
 Quite nice!
Answer
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments