Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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)

share|improve this question
1  
The syntax is Minimize[{f,constraints},{q00,q02...}] and it looks like you wrote Minimize[f,constraint,{q00,q01...}]. –  Pickett Jul 28 '13 at 14:59
    
@Anon Thanks for the correction. However, when I tried that procedure it still did not produce an answer, even after thinking overnight. –  sheppa28 Jul 29 '13 at 11:40
    
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? –  Mr.Wizard Jul 29 '13 at 11:55
    
@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.) –  Pickett Jul 29 '13 at 13:10
    
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.. –  george2079 Jul 30 '13 at 19:54

1 Answer 1

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

share|improve this answer
    
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. –  sheppa28 Jul 29 '13 at 16:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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