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.

How to find the maximum of a function on a set of discrete points? For example, what is the best way to find the maximum of

-2 a - 2 b - 2 c - 2 d - 2 e - 2 f + e (-2 + d + f) - 2 g + f (-2 + a + e + g) - 
 2 h + c (-2 + b + d + h) - 2 i - 2 j + a (-2 + b + f + j) + i (-2 + h + j) + 
 h (-2 + c + g + i + j) - 2 k + d (-2 + c + e + k) + j (-2 + a + h + i + k) - 
 2 l + g (-2 + f + h + l) + k (-2 + d + j + l) - 2 m + (-2 + b + l) m + l 
 (-2 + b + g + k + m) + b (-2 + a + c + l + m)

where $a,b,c,d,e,f,g,h,i,j,k,l, m \in \{-1,1\}$? Any help or suggestion will be appreciated!

share|improve this question
    
What about the other parameters ? Do they have a numeric value ? –  b.gatessucks Sep 13 '13 at 8:23
    
@b.gatessucks All the parameters are -1 or 1. –  Eden Harder Sep 13 '13 at 8:25

4 Answers 4

up vote 5 down vote accepted

Since the expression is slightly involved I'd put it in Table and write its all values for {a, {-1, 1}}, {b, {-1, 1}},..., {m, {-1, 1}}

It can be done this way

With[{iter = 
      Sequence @@ Table[{var, {-1, 1}}, 
                        {var, {a, b, c, d, e, f, g, h, i, j, k, l, m}}]}, 
     With[{tab = 
           Table[{ -2 a - 2 b - 2 c - 2 d - 2 e - 2 f + e (-2 + d + f) - 2 g 
                   + f (-2 + a + e + g) - 2 h + c (-2 + b + d + h) - 2 i - 2 j 
                   + a (-2 + b + f + j) + i (-2 + h + j) + h (-2 + c + g + i + j) 
                   - 2 k + d (-2 + c + e + k) + j (-2 + a + h + i + k) - 2 l 
                   + g (-2 + f + h + l) + k (-2 + d + j + l) - 2 m + (-2 + b + l) m 
                   + l (-2 + b + g + k + m) + b (-2 + a + c + l + m), 
                  {a, b, c, d, e, f, g, h, i, j, k, l, m}}, iter]}, 

           Cases[tab, {tab // Max, {___}}, Infinity]
         ]
    ]
{{92, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}}}

In more general cases you should consider writing your expression as a pure function and work with e.g. Inner, Outer, Tuples. What might be the best approach depends on various issues, like e.g. the size of the underlying parameter space, etc..

share|improve this answer
    
Nice! But how to find the values of $a,b,c,\cdots,m$ for the maximal value? –  Eden Harder Sep 13 '13 at 8:45
    
Cases[With[{w = Sequence @@ Table[{z, {-1, 1}}, {z, {a, b, c, d, e, f, g, h, i, j, k, l, m}}]}, Table[{-2 a - 2 b - 2 c - 2 d - 2 e - 2 f + e (-2 + d + f) - 2 g + f (-2 + a + e + g) - 2 h + c (-2 + b + d + h) - 2 i - 2 j + a (-2 + b + f + j) + i (-2 + h + j) + h (-2 + c + g + i + j) - 2 k + d (-2 + c + e + k) + j (-2 + a + h + i + k) - 2 l + g (-2 + f + h + l) + k (-2 + d + j + l) - 2 m + (-2 + b + l) m + l (-2 + b + g + k + m) + b (-2 + a + c + l + m), {a, b, c, d, e, f, g, h, i, j, k, l, m}}, w]], {92, {___}}, Infinity] –  Artes Sep 13 '13 at 8:55
2  
Yields {{92, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}}}. But that was another question ! –  Artes Sep 13 '13 at 8:57
    
Is it possible to find the maximum and the corresponding points at the same time? –  Eden Harder Sep 13 '13 at 9:08
    
@EdenHarder Yes, of course, let me update my answer. –  Artes Sep 13 '13 at 9:10

One can take advantage of the Listable properties of Plus and Times. One can just feed the lists of input values into each of a, b, etc. Tuples yields all possible combinations of {1, -1} and Transpose collects all the inputs for a, b, etc. respectively into lists to feed into the function fn:

expr = -2 a - 2 b - 2 c - 2 d - 2 e - 2 f + e (-2 + d + f) - 2 g + 
   f (-2 + a + e + g) - 2 h + c (-2 + b + d + h) - 2 i - 2 j + 
   a (-2 + b + f + j) + i (-2 + h + j) + h (-2 + c + g + i + j) - 
   2 k + d (-2 + c + e + k) + j (-2 + a + h + i + k) - 2 l + 
   g (-2 + f + h + l) + k (-2 + d + j + l) - 2 m + (-2 + b + l) m + 
   l (-2 + b + g + k + m) + b (-2 + a + c + l + m);

fn = Function @@ {Variables@expr, expr}  (* Variables will put them in alpha. order *)
fn @@ Transpose@Tuples[{1, -1}, 13] // Max 
(* 92 *)

You can use Pick as does @Verbeia to select the input(s) that gives the maximum.

values = fn @@ Transpose[tuples = Tuples[{1, -1}, 13]];
Pick[tuples, values, Max@values]
(* {{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}} *)

Or to get the maximum and input at the same time:

values = fn @@ Transpose[tuples = Tuples[{1, -1}, 13]];
With[{max = Max@values},
  {max, Pick[tuples, values, max]}
]
(* {92, {{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}}} *)
share|improve this answer
    
Thanks very much! Will this code be better in speed? And can we find the maximum and the corresponding points at the same time? –  Eden Harder Sep 13 '13 at 13:25
    
This code should be about the fastest way to find the maximum of all the values. A particular function might have a special form that allows for a faster algorithm to be applied. It's quite easy to get the max. and points at the same time. See the update –  Michael E2 Sep 13 '13 at 15:57

Because your set of discrete points is very long (13 variables each with two possible values = $2^{13}$ = 8192, I will demonstrate an approach with a simpler case.

First, you can get your values using Tuples:

tups = Tuples[{-1, 1}, 3]

{{-1, -1, -1}, {-1, -1, 1}, {-1, 1, -1}, {-1, 1, 1}, {1, -1, -1}, {1, -1, 1}, {1, 1, -1}, {1, 1, 1}}

If you recast your problem as a pure function, you can then apply that function to each case like this:

values= #1 + #2 + #3 & @@@ tups

{-3, -1, -1, 1, -1, 1, 1, 3}

You can then use Pick to select the combination of parameters that generates the maximum value:

Pick[tups, values, Max[values]]

{{1, 1, 1}}

share|improve this answer

This will probably not work for much bigger problems :

Maximize[{-2 a - 2 b - 2 c - 2 d - 2 e - 2 f + e (-2 + d + f) - 2 g + 
          f (-2 + a + e + g) - 2 h + c (-2 + b + d + h) - 2 i - 2 j + 
          a (-2 + b + f + j) + i (-2 + h + j) + h (-2 + c + g + i + j) - 
          2 k + d (-2 + c + e + k) + j (-2 + a + h + i + k) - 2 l + 
          g (-2 + f + h + l) + k (-2 + d + j + l) - 2 m + (-2 + b + l) m + l
          (-2 + b + g + k + m) + b (-2 + a + c + l + m), -1 == a || 
          1 == a, -1 == b || 1 == b, -1 == c || 1 == c, -1 == d || 
          1 == d, -1 == e || 1 == e, -1 == f || 1 == f, -1 == g || 
          1 == g, -1 == h || 1 == h, -1 == i || 1 == i, -1 == j || 
          1 == j, -1 == k || 1 == k, -1 == l || 1 == l, -1 == m || 
          1 == m}, 
       {a, b, c, d, e, f, g, h, i, j, k, l, m}, Integers]
(* {92, {a -> -1, b -> -1, c -> -1, d -> -1, e -> -1, f -> -1, g -> -1, 
    h -> -1, i -> -1, j -> -1, k -> -1, l -> -1, m -> -1}} *)
share|improve this answer
    
Thanks! why the code is '-1 == a || 1 == a' instead of 'a == -1 || a == 1'? –  Eden Harder Sep 13 '13 at 9:03
    
No reason at all. –  b.gatessucks Sep 13 '13 at 9:05

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.