9

I am trying to minimize the following function: \begin{align} &f(z_x,z_y)=|az_x-bz_y| \\ &\text{ s.t. } z_x,z_y \in \mathbb{Z},1 \le z_x \le N_x \text{ and } 1 \le z_y \le N_y \text{ and } a,b \in \mathbb{R}^{+}. \end{align}

There reason I find this problem difficult is that it involves several areas of mathematics: number theory (Diophantine equations), optimization with constrains.

{ Edit:} I know the following: if $a<N_y$ and $b<N_x$ then minimum is attained at $z_x= \lceil b \rfloor$ and $z_y= \lceil a \rfloor$. But there are other cases which I don't see how to solve.

{ The above is wrong. Can show a counter example}

I have been also pursuing a direction with continued fractions. So far unsuccessful.:(

Partial answer:

if $a \ge bN_y$ or $b \ge a N_x$ then minimum value is is $\min(a,b)$.

First bounty Tony was able to answer it for specific $a$ and $b$ and gave a general procedure how to do it.

Second bounty This is second bounty question. Can one find a minimum solution or a tight lower bound that is a function of $a,b, N_x,N_y$?

Boby
  • 5,985
  • If $N_x$ and $N_y$ are very large, the minimum is the gcd. – cactus314 Sep 03 '14 at 23:50
  • gcd of a and b?? – Boby Sep 04 '14 at 01:07
  • 1
    If $b/a$ is rational, and $N_x$ and $N_y$ sufficiently large, then the minimum is $0$. If not, then you want closest rational approximations of $b/a$. These are given by the continued fraction algorithm, which is also what you use if $b/a$ is rational, but $N_x$ and $N_y$ aren't sufficiently large. If $N_x$ or $N_y$ is chosen so that no convergents are in the allowable region, then you have to choose the closest point you can to one of those convergents, and the details of that are what I'm still thinking about. – G Tony Jacobs Sep 04 '14 at 12:49
  • What's the counterexample you mention? – G Tony Jacobs Sep 04 '14 at 12:50
  • Tony. By counter example. I meant that we can approximate $\frac{a}{b}$ as close as possible and hence solutions $z_x= \lceil b \rceil$ and $z_y= \lceil a \rceil$ are not optimal. – Boby Sep 04 '14 at 13:06
  • Tony I have also been trying to work with continued fractions. Unfortunately, my knowledge of continued fractions is rather limited. I am trying to learn though. Could you please post maybe some details on you approach so I can see what is the directions exactly. Thanks – Boby Sep 04 '14 at 13:31
  • Tony I have been able to solve it for a special case. An easy case. When the line formed by $|az_x-bz_y|$ is not in the box formed by $1 \le z_x \le N_x$ and $1 \le z_y \le N_y$. – Boby Sep 04 '14 at 16:10
  • I strongly recommend the book Continued Fractions by Khinchin. He goes into detail about how convergents are closest approximations, and it's very well-written and accessible. – G Tony Jacobs Sep 07 '14 at 15:36

1 Answers1

4

First of all, we can assume that $b=1$ without loss of generality. For, if we define $\overline{a}=\frac{a}{b}$, then minimizing $|\overline{a}z_x-z_y|$ is the same as minimizing $|az_x-bz_y|$.

Now, we're really looking for $\frac{z_y}{z_x}$ to be a rational number close to $a$. The convergents of the continued fraction expansion of $a$ are precisely the rational numbers $\frac{z_y}{z_x}$ that minimize $|az_x-z_y|$ for bounded $z_x$. If any of those are in the region $1\leq z_x\leq N_x$, $a\leq z_y\leq N_y$, simply choose the last one that is. For example, let $N_x=N_y=20$ and let $a=\sqrt{2}$, which has for its first few convergents, $\{\frac11, \frac32, \frac75, \frac{17}{12}, \frac{41}{29},\ldots\}$. We would choose $z_x=12, z_y=17$ to find our minimum.

This actually applies to rational numbers as well as irrational ones. In that example, we would obtain the same solution for, say, $a=\frac{41}{29}$.

The case remains where no convergents of $a$ are in the desired region. Now we can simply think about the geometry of this situation. We've got a line through the origin with a slope of $a$, and a rectangular region defined by our inequalites on $z_x$ and $z_y$. Convergents are simply lattice points closer to the line than any (first quadrant) lattice point to their left. Thus, any line that misses the region entirely will either have its closest approach to the point $(1,N_y)$ or the point $(N_x,1)$, depending on whether the line misses the region because $a>N_y$ or because $a<\frac{1}{N_x}$, respectively.

G Tony Jacobs
  • 31,218
  • Ok. Thank you I will take a look at that book. – Boby Sep 07 '14 at 18:59
  • Does this answer the question to your satisfaction, or should it be further clarified? – G Tony Jacobs Sep 09 '14 at 02:12
  • Thanks it was clear. Do you think it is possible to have a close form solution in terms of $a,b,N_x,N_y$.? – Boby Sep 09 '14 at 13:10
  • 1
    Tricky. I guess you could write $z_y=p_n, z_x=q_n$, where $n$ is chosen maximal so that, for $\frac{p_n}{q_n}$ the $n$-th convergent of $\frac{a}{b}$, we have $p_n<N_y$ and $q_n<N_x$. That's not exactly closed form. There might be a nicer way of expressing the numbers $p_n$ and $q_n$ in terms of $\frac{a}{b}$, using the Gauss map or something, but you'll still have to take some sort of maximum to choose $n$. – G Tony Jacobs Sep 09 '14 at 14:14