Minimise discrete function

Question

Let $f\,\colon\,\Lambda\to\mathbb R$ be a real-valued function, where $\Lambda$ is a finite integer lattice. Say, $\Lambda=\mathbb Z_3^n=\{\vec x\,\mid\, x_i=0,1,2\}$ for some $n\in\mathbb N$. I'd like to compute $$ \operatorname*{arg\, min}_{\vec x\in\Lambda} |f(\vec x)| $$

A possibility is to brute-force through all lattice points,

MinimalBy[Λ, Abs@*f]          (* untested but hopefully you get the idea *)

but this becomes way too slow for large $|\Lambda|=3^n$ (and I run out of memory). For this reason, I would settle for a local minimum. In other words, given some initial point $\vec x_0\in\Lambda$, I'd like to compute the minimum of $f(\vec x)$ as $\vec x$ takes values around $\vec x_0$. If $\vec x$ were to take continuous values, I'd use a gradient descent approach, but I don't know how to use something similar in the discrete case. What is the most efficient way to do this?

For the sake of definiteness, let $n=3$:

Λ = Table[{x1, x2, x3}, {x1, 0, 2}, {x2, 0, 2}, {x3, 0, 2}];
f = Sqrt[2] #1 + Sqrt[3] #2 + Sqrt[5] #3 - 1;

In a more realistic case, $n\sim 50$ and f has the same form as above (linear in $\vec x$, with algebraic coefficients, with a constant inhomogeneous term at the end). Evaluating f is fast, but Λ is way too large. How can I find a local minimum of $|f(\vec x)|$ without running out of memory and in a reasonable amount of time?

Answer 1

You could use Minimize:

Minimize[
    {
    Abs[Sqrt[2] x1 + Sqrt[3] x2 + Sqrt[5] x3 - 1],
    0<=x1<=2 && 0<=x2<=2 && 0<=x3<=2
    },
    {x1, x2, x3},
    Integers
]

{-1 + Sqrt[2], {x1 -> 1, x2 -> 0, x3 -> 0}}

Another alternative is to use LinearProgramming:

LinearProgramming[
    N @ {Sqrt[2], Sqrt[3], Sqrt[5], -1},
    {
    N @ {Sqrt[2], Sqrt[3], Sqrt[5], -1}
    },
    {0},
    {{0,2},{0,2},{0,2},{1,1}},
    Integers
]

{1, 0, 0, 1}

I augment the desired vector to be minimized ($x$) with a scalar. Then, the LinearProgramming call minimizes the vector $x$ such that {Sqrt[2], Sqrt[3], Sqrt[5], -1} . x is minimized, with the constraint that {Sqrt[2], Sqrt[3], Sqrt[5], -1} . x is greater than 0. Finally I constrain the augmented scalar to be 1, and the other variables to be between 0 and 2, in the Integers domain.

The above approach finds the minimimum for f>0, which in this case is Sqrt[2] - 1. For f<0 use:

LinearProgramming[
    -N @ {Sqrt[2], Sqrt[3], Sqrt[5], -1},
    {
    -N @ {Sqrt[2], Sqrt[3], Sqrt[5], -1}
    },
    {0},
    {{0,2}, {0,2}, {0,2}, {1,1}},
    Integers
]

{0, 0, 0, 1}

and in this case the minimum is $\left| -1 \right| = 1$. So, the answer again is Sqrt[2]-1 in agreement with the answer using Minimize.

Answer 2

I'm not sure this will help in the general case, but for the simplified one you can use Reduce (or FindInstance)

f[x1_, x2_, x3_] := Abs[Sqrt[2] x1 + Sqrt[3] x2 + Sqrt[5] x3 - 1];  

Reduce[f[x1, x2, x3] < 1 && 0 <= x1 <= 3 && 0 <= x2 <= 3 && 
                 0 <= x3 <= 3, {x1, x2, x3}, Integers]

(x1 == 0 && x2 == 1 && x3 == 0) || (x1 == 1 && x2 == 0 && x3 == 0)

Now you only need to pick from the two possibilities.