[proofplan] We rewrite the formula as a finite-dimensional duality statement for the compact convex set $\operatorname{conv} U_A(x) \subset [0,1]^n$. The upper bound follows by comparing each nonnegative linear functional of Euclidean norm at most one with the Euclidean norm on this convex set. For the reverse inequality, we choose a point of minimal Euclidean norm in the convex hull and use the first-order variational inequality for the squared norm on a convex set. If $A=\varnothing$, both sides are interpreted as $+\infty$ by the stated convention. [/proofplan]

[step:Reduce the assertion to a compact convex subset of $[0,1]^n$] Fix $x = (x_1,\dots,x_n) \in X$ and $A \subset X$. If $A=\varnothing$, then $U_A(x)=\varnothing$, hence $\operatorname{conv}U_A(x)=\varnothing$ and \begin{align*} d_T(x,A)=\inf \varnothing=+\infty. \end{align*} For every $\alpha \in [0,\infty)^n$ with $|\alpha|\le 1$, the set over which the inner infimum is taken is empty, so \begin{align*} \inf_{y\in \varnothing}\sum_{i=1}^n \alpha_i\mathbb{1}_{\{x_i\ne y_i\}}=+\infty. \end{align*} The supremum of the constant value $+\infty$ is $+\infty$, and the identity follows. Assume from now on that $A\ne\varnothing$. Define \begin{align*} S := U_A(x)=\{m_x(y):y\in A\}\subset \{0,1\}^n \end{align*} and define \begin{align*} C := \operatorname{conv}S \subset \mathbb{R}^n. \end{align*} Since $\{0,1\}^n$ is finite, $S$ is finite and nonempty. Therefore $C$ is a nonempty compact convex subset of $\mathbb{R}^n$, and $C\subset [0,1]^n$. By definition, \begin{align*} d_T(x,A)=\inf_{u\in C}|u|. \end{align*} For every $\alpha \in [0,\infty)^n$, linearity gives \begin{align*} \inf_{y\in A}\sum_{i=1}^n \alpha_i\mathbb{1}_{\{x_i\ne y_i\}}=\inf_{s\in S}\alpha\cdot s. \end{align*} Because the map $u\mapsto \alpha\cdot u$ is affine on $C=\operatorname{conv}S$, its infimum over $C$ equals its infimum over the finite set $S$. Hence the desired formula is equivalent to \begin{align*} \inf_{u\in C}|u|=\sup\{\inf_{u\in C}\alpha\cdot u:\alpha\in[0,\infty)^n,\ |\alpha|\le 1\}. \end{align*} [/step]

[step:Bound every admissible weighted distance by the convex distance]Let $\alpha\in[0,\infty)^n$ satisfy $|\alpha|\le 1$. For every $u\in C$, the Euclidean inner-product estimate gives \begin{align*} \alpha\cdot u \le |\alpha|\,|u| \le |u|. \end{align*} Taking the infimum over $u\in C$ on the left and using the fact that the inequality holds for every $u\in C$, we obtain \begin{align*} \inf_{u\in C}\alpha\cdot u \le \inf_{u\in C}|u|=d_T(x,A). \end{align*} Taking the supremum over all $\alpha\in[0,\infty)^n$ with $|\alpha|\le 1$ gives \begin{align*} \sup\{\inf_{u\in C}\alpha\cdot u:\alpha\in[0,\infty)^n,\ |\alpha|\le 1\}\le d_T(x,A). \end{align*}[/step]

[guided]We first prove that no admissible weight vector can produce a value larger than the convex distance. Fix a vector $\alpha\in[0,\infty)^n$ with $|\alpha|\le 1$. The linear functional \begin{align*} L_\alpha:\mathbb{R}^n&\to\mathbb{R} \end{align*} is defined by $L_\alpha(u)=\alpha\cdot u$. For each $u\in C$, the elementary Euclidean inner-product bound gives \begin{align*} L_\alpha(u)=\alpha\cdot u\le |\alpha|\,|u|. \end{align*} Since $|\alpha|\le 1$, this implies \begin{align*} \alpha\cdot u\le |u|. \end{align*} This inequality holds for every point $u$ in the convex hull $C$. Therefore the smallest value of the linear functional on $C$ cannot exceed the smallest Euclidean norm on $C$: \begin{align*} \inf_{u\in C}\alpha\cdot u\le \inf_{u\in C}|u|. \end{align*} By the definition of Talagrand's convex distance, the right-hand side is $d_T(x,A)$. Since the same estimate holds for every admissible $\alpha$, taking the supremum over all admissible $\alpha$ preserves the inequality: \begin{align*} \sup\{\inf_{u\in C}\alpha\cdot u:\alpha\in[0,\infty)^n,\ |\alpha|\le 1\}\le d_T(x,A). \end{align*}[/guided]

[step:Choose the nearest point in the convex hull] The continuous map \begin{align*} N:C&\to[0,\infty) \end{align*} defined by $N(u)=|u|$ attains its minimum on the compact set $C$. Let $u_0\in C$ be a minimizer, so \begin{align*} |u_0|=\inf_{u\in C}|u|=d_T(x,A). \end{align*} Since $C\subset[0,1]^n$, we have $u_0\in[0,\infty)^n$. If $u_0=0$, then $d_T(x,A)=0$. The upper bound from the previous step and the admissible choice $\alpha=0$ give \begin{align*} 0\le \sup\{\inf_{u\in C}\alpha\cdot u:\alpha\in[0,\infty)^n,\ |\alpha|\le 1\}\le 0, \end{align*} so equality holds. Assume now that $u_0\ne 0$. Define \begin{align*} \alpha_0:=\frac{u_0}{|u_0|}\in[0,\infty)^n. \end{align*} Then $|\alpha_0|=1$, so $\alpha_0$ is admissible. [/step]

[step:Use the variational inequality for the nearest point] We prove that \begin{align*} u_0\cdot u\ge |u_0|^2 \end{align*} for every $u\in C$. Fix $u\in C$ and define \begin{align*} \gamma_u:[0,1]&\to C \end{align*} by $\gamma_u(t)=(1-t)u_0+tu$. Convexity of $C$ implies that $\gamma_u(t)\in C$ for every $t\in[0,1]$. Since $u_0$ minimizes the squared norm on $C$, for every $t\in[0,1]$, \begin{align*} |u_0|^2\le |\gamma_u(t)|^2. \end{align*} Expanding the square gives \begin{align*} |\gamma_u(t)|^2=|u_0+t(u-u_0)|^2=|u_0|^2+2t\,u_0\cdot(u-u_0)+t^2|u-u_0|^2. \end{align*} Subtracting $|u_0|^2$ and dividing by $t>0$ yields \begin{align*} 0\le 2u_0\cdot(u-u_0)+t|u-u_0|^2. \end{align*} Letting $t\downarrow 0$ gives \begin{align*} 0\le u_0\cdot(u-u_0). \end{align*} Equivalently, \begin{align*} u_0\cdot u\ge |u_0|^2. \end{align*} Therefore, for the admissible vector $\alpha_0=u_0/|u_0|$, \begin{align*} \alpha_0\cdot u\ge |u_0| \end{align*} for every $u\in C$. Taking the infimum over $u\in C$ gives \begin{align*} \inf_{u\in C}\alpha_0\cdot u\ge |u_0|=d_T(x,A). \end{align*} [/step]

[step:Convert the supporting functional back to weighted mismatches] Since $\alpha_0$ is one of the admissible vectors in $[0,\infty)^n$ with $|\alpha_0|\le 1$, the previous step gives \begin{align*} \sup\{\inf_{u\in C}\alpha\cdot u:\alpha\in[0,\infty)^n,\ |\alpha|\le 1\}\ge d_T(x,A). \end{align*} Together with the upper bound already proved, this gives \begin{align*} d_T(x,A)=\sup\{\inf_{u\in C}\alpha\cdot u:\alpha\in[0,\infty)^n,\ |\alpha|\le 1\}. \end{align*} Finally, for each admissible $\alpha$, \begin{align*} \inf_{u\in C}\alpha\cdot u=\inf_{s\in S}\alpha\cdot s=\inf_{y\in A}\sum_{i=1}^n\alpha_i\mathbb{1}_{\{x_i\ne y_i\}}. \end{align*} Substituting this identity into the preceding display proves \begin{align*} d_T(x,A)=\sup\left\{\inf_{y \in A} \sum_{i=1}^n \alpha_i \mathbb{1}_{\{x_i \ne y_i\}} : \alpha \in [0,\infty)^n,\ |\alpha| \le 1\right\}. \end{align*} This is the asserted dual formula. [/step]