# Symbolic Minimization Using the Karush-Kuhn-Tucker Conditions

Posted 10 years ago
10088 Views
|
3 Replies
|
4 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]))
3 Replies
Sort By:
Posted 2 months ago
 I was fascinated by Frank, I know it's been around for a long time, but could you provide more information about the scope of this code, some variants you've found and for what cases it works?Is there an article or book that talks about these topics?
Posted 2 months ago
 Recently I've been using the Kuhn-Tucker approach to maximize the minimum separation between polygons inside a polygon border. I'm using ParametricIPOPTMinimize, rather than Reduce, to solve the resulting equations.
Posted 10 years ago
 Quite nice!