3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
2
$\begingroup$

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.

|improve this answer|||||
$\endgroup$

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.