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)
Minimize[{f,constraints},{q00,q02...}]
and it looks like you wroteMinimize[f,constraint,{q00,q01...}]
. $\endgroup$Minimize[x + y, x + 2*y >= a && x >= 0 && y >= 0, {x, y}]
that can be solved byMinimize
? $\endgroup$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$