10
$\begingroup$

I am trying to reconstruct the answer that is given in this report. (page 153 in Appendix B; Section B.2.1). They are given variables, parameters, constraints, and the objective function to minimize.

Summary of the problem:

Minimize: q01 + q11 + q21 + q31 - q02 - q12 - q22 - q32
Variables: {q00 , q01 , q02 , q03 , q10 , q11 , q12 , q13 , 
            q20 , q21 , q22 , q23 , q30, q31 , q32 , q33}
Parameters: {p000 , p010 , p100 , p110 , p001 , p011 , p101 , p111}
Constraints: 
  1) all q's nonnegative
  2) [sum all q's] == 1
  3) p000 == q00 + q01 + q10 + q11
  4) p010 == q20 + q22 + q30 + q32
  5) p100 == q02 + q03 + q12 + q13
  6) p110 == q21 + q23 + q31 + q33
  7) p001 == q00 + q01 + q20 + q21
  8) p011 == q10 + q12 + q30 + q32
  9) p101 == q02 + q03 + q22 + q23
  10) p111 == q11 + q13 + q31 + q33

Their output is given on page 155 as the maximum of a set of eight linear functions of the parameters:

 Minimum of Objective Function is the Maximum of:
 p111 + p000 - 1
 p110 + p001 - 1
 -p011 - p101
 -p010 - p100
 p110 - p111 - p101 - p010 - p100
 p111 - p110 - p100 - p011 - p101
 p001 - p011 - p101 - p010 - p000
 p000 - p010 - p100 - p011 - p001

When trying to reproduce it in Mathematica 8.0, first tried simple test case of using parameters

LinearProgramming[{1, 1}, {{1, 2}}, {a}]

which gave an error, but using Minimize does give a full answer

Minimize[x + y, x + 2*y >= a && x >= 0 && y >= 0, {x, y}]

I then rephrased the original problem in terms of Minimize function and even after running overnight it was still thinking:

Minimize[q01 + q11 + q21 + q31 - q02 - q12 - q22 - q32, 
  q00 + q01 + q02 + q03 + q10 + q11 + q12 + q13 + q20 + q21 + q22 + 
    q23 + q30 + q31 + q32 + q33 == 1 && 
  q00 >= 0 && q01 >= 0 && 
  q02 >= 0 && q03 >= 0 && q10 >= 0 && q11 >= 0 && q12 >= 0 && 
  q13 >= 0 && q20 >= 0 && q21 >= 0 && q22 >= 0 && q23 >= 0 && 
  q30 >= 0 && q31 >= 0 && q32 >= 0 && q33 >= 0 && 
  p000 == q00 + q01 + q10 + q11 && p010 == q20 + q22 + q30 + q32 && 
  p100 == q02 + q03 + q12 + q13 && p110 == q21 + q23 + q31 + q33 && 
  p001 == q00 + q01 + q20 + q21 && p011 == q10 + q12 + q30 + q32 && 
  p101 == q02 + q03 + q22 + q23 && 
  p111 == q11 + q13 + q31 + q33, {q00, q01, q02, q03, q10, q11, q12, 
  q13, q20, q21, q22, q23, q30, q31, q32, q33}]

Is there a way for Mathematica (8.0) to reproduce their results? Have a feeling I'm either missing a function that would answer it, or not inputting some restriction or assumption which Mathematica needs. Thank you!

EDIT

I tried the suggestion of @Anon:

Minimize[{f, constraints}, {q00, q02, ...}] 

instead of

Minimize[f, constraints, {q00, q01, ...}]

hoping that was the answer. It still was thinking overnight, with no answer produced. Is Minimize the correct function to use for this problem?

(Originally posted in StackOverflow, first response recommended posting the question here)

$\endgroup$
9
  • 1
    $\begingroup$ The syntax is Minimize[{f,constraints},{q00,q02...}] and it looks like you wrote Minimize[f,constraint,{q00,q01...}]. $\endgroup$
    – C. E.
    Jul 28, 2013 at 14:59
  • $\begingroup$ @Anon Thanks for the correction. However, when I tried that procedure it still did not produce an answer, even after thinking overnight. $\endgroup$
    – sheppa28
    Jul 29, 2013 at 11:40
  • $\begingroup$ I'm not much good with these things but I'd like to help if I can. Could you provide an example smaller than the main one but larger than Minimize[x + y, x + 2*y >= a && x >= 0 && y >= 0, {x, y}] that can be solved by Minimize? $\endgroup$
    – Mr.Wizard
    Jul 29, 2013 at 11:55
  • $\begingroup$ @sheppa28 If one removes all constraints but the first, q00 + q01 + q02 + q03 + q10 + q11 + q12 + q13 + q20 + q21 + q22 + q23 + q30 + q31 + q32 + q33 == 1, Minimize quickly returns "The minimum is not attained at any point satisfying the given constraints." Piling on more constraints isn't helping I suppose, maybe it's taking so long because there are lots of combinations to try and no correct answer. (IDK any about this, I just put this to you for consideration.) $\endgroup$
    – C. E.
    Jul 29, 2013 at 13:10
  • $\begingroup$ Note the problem is not solvable for "arbitrary" parameters, for one thing all p must obviously be > 0. Its likely getting bogged down generating massive lists of conditional results for different p cases. Adding all pxx>=0 to the system might help.. $\endgroup$
    – george2079
    Jul 30, 2013 at 19:54

2 Answers 2

2
$\begingroup$

LinearProgramming will work but you need the values for the parameters as it is not a symbolic algorithm.

Constructing the parameters for LinearProgramming will give:

c = Flatten@{{1, 0, -1, 0}, {0, 1, -1, 0}, {0, 1, -1, 0}, {0, 1, -1, 0}};

This corresponds to the minimisation problem. I use the matrix form and then flatten to assist with translating. The left-hand side of the constraints in the same order as you have present will give:

m =
  {
   ConstantArray[1, 16],
   Flatten@{{1, 1, 0, 0}, {1, 1, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}},
   Flatten@{{0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {1, 0, 1, 0}},
   Flatten@{{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}},
   Flatten@{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 1, 0, 1}, {0, 1, 0, 1}},
   Flatten@{{1, 1, 0, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}},
   Flatten@{{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}},
   Flatten@{{0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 1, 1}, {0, 0, 0, 0}},
   Flatten@{{0, 0, 0, 0}, {0, 1, 0, 1}, {0, 0, 0, 0}, {0, 1, 0, 1}}
  };

The right-hand side of the constraints is where you need values for the algorithm to compute. I've chosen some values that will work for all but the first constraint. I hand to change the first constraint from == 1 to >= 1 to demonstrate that it works. You need the actual values from the constraints to get the intended result since LinearProgramming is not a symbolic algorithm.

p000 = 0.9; p010 = 0.8; p100 = 0.7; p110 = 0.6; 
p001 = 0.5; p011 = 0.6; p101 = 0.8; p111 = 0.9;
b = {{1, 1}, {p000, 0}, {p010, 0}, {p100, 0}, {p110, 0}, 
     {p001, 0}, {p011, 0}, {p101, 0}, {p111, 0}};

This will solve but as I don't have the actual values to the parameters and had to change the first constraint from == to >= the result vector sums to 3 instead of 1.

LinearProgramming[c, m, b]
(* {0., 0.3, 0.7, 0., 0., 0.6, 0., 0., 0.2, 0.2, 0., 0.1, 0., 0., 0.6, 0.3} *)
Total[%]
(* 3 *)

This returns immediately; no overnight wait. I suspect that if you get the actual parameter values (and change the first constraint back to == by changing the {1,1} to {1,0} in b) that it would solve equally as fast.

Hope this helps

$\endgroup$
1
$\begingroup$

Removing the >= 0 constrains solves the problem

q00 >= 0 && q01 >= 0 && 
q02 >= 0 && q03 >= 0 && q10 >= 0 && q11 >= 0 && q12 >= 0 && 
q13 >= 0 && q20 >= 0 && q21 >= 0 && q22 >= 0 && q23 >= 0 && 
q30 >= 0 && q31 >= 0 && q32 >= 0 && q33 >= 0 && 

-

Minimize[{q01 + q11 + q21 + q31 - q02 - q12 - q22 - q32,

  q00 + q01 + q02 + q03 + q10 + q11 + q12 + q13 + q20 + q21 + q22 + 
     q23 + q30 + q31 + q32 + q33 == 1 &&
   p000 - q00 - q01 - q10 - q11 == 0 &&
   p010 - q20 - q22 - q30 - q32 == 0 &&
   p100 - q02 - q03 - q12 - q13 == 0 &&
   p110 - q21 - q23 - q31 - q33 == 0 &&
   p001 - q00 - q01 - q20 - q21 == 0 &&
   p011 - q10 - q12 - q30 - q32 == 0 &&
   p101 - q02 - q03 - q22 - q23 == 0 &&
   p111 - q11 - q13 - q31 - q33 == 0
  },
 {q00, q01, q02, q03, q10, q11, q12, q13, q20, q21, q22, q23, q30, q31, q32, q33}] 

results in

enter image description here

$\endgroup$
1
  • $\begingroup$ Removing the >= constraints does solve the run-time problem, but the answers do not match. Is there a way to reconstruct their answer? (Given above in original question under "Minimum of Objective Function is the Maximum of:") On a side note, when all the p's are specified numerically Mathematica does give the correct numerical answer, along with what the q's equal. I am trying to reproduce the parametric solution given in the original paper. $\endgroup$
    – sheppa28
    Jul 29, 2013 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.