Minimizing the maximum of some functions

Question

I have some two variable functions defined as $f(x, y)_i = \frac{\sqrt{(x_i - x)^2 + (y_i - y)^2}}{S_i}$

Let I have $n$ such functions $f(x, y)_1, f(x, y)_2$ ... $f(x, y)_n$. I have to minimize the maximum of these functions by choosing appropriate values of $x$ and $y$. How to do this?

Answer 1

The case of $S_i$'s being equal is covered by the smallest circle cover. For the general case look at the bottom of this article.

Answer 2

First let us collect the information we can extract from the problem.

1. $f(\cdot,\cdot)_i\geq 0$ as $S_i>0, \forall i$
2. $f(\cdot,\cdot)_i$ is continuously differentiable $\forall i$
3. $\min(\max (f_1,...f_n))>0$

As 1. and 2. are clear, let me explain 3. Assume we would have $\min(\max(f_1,..,f_n))=0$. This would imply that we have $f_1=...=f_n=0$ at that certain minima. This would only be possible, if the pair $(x_i,y_i)$ is the same $\forall i$, which would make the problem trivial. We can also assume that the pairs $(x_i,y_i)$ differ $\forall i$, because otherwise we could ignore all the functions with the same pairs, except for the one with the smallest value for $S_i$. The fact, that we can not have zero as a minima furthermore implies, that our minima doesn't occur at the position of a minima of any $f_i$ as they all have zero as a minima.

From that we can derive that our minima occours

• at the minimum of the intersection line of two functions
• or at the intersection point of three (or more) functions

So you have to calculate the intersection lines / points and check whether all other functions have lower values at that points. From all the intersection points and minima of the intersection lines where your value is greater than the value of all other functions at that point you then take the minimal value.