Nonlinear integer programming problem

85 Views Asked by At

I am trying to maximize the following function

$$ f(m,n) = \frac{m \log 3 + n \log 2}{\sqrt{m^2+n^2}} $$ where $ n $ and $ m $ are integers, not both $ = 0 $, although one could be $ 0 $.

This is not for a class- it's part of a research problem, and this is a "toy" case. I don't have any background in integer programming, especially nonlinear.

I'm hoping for an proof, that doesn't involve writing a computer program to solve it, if possible.

1

There are 1 best solutions below

0
On

Let $a=\log3/\log2$. The problem is equivalent to maximize $$ g(m,n)=\frac{m\,a+n}{\sqrt{m^2+n^2}}. $$From the inequality $$ a\,m+n\le\sqrt{a^2+1}\,\sqrt{m^2+n^2} $$ it follows that $g(m,n)\le\sqrt{a^2+1}$. If there exist an integer $n$ such that $m=n\,a$ is also an integer, then $g(m,n)=\sqrt{a^2+1}$, and this is the maximum value. This works if $a$ is rational. If $a$ is irrational the maximun value is never attained. However it is possible to get as close to it as desired. Let $p_k$, $q_k$ be positive integers, relatively prime, such that $p_k/q_k$ approaches $a$ as $k\to\infty$. Let $r_k=p_k-q_k\,a$. Then $$\begin{align} g(p_k,q_k)&=\frac{p_k\,a+q_k}{\sqrt{p_k^2+q_k^2}}\\ &=\frac{a^2+1}{\sqrt{\Bigl(a+\dfrac{r_k}{q_k}\Bigr)^2+1}}+\frac{r_k}{\sqrt{p_k^2+q_k^2}} \end{align}$$ and $r_k/q_k=p_k/q_k-a$ goes to $0$ as $k\to\infty$.