# Minimizing the maximum of some functions

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?

-
You can define a new function $g(x,y) := \max \{f_1, \dots, f_n\}$ and find the minimum of that. Of course, this need not be differentiable, so you can't use analytical tools to solve the problem. But you can instead minimize the sum of squares (this would be the famous least squares method) which is smooth and actually in your case just a polynomial of degree two, so this is simple to solve. –  Marek Jan 11 '13 at 12:15
Thank you but does minimizing the sum of squares ensures that the maximum of the square is also minimized? –  Rafi Kamal Jan 11 '13 at 12:40
No, it doesn't. But it gives similarly good (and for many purposes better) results, that's why I mentioned it. If you intend to use the maximum, I don't think there is any math that's going to help you solve it, you will need an algorithm similar to the one creating Voronoi diagram (en.wikipedia.org/wiki/Voronoi_diagram). Note that when all the weights $S_i$ are equal, the solution is obtained as center of the circle circumscribed to the convex hull of the points $(x_i, y_i)$. –  Marek Jan 11 '13 at 13:40
is $S_i$ a constant? Do we know whether it is > or < 0 ? –  sonystarmap Jan 11 '13 at 13:41
@macydanim Yes, it is a constant > 0. –  Rafi Kamal Jan 11 '13 at 13:48

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.

-

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.

-