0

I'm an engineer with not-so-strong mathematics skills.

My apologies if my title is misleading, as I am unsure how to properly categorize this issue.

I came across a practical problem at work, described as follows:

$a$, $b$, and $c$ are nonnegative integers that satisfy the following conditions:

$0 \leq a \leq 1$,

$0 \leq b \leq 51$,

$0 \leq c \leq 40$,

with $a + b + c = 10$.

The task is to find the minimum value of the function

$f(a, b, c) = (a - \frac{10}{3})^2 + (b - \frac{10}{3})^2 + (c - \frac{10}{3})^2$,

as well as the corresponding values of $a$, $b$, and $c$.

Based on my basic mathematical knowledge, I solved this problem on a case-by-case basis, assuming $a = 0$ and $a = 1$ respectively.

(step1) When $a = 0$, the function becomes $(0 - \frac{10}{3})^2 + (b - \frac{10}{3})^2 + ((10 - b) - \frac{10}{3}) ^2$, which easily gives the minimum value when $b = 5$.

(step2) When $a = 1$, using the same approach we find that the optimal value for $b$ occurs at $b = 4.5$, that is, choosing either $b = 4$ or $b = 5$ brings us close enough to the optimal solution.

(step final) Comparing the function values in the two cases, we find that the optimal solution occurs when $a = 1$, $b= 4$, and $c = 5$.

My question is, my approach was to exhaustively reduce the problem to one dimension and solve it.

I wonder if there is a better way to do this?

I have this doubt because in practice, the upper bound for $a$ is often more than just 1, it could be a larger number. I don't want to always resort to the brute-force method when I come across such problems. I hope someone kind could tell me some methods or keywords.

update_1

I apologize for not being clear before. In practical situations, the upper bounds for $a$, $b$, and $c$ vary depending on the circumstances, while the lower bounds are always $0$.

After several calculations, I found that due to the nature of the function, without boundaries, the minimum value in real numbers would be $(a, b, c) = (\frac{10}{3}, \frac{10}{3}, \frac{10}{3})$.

When boundaries are added, for example, in the previous case, I simply choose the value as close as possible to the solution (among the choices of $0$ or $1$ for $a$, $1$ is closer to $\frac{10}{3}$), and this will yield the optimal solution.

In other situations, for example,

$0 \leq a \leq 2$,

$0 \leq b \leq 3$,

$0 \leq c \leq 60$,

the optimal solution should occur at $(a, b, c) = (2, 3, 5)$, because $a$ and $b$ should be as close to $\frac{10}{3}$ as possible, just like choosing the optimal point in linear programming.

Is my observation correct? And why does this happen?

yamiew
  • 13
  • I believe you can try brute-force. Note, that $a+b+c=10$ requires all non-negative $a$, $b$, $c$ to be less or equal 10 – Ivan Kaznacheyeu Jun 08 '23 at 07:29
  • ... for a = 0 to 1 do {for b=0 to 10-a do {c=10-a-b; ... }} – Ivan Kaznacheyeu Jun 08 '23 at 07:33
  • @IvanKaznacheyeu thanks for replying, i know it's 100% correct if i compute every result out and compare these values. But i also want to offer best performance in my code, so I try to think in math to solve the problem. – yamiew Jun 08 '23 at 08:10
  • So you need general solution of the following problem: $f=(a-a_1)^2+(b-b_1)^2+(c-c_1)^2$, find non-negative integers $a$, $b$, $c$ such that $a+b+c=A$, $a\leq a_2$, $b\leq b_2$, $c\leq c_2$ and $f$ to have minimum possible value? – Ivan Kaznacheyeu Jun 08 '23 at 09:24
  • As for last question in update 1. We still need to take into account third dimension. For example, let $a\leq 2,b\leq 4,c\leq 10$. Then minimum point is not $(2,3,5)$ but $(2,4,4)$ where $b$ is farther from $10/3$ than in $(2,3,5)$. – Ivan Kaznacheyeu Jun 08 '23 at 09:36
  • @IvanKaznacheyeu Your example is very clear and easy to understand, but it has left me more confused. Do we still have to use brute force to deal with this kind of problem?

    Also, I apologize for the incorrect general form earlier.

    My general case should be $f = (a - \frac{U}{3})^2 + (b - \frac{U}{3})^2 + (c - \frac{U}{3})^2$. The goal is to find non-negative integers $a$, $b$, and $c$ such that $a+b+c=U$, where $U$ is a positive integer, and $0 \leq a \leq a_2$, $0 \leq b \leq b_2$, $0 \leq c \leq c_2$. The aim is to determine $a$, $b$, and $c$ that would minimize the value of $f$.

     – yamiew Jun 08 '23 at 09:48
  • https://i.stack.imgur.com/x1oQs.png This is plane $a+b+c=U$. Point shows $(U/3,U/3,U/3)$ (for $U=3k$ it can be in node). Red part of plane correspond to requirements $a\leq a_2$, $b\leq b_2$. You need to find node in red part, which is closest to the point. So you just need check two shown distances, all other nodes are definitely farther. But it is not so easy to generalize. – Ivan Kaznacheyeu Jun 08 '23 at 11:52

0 Answers0