# Minimising the maximum distance between bounded functions for a given bounded function

Let $g\in C[0,1]$ where $C[0,1]$ is the vector space of continuous functions on [0,1].

For any function $f$, define $A_f$ $= \sup\{\sqrt{(x-y)^2+(f(x)-g(y))^2}:x,y\in[0,1]\}$

Can the "sup" be replaced with "max" here?

Main question: What is inf { $A_f: f \in C[0,1]$} ? Clearly $A_f$ is always unique for a given $g$, but how many functions can give rise to a $A_f$ for a given $g$, and more importantly, how do we find them?

-
Why is the minimum in your main question attainable? – 23rd Dec 7 '12 at 13:39
Yes, good point. There might be a function g(x) such that $f_n(x) = x^n$ gets closer and closer to the function which "provides" $A_f$, and also the function which is the pointwise limit of $(f_n(x))$ would give rise to $A_f$ if we did not require f to be continuous. I have no idea if this is possible but it is not obvious that it is not possible. – Adam Rubinson Dec 7 '12 at 13:52
The sup is indeed a max, as $F(x,y)=(x-y)^2+(f(x)-g(y))^2$ is continuous on the compact set $[0,1]^2$. – Ewan Delanoy Dec 9 '12 at 19:16
Thanks Ewan - that's just what I thought. I don't know much about compact sets (but am about to learn about them). But I guess what you said is similar to B-W on [0,1]^2. – Adam Rubinson Dec 10 '12 at 10:28

I present my answer in three parts :

Part I. List of short answers

Part II. The formal details and proofs.

Part III. A complete example.

Part I : List of short answers

• Is the supremum $A_f$ actually attained ? YES (as $(x-y)^2 + (f(x) - g(y))^2$ is continuous on the compact set $[0,1]^2$)
• Is the infimum ${\sf inf }_f(A_f)$ actually attained ? YES (see proof in Part II)
• Is there a unique optimal solution $f$ ? NO ( in the typical example in Part III, there are uncountably many solutions).
• How do I find the optimal solutions ? It will be clear from Part II that the condition “$f$ is optimal” is equivalent to a certain (obvious&natural) inequality system involving $f$ (called “(*)” in Part II). In the simplest cases (such as the example in Part III), this system reduces to something of the form $L\leq f \leq U$, where $L$ and $U$ are functions that we can compute from the initial data.

Part II : The formal details and proofs

First, note that your $A_f$ depends on $g$, so I prefer to denote it by $A_f^g$. The quantity that we are dealing with is then $\inf_{f}A_f^g$, which I denote by $RD(f,g)$ and call the Rubinson distance between $f$ and $g$. Fix $g\in C([0,1])$. For $x,y\in [0,1]$ and $c\in {\mathbb R}$, let $$F_1(x,c,y)=(x-y)^2+(c-g(y))^2$$ Then $F_1$ is continuous on $[0,1] \times {\mathbb R} \times [0,1]$. Since $[0,1]$ is compact, the function

$$F_2(x,c)={\sf max}_{y\in [0,1]} F_1(x,c,y)$$ is well-defined and continuous on $[0,1] \times {\mathbb R}$. Also, for any $(x,y) \in [0,1]^2$, the map $F_1(x,.,y)$ is nonnegative and strictly convex on $\mathbb R$. We deduce that for any $x\in[0,1]$,$F_2(x,.)$ is also nonnegative and strictly convex on $\mathbb R$.

Now any nonnegative, strictly convex and continuous map on $\mathbb R$ which tends to $+\infty$ at both $-\infty$ and $+\infty$ attains a minimum at a unique point. So for each $x\in [0,1]$, $F_2(x,.)$ attains a global minimum at a unique point, which I denote by $F_3(x)$.

I claim that $F_3$ is continuous on $[0,1]$. For suppose not ; then, we would have a $x\in [0,1]$ and a sequence $(x_n)$ converging to $x$ in $[0,1]$, such that $(F_3(x_n))$ does not converge to $(F_3(x))$. By the Bolzanno-Weierstrass property, we may assume without loss of generality that $(F_3(x_n))$ converges to a value $z$ ; then $z\neq F_3(x)$ by hypothesis. For any $n\in {\mathbb N}$, $F_2(x_n,.)$ attains a global minimum at $F_3(x_n)$. Passing to the limit, we see that $F_2(x,.)$ attains a global minimum at $z$. But by unicity of $F_3(x)$, we must have $z=F_3(x)$, contradiction.

I claim that $F_3$ is an optimal solution. Indeed, let $m=RD(g,F_3)$. There is an $(x_0,y_0)$ in $[0,1]^2$ such that $$m=\sqrt{(x_0-y_0)^2+(F_3(x_0)-g(y_0))^2} =\sqrt{F_1(x_0,F_3(x_0),y_0)} \tag{1}$$ By definition of $RD$, we must have $m \geq \sqrt{F_1(x_0,F_3(x_0),y)}$ for any $y\in [0,1]$. We deduce $$m=\sqrt{{\sf max}_{y\in [0,1]} F_1(x_0,F_3(x_0),y)}=\sqrt{F_2(x_0,F_3(x_0))}. \tag{2}$$

and let $f$ be an arbitrary function in $C([0,1])$. Then we have

$$RD(f,g)={\sf max}_{x,y\in [0,1]} \sqrt{(x-y)^2+(f(x)-g(y))^2} = {\sf max}_{x\in [0,1]} \sqrt{F_2(x,f(x))} \geq \sqrt{F_2(x_0,f(x_0))} \geq \sqrt{F_2(x_0,F_3(x_0))} = m = RD(F_3,g),$$ as wished.

Also, an arbitrary function $f$ will be optimal iff $RD(f,g) \leq m$, or in other words

$$(x-y)^2+(f(x)-g(y))^2 \leq m^2, \tag{*}$$

for any $x,y \in [0,1]$.

Part III : A complete example

Let us look at $g(t)=1+2t$.

We have $F_1(x,c,y)=(x-y)^2+(c-(2y+1))^2$ and the following polynomial identities :

$$F_1(x,c,y)=F_1(x,c,1)-5(1-y)\bigg(\frac{4}{5}.\big(\frac{9-2x}{4}-c\big)+y\bigg) \tag{3}$$

$$F_1(x,c,y)=F_1(x,c,0)-5y\bigg(\frac{4}{5}.\big(c-\frac{9-2x}{4}\big)+1-y\bigg) \tag{4}$$

We deduce

$$F_2(x,c)= \left\lbrace \tag{5} \begin{array}{lcl} F_1(x,c,1) = (x-1)^2+(c-3)^2, & \text{if} & c \leq \frac{9-2x}{4}, \\ F_1(x,c,0) = x^2+(c-1)^2, & \text{if} & c \geq \frac{9-2x}{4} \end{array} \right.$$

And hence $$F_3(x)= \frac{9-2x}{4}, m=\frac{5}{4}. \tag{6}$$

Making (*) explicit, we see that an $f\in C[0,1]$ will be optimal iff

$$2- \sqrt{\frac{25}{16}-(1-x)^2} \leq f(x) \leq \sqrt{\frac{25}{16}-x^2}, \tag{7}$$ for any $x\in [0,1]$. So the optimal solutions will be the solutions whose curve stays between the curves defined by the left-hand and right-hand side in $(7)$.

-
Nice, clear and well structured proof! – k1next Dec 11 '12 at 10:17
Mother of God... – Adam Rubinson Dec 11 '12 at 11:16
I edited your answer to include the comment you referenced, and did some other cleanup while I was there. I hope none of my changes are counter to the spirit of your answer, feel free to revert them if so :) – Ben Millwood Dec 14 '12 at 2:56
@BenMillwood : thank you very much for your latex improvements. – Ewan Delanoy Dec 14 '12 at 7:32