Message Boards

WOLFRAM COMMUNITY

4726 Views

3 Replies

0 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Reduce Improves Minimize

Frank Kampas

Frank Kampas, Physicist at Large Consulting

Posted 6 years ago

consider the following symbolic minimization problem: obj = E^(x1 x4) + x1 + 2 x2 + 4 x5; cons = {-6 + x1 + 2 x2 + 5 x5 == 0, -3 + x1 + x2 + x3 == 0, -2 + x4 + x5 + x6 == 0, -1 + x1 + x4 == 0, -2 + x2 + x5 == 0, -2 + x3 + x6 == 0, 0 <= x1, 0 <= x2, 0 <= x3, 0 <= x4, 0 <= x5, 0 <= x6, x1 <= 1, x4 <= 1}; vars = {x1, x2, x3, x4, x5, x6}; Minimize gives a strange answer which doesn't satisfy the constraints: In[4]:= sln = Minimize[{obj, Sequence @@ cons}, vars] Out[4]= {19/3, {x1 -> 3 - x2 - x3, x2 -> 2 - x3 + x4, x3 -> 1/2 (-1 + x4 + 5 x5), x4 -> -1 + 3 x5, x5 -> 2/3, x6 -> 1/3}} In[5]:= cons /. sln[[2]] Out[5]= {1/3 - x2 - x3 + 2 (2 - x3 + x4) == 0, 2 - x2 - 2 x3 + x4 + 1/2 (-1 + x4 + 5 x5) == 0, -2 + 3 x5 == 0, 1 - x2 - x3 + 3 x5 == 0, 2/3 - x3 + x4 == 0, -(5/3) + 1/2 (-1 + x4 + 5 x5) == 0, 0 <= 3 - x2 - x3, 0 <= 2 - x3 + x4, 0 <= 1/2 (-1 + x4 + 5 x5), 0 <= -1 + 3 x5, True, True, 3 - x2 - x3 <= 1, -1 + 3 x5 <= 1} If I first Reduce the constraints and use the result for Minimize and then rerun Reduce using the objective function value, I get a solution which does satisfy the constraints. In[6]:= r = Reduce[cons, vars, Reals, Backsubstitution -> True] Out[6]= 0 <= x1 <= 1 && x2 == (4 + x1)/3 && x3 == 1/3 (5 - 4 x1) && x4 == 1 - x1 && x5 == (2 - x1)/3 && x6 == 1/3 (1 + 4 x1) In[7]:= slnr = Minimize[obj, r, vars] Out[7]= {19/3, {x1 -> -4 + 3 x2, x2 -> (7 - x3)/4, x3 -> 1/3 (1 + 4 x4), x4 -> -1 + 3 x5, x5 -> 2/3, x6 -> 1/3}} In[8]:= r1 = Reduce[obj == slnr[[1]] && r, vars, Reals, Backsubstitution -> True] Out[8]= x1 == 0 && x2 == 4/3 && x3 == 5/3 && x4 == 1 && x5 == 2/3 && x6 == 1/3 In[9]:= cons /. ToRules[r1] Out[9]= {True, True, True, True, True, True, True, True, True, True, \ True, True, True, True}

consider the following symbolic minimization problem:

obj = E^(x1 x4) + x1 + 2 x2 + 4 x5;

cons = {-6 + x1 + 2 x2 + 5 x5 == 0, -3 + x1 + x2 + x3 == 
    0, -2 + x4 + x5 + x6 == 0, -1 + x1 + x4 == 0, -2 + x2 + x5 == 
    0, -2 + x3 + x6 == 0, 0 <= x1, 0 <= x2, 0 <= x3, 0 <= x4, 0 <= x5,
    0 <= x6, x1 <= 1, x4 <= 1};

vars = {x1, x2, x3, x4, x5, x6};

Minimize gives a strange answer which doesn't satisfy the constraints:

In[4]:= sln = Minimize[{obj, Sequence @@ cons}, vars]

Out[4]= {19/3, {x1 -> 3 - x2 - x3, x2 -> 2 - x3 + x4, 
  x3 -> 1/2 (-1 + x4 + 5 x5), x4 -> -1 + 3 x5, x5 -> 2/3, x6 -> 1/3}}

In[5]:= cons /. sln[[2]]

Out[5]= {1/3 - x2 - x3 + 2 (2 - x3 + x4) == 0, 
 2 - x2 - 2 x3 + x4 + 1/2 (-1 + x4 + 5 x5) == 0, -2 + 3 x5 == 0, 
 1 - x2 - x3 + 3 x5 == 0, 
 2/3 - x3 + x4 == 0, -(5/3) + 1/2 (-1 + x4 + 5 x5) == 0, 
 0 <= 3 - x2 - x3, 0 <= 2 - x3 + x4, 0 <= 1/2 (-1 + x4 + 5 x5), 
 0 <= -1 + 3 x5, True, True, 3 - x2 - x3 <= 1, -1 + 3 x5 <= 1}

If I first Reduce the constraints and use the result for Minimize and then rerun Reduce using the objective function value, I get a solution which does satisfy the constraints.

In[6]:= r = Reduce[cons, vars, Reals, Backsubstitution -> True]

Out[6]= 0 <= x1 <= 1 && x2 == (4 + x1)/3 && x3 == 1/3 (5 - 4 x1) && 
 x4 == 1 - x1 && x5 == (2 - x1)/3 && x6 == 1/3 (1 + 4 x1)

In[7]:= slnr = Minimize[obj, r, vars]

Out[7]= {19/3, {x1 -> -4 + 3 x2, x2 -> (7 - x3)/4, 
  x3 -> 1/3 (1 + 4 x4), x4 -> -1 + 3 x5, x5 -> 2/3, x6 -> 1/3}}

In[8]:= r1 = 
 Reduce[obj == slnr[[1]] &&  r, vars, Reals, Backsubstitution -> True]

Out[8]= x1 == 0 && x2 == 4/3 && x3 == 5/3 && x4 == 1 && x5 == 2/3 && 
 x6 == 1/3

In[9]:= cons /. ToRules[r1]

Out[9]= {True, True, True, True, True, True, True, True, True, True, \
True, True, True, True}

POSTED BY: Frank Kampas

3 Replies

Sort By:

Frank Kampas

Frank Kampas, Physicist at Large Consulting

Posted 6 years ago

Here's a situation where Minimize does not give a solution, but using Reduce first gives both solutions. In[1]:= ReduceMinimize[objcons_List, vars_List] := Block[{obj, cons, redcons, minobj}, obj = objcons[[1]]; cons = Drop[objcons, 1]; redcons = Reduce[cons, vars]; minobj = MinValue[obj, redcons, vars]; {minobj, Reduce[obj == minobj && redcons, vars, Reals, Backsubstitution -> True]} ] In[6]:= Minimize[{x^2 - y^2, Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}] Out[6]= Minimize[{x^2 - y^2, Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}] In[7]:= ReduceMinimize[{x^2 - y^2, Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}] Out[7]= {1/ 9 (-150 \[Pi] + 25 \[Pi]^2), (x == -(5/3) (-3 + \[Pi]) && y == 5) \|\| (x == 5/3 (-3 + \[Pi]) && y == -5)}

Here's a situation where Minimize does not give a solution, but using Reduce first gives both solutions.

In[1]:= ReduceMinimize[objcons_List, vars_List] :=
 Block[{obj, cons, redcons, minobj},
  obj = objcons[[1]];
  cons = Drop[objcons, 1];
  redcons = Reduce[cons, vars];
  minobj = MinValue[obj, redcons, vars];
  {minobj, 
   Reduce[obj == minobj && redcons, vars, Reals, 
    Backsubstitution -> True]}
  ]

In[6]:= Minimize[{x^2 - y^2, 
  Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}]

Out[6]= Minimize[{x^2 - y^2, 
  Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}]

In[7]:= ReduceMinimize[{x^2 - y^2, 
  Cos[x - y] >= 1/2, -5 <= x <= 5, -5 <= y <= 5}, {x, y}]

Out[7]= {1/
  9 (-150 \[Pi] + 25 \[Pi]^2), (x == -(5/3) (-3 + \[Pi]) && 
    y == 5) || (x == 5/3 (-3 + \[Pi]) && y == -5)}

POSTED BY: Frank Kampas

Frank Kampas

Frank Kampas, Physicist at Large Consulting

Posted 6 years ago

That's a good point. Your observation caused me to try Reduce on the original solution, which gives the solution I got by my more complicated method. In[2]:= Reduce[{x1 -> 3 - x2 - x3, x2 -> 2 - x3 + x4, x3 -> 1/2 (-1 + x4 + 5 x5), x4 -> -1 + 3 x5, x5 -> 2/3, x6 -> 1/3} /. Rule :> Equal, {x1, x2, x3, x4, x5, x6}, Reals, Backsubstitution -> True] Out[2]= x1 == 0 && x2 == 4/3 && x3 == 5/3 && x4 == 1 && x5 == 2/3 && x6 == 1/3

That's a good point. Your observation caused me to try Reduce on the original solution, which gives the solution I got by my more complicated method.

In[2]:= Reduce[{x1 -> 3 - x2 - x3, x2 -> 2 - x3 + x4, 
   x3 -> 1/2 (-1 + x4 + 5 x5), x4 -> -1 + 3 x5, x5 -> 2/3, 
   x6 -> 1/3} /. Rule :> Equal, {x1, x2, x3, x4, x5, x6}, Reals, 
 Backsubstitution -> True]

Out[2]= x1 == 0 && x2 == 4/3 && x3 == 5/3 && x4 == 1 && x5 == 2/3 && 
 x6 == 1/3

POSTED BY: Frank Kampas

Michael Rogers

Michael Rogers, Emory University

Posted 6 years ago

I think the solutions satisfy the constaints (note the use of `ReplaceRepeated`): cons //. Last@sln (* {True, True, True, True, True, True, True, True, True, True, True, True, True, True} *) It's just that they're not in "backsubstitution" order.

POSTED BY: Michael Rogers

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback