Maximising a quadratic function over the integers

Question

What is the best way to solve the following optimization problem without blinding guessing values for $x,y$?

$$\begin{array}{ll} \text{maximize} & xy+(38-x)(32-y)\\ \text{subject to} & 1 \leq x, y \leq 37\\ & x, y \in \mathbb Z\end{array}$$

Usually I would try completing the square or using the AM-GM inequality, but both methods don't seem to work here. Help would be greatly appreciated. The question should be answered without using calculus.

Answer 1

Let us first relax the integrality constraints and optimize over the reals.

Note that the only 2nd order term in the objective function

$$f (x, y) := x y + (38-x)(32-y)$$

is the bilinear term $2 x y$. Hence, function $f$ is indefinite and, thus, the maximum should be attained at the boundary of the feasible region $[1,37] \times [1,37]$. Do note that the gradient of $f$ does vanish at $(x,y) = (19,16)$, which is in the interior of the feasible region $[1,37] \times [1,37]$, but that is a saddle point, not a maximum.

Evaluating $f$ on the line segment $\{ (x,1) \mid x \in [1,37] \}$, we obtain an affine function

$$f (x,1) = -30 x + 38 \cdot 31$$

Evaluating $f$ on the other $3$ line segments that form the boundary of $[1,37] \times [1,37]$, we also obtain affine functions. We then conclude that the maximum is attained at one of the $4$ vertices.

$$f (1,1) = 1148 \qquad\qquad f (1,37) = -148 \qquad\qquad f (37,1) = 68 \qquad\qquad \color{blue}{f (37,37) = 1364}$$

Thus, the maximum is $1364$, which is attained at $(x,y) = (37,37)$. Since this is a pair of integers, this is the solution over the integers, too.

Answer 2

I don't know of any methods beyond calculus to find the maximum of a function, but we can use calculas to show that this function doesn'thave a maximum:

First we need to calculate the partial derviatives of $$f(x,y)=xy+(38−x)(32−y)$$ which are:

\begin{align}\frac{\partial f}{\partial x}&=2(y-16)\\ \frac{\partial f}{\partial y} &=2(x-19)\end{align}

We find any stationary points by solving \begin{align}\frac{\partial f}{\partial x}&=0\\ 2(y-16)&=0\\ y&=16\\ \frac{\partial f}{\partial y} &=0\\ 2(x-19)&=0\\ x&=19\end{align}

So we can say that this function has one stationary point at $(19,16)$.

Now we need to classify this stationary point. To do this, we need to calculate the second derivatives of the function, which are:

\begin{align}\frac{\partial^2 f}{\partial x^2}&=\frac{\partial }{\partial x}(2(y-16))=0\\ \frac{\partial^2 f}{\partial y^2}&=\frac{\partial}{\partial y}(2(x-19))=0\\ \frac{\partial^2f}{\partial y\partial x}&=\frac{\partial }{\partial y}(2(y-16))=2\end{align}

Points are classified by first calculating

\begin{align}M=\frac{\partial^2 f}{\partial x^2}\times \frac{\partial^2 f}{\partial y^2} - \left(\frac{\partial^2f}{\partial y\partial x}\right)^2\end{align}

Then, if $M<0$ at $(a,b)$, then $(a,b)$ is a saddle point and if $M>0$ then $(a,b)$ is either a maximum or a minimum.

We have \begin{align}M&=\frac{\partial^2 f}{\partial x^2}\times \frac{\partial^2 f}{\partial y^2} - \left(\frac{\partial^2f}{\partial y\partial x}\right)^2\\ &=0\times 0-2^2\\ &=-4\end{align}

and therefore we can conclude that $(19,16)$ is a saddle point. As there was only one stationary point found, then we can conclude that this function does not have a maximum value. We can also see this if we plot the function.