Message Boards Message Boards

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

Symbolic Minimization Using the Karush-Kuhn-Tucker Conditions

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]))
POSTED BY: Frank Kampas
3 Replies

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.

enter image description here

POSTED BY: Frank Kampas

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 BY: Arturo Hernandez
Quite nice!
POSTED BY: Frank Iannarilli
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