4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ What about the other parameters ? Do they have a numeric value ? $\endgroup$ – b.gates.you.know.what Sep 13 '13 at 8:23
  • $\begingroup$ @b.gatessucks All the parameters are -1 or 1. $\endgroup$ – Eden Harder Sep 13 '13 at 8:25
5
$\begingroup$

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..

$\endgroup$
  • $\begingroup$ Nice! But how to find the values of $a,b,c,\cdots,m$ for the maximal value? $\endgroup$ – Eden Harder Sep 13 '13 at 8:45
  • $\begingroup$ 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] $\endgroup$ – Artes Sep 13 '13 at 8:55
  • 2
    $\begingroup$ Yields {{92, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}}}. But that was another question ! $\endgroup$ – Artes Sep 13 '13 at 8:57
  • $\begingroup$ Is it possible to find the maximum and the corresponding points at the same time? $\endgroup$ – Eden Harder Sep 13 '13 at 9:08
  • $\begingroup$ @EdenHarder Yes, of course, let me update my answer. $\endgroup$ – Artes Sep 13 '13 at 9:10
3
$\begingroup$

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}}} *)
$\endgroup$
  • $\begingroup$ Thanks very much! Will this code be better in speed? And can we find the maximum and the corresponding points at the same time? $\endgroup$ – Eden Harder Sep 13 '13 at 13:25
  • $\begingroup$ 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 $\endgroup$ – Michael E2 Sep 13 '13 at 15:57
2
$\begingroup$

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}}

$\endgroup$
1
$\begingroup$

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}} *)
$\endgroup$
  • $\begingroup$ Thanks! why the code is '-1 == a || 1 == a' instead of 'a == -1 || a == 1'? $\endgroup$ – Eden Harder Sep 13 '13 at 9:03
  • $\begingroup$ No reason at all. $\endgroup$ – b.gates.you.know.what Sep 13 '13 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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