4
|
13515 Views
|
3 Replies
|
4 Total Likes
View groups...
Share
GROUPS:

# Symbolic Minimization Using the Karush-Kuhn-Tucker Conditions

Posted 11 years ago
 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 1 year 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 1 year 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 11 years ago
 Quite nice!