Message Boards Message Boards

GROUPS:

Symbolic Minimization Using the Karush-Kuhn-Tucker Conditions

Posted 8 years ago
7806 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 application
KKT[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]))
Quite nice!
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract