# Maximization of a function over a discrete set

I have a function of three variables: $f = f(x, y, z)$. I need to maximize $f$, when $x$, $y$ and $z$ run given sets of values: $x \in (x_1, x_2, x_3)$, $y \in (y_1, y_2, y_3)$ and $z \in (z_1, z_2, z_3)$, as well as find the maximizers. I tried to define the set

setx = {x1, x2, x3};
sety = {y1, y2, y3};
setz = {z1, z2, z3};


and use

NMaximize[{f[x, y, z], x\[Element] setx, y\[Element] sety, z\[Element] setz}, {x, y, z}]


but it does not work.

Any idea is appreciated.

This?

Last[SortBy[Map[{f@@#, #}&, Tuples[{setx, sety, setz}]], First]]


The Tuples will give you all combinations, the anonymous function will construct the function value and arguments and the Last and SortBy will extract the desired maximal function value and arguments

• It works! Thanks a lot. – Asatur Khurshudyan Jan 29 '18 at 8:25
• MaximalBy[Tuples[{setx, sety, setz}], f @@ # &] seems more direct. One should warn that the Tuples approach would use a lot of memory on large sets. – Michael E2 Jan 29 '18 at 12:49

One way to use your original idea with the constraints:

(* Test function *)
f[vars_] := vars[[1]]^2 + vars[[2]]^2 - vars[[3]]^3

(* Test data *)
n = 3;
vars = Unique["x"] & /@ Range[n];

SeedRandom[123]
setx = RandomVariate[NormalDistribution[1.2, 3.4], n];
sety = RandomVariate[NormalDistribution[-1.2, 3.4], n];
setz = RandomVariate[NormalDistribution[0., 3.4], n];

conditions = And @@ ((Or @@ Thread[Equal[#[[1]], #[[2]]]]) & /@
Transpose[{vars, {setx, sety, setz}}]);

NMaximize[{f[vars], conditions}, vars, Reals]
(* {275.963, {x13 -> 5.42127, x14 -> -7.24214, x15 -> -5.79019}} *)


Check:

Last[SortBy[Map[{f[#], #} &, Tuples[{setx, sety, setz}]], First]]
(* {275.963, {5.42127, -7.24214, -5.79019}} *)

• Thanks! This also works well. – Asatur Khurshudyan Jan 30 '18 at 7:07

For a problem with no extra assumptions or structure, an exhaustive search is probably best. A Tuples based search has a memory complexity of $O(n_1n_2n_3\cdots)$ (or $O(n^k)$ if the $k$ sets are of about the same size $n$). A procedural-programming approach both is time-efficient and uses little memory; it is slightly faster than @Bill's on @b.gatessucks' example. Here is the basic idea:

Do[
val = f[x, y, z];
If[val > max,     (* see below for initialization of max *)
max = val; args = {x, y, z}],
{x, setx}, {y, sety}, {z, setz}]


Vectorizing the inner loop, if the function f supports it, is much faster than the above, especially as the size n of the sets grows:

max = -Infinity;
Do[
vals = f[x, y, setz];  (* f must be listable *)
val = Max@vals;
If[val > max,
max = val;
args = {x, y, First@Pick[setz, vals, max]}],
{x, setx}, {y, sety}];
{max, args}


If f is compilable and listable, then compiling this speeds things up a little bit more on @b.gatessucks' example.

The following gives some idea of what is possible:

Fig. 1. The time of execution for three sets of size 3, 6,... 768. Note the uncompiled, vectorized Do loop is quite fast, with a time complexity that appears to be somewhat less than $O(n^3)$, unlike the others. It ought to be $O(n^2(1+\epsilon\,n))$, but I suppose $\epsilon\,n$ is still rather less than $1$ in the plot.

The MaximalBy code is from my comment. The basis for the compiled and uncompiled procedural code is the first Do loop above; the second Do is the basis for the "vectorized" version. When compiled, one can make it Listable and parallelized on one of the arguments; that's the fastest way I have.

I've been playing with it, obviously, trying to create an interface that automatically chooses the optimal method (and when not automatic, controlled by options). But I'm not done. It's hardly relevant to the question at hand, unless speed on moderately sized sets is important to the OP. I don't mind sharing the code, but I'm not sure it would be of broad interest.