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$
2
  • $\begingroup$ What about the other parameters ? Do they have a numeric value ? $\endgroup$ Commented Sep 13, 2013 at 8:23
  • $\begingroup$ @b.gatessucks All the parameters are -1 or 1. $\endgroup$ Commented Sep 13, 2013 at 8:25

4 Answers 4

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$
5
  • $\begingroup$ Nice! But how to find the values of $a,b,c,\cdots,m$ for the maximal value? $\endgroup$ Commented Sep 13, 2013 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
    Commented Sep 13, 2013 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
    Commented Sep 13, 2013 at 8:57
  • $\begingroup$ Is it possible to find the maximum and the corresponding points at the same time? $\endgroup$ Commented Sep 13, 2013 at 9:08
  • $\begingroup$ @EdenHarder Yes, of course, let me update my answer. $\endgroup$
    – Artes
    Commented Sep 13, 2013 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$
2
  • $\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$ Commented Sep 13, 2013 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
    Commented Sep 13, 2013 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$
2
  • $\begingroup$ Thanks! why the code is '-1 == a || 1 == a' instead of 'a == -1 || a == 1'? $\endgroup$ Commented Sep 13, 2013 at 9:03
  • $\begingroup$ No reason at all. $\endgroup$ Commented Sep 13, 2013 at 9:05

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.