Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

1 Answer 1

up vote 7 down vote accepted
+50

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)$.

share|improve this answer
    
Nice, clear and well structured proof! –  sonystarmap 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.