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