Update: If somebody can answer my question there, then I will be able to fully answer my question here.

Consider $n\in\mathbb N$ and a non-empty set $M\subset\{0,1\}^n$. I have the following conjecture:

Conjecture. It is true that $$\sup_{\alpha\in[0,1]^n, \lVert \alpha\rVert_2=1}\min_{m\in M} \langle \alpha, m\rangle = \min_{\beta\in[0,1]^M, \sum_{m\in M} \beta_m = 1} \left\lVert\sum_{m\in M}\beta_m m\right\rVert_2.$$

Here, $\beta_m m$ is just the scalar multiplication of the number $\beta_m$ with $m\in M\subset\{0,1\}^n$. Also, $\lVert \cdot\rVert_2$ is the usual euclidean norm and $\langle\cdot,\cdot\rangle$ is the usual euclidean inner product. (And note, of course, that $[0,1]^M$ is the set of all functions $\beta: M\to[0,1]$ where I will write $\beta_m$ for $\beta(m)$.)

For instance, it is true if $M=\{m\}$, i.e. if $M$ only contains one element. In that case, the left-hand side equals $$\sup_{\alpha\in[0,1]^n, \lVert \alpha\rVert_2 =1}\langle \alpha,m\rangle.$$

By Cauchy-Schwarz, we know that $\langle\alpha, m\rangle\le\lVert \alpha\rVert_2\lVert m\rVert_2=\lVert m\rVert_2$ and we have equality if and only if $\alpha=\frac{m}{\lVert m\rVert_2}$. Hence the left-hand side equals $\lVert m\rVert_2$.

The right-hand side is, as we must have $\beta=1$, $\lVert m\rVert_2$.

If $M=\{m_1, m_2\}$, then we would have to prove $$\sup_{\alpha\in[0,1]^n, \lVert \alpha\rVert_2 = 1} \min(\langle \alpha, m_1\rangle, \langle\alpha, m_2\rangle) = \min_{\beta\in[0,1]} \lVert \beta\, m_1+(1-\beta)\, m_2\rVert_2.$$

This is already not obvious to me. However, for example with $M=\{(1,0),(0,1)\}$, both sides can be computed to equal $\frac1{\sqrt 2}$.

Note: This conjecture is a Lemma that I would need to prove the equivalence of different definitions of convex distance that I found in the context of Talagrand's concentration inequality.

Another example: Consider $n=4$ and (with a slight abuse of notation) $M=\{m_1,m_2,m_3\}=\{(1,1,0,0),(0,1,1,0),(0,1,1,1)\}$.

The right-hand side is $$\min_{(\beta_1,\beta_2,\beta_3)\in[0,1]^3, \beta_1+\beta_2+\beta_3=1} \lVert (\beta_1,\beta_1+\beta_2+\beta_3,\beta_2+\beta_3,\beta_3)\rVert_2.$$

It is not too hard to see that the minimizer is $\beta=(1/2,1/2,0)$ for which we have $$\lVert (\beta_1,\beta_1+\beta_2+\beta_3,\beta_2+\beta_3,\beta_3)\rVert_2=\lVert (1/2,1,1/2,0)\rVert_2=\sqrt{\frac32}.$$

The left-hand side is $$\sup_{(\alpha_1,\alpha_2,\alpha_3,\alpha_4)\in[0,1]^4, \alpha_1^2+\alpha_2^2+\alpha_3^2+\alpha_4^2=1} \min(\alpha_1+\alpha_2,\alpha_2+\alpha_3,\alpha_2+\alpha_3)=\sup_{(\alpha_1,\alpha_2,\alpha_3,\alpha_4)\in[0,1]^4, \alpha_1^2+\alpha_2^2+\alpha_3^2+\alpha_4^2=1}\min(\alpha_1+\alpha_2,\alpha_2+\alpha_3).$$

The supremum occurs only if $\alpha_1+\alpha_2=\alpha_2+\alpha_3$, which happens for $\alpha=\left(\sqrt{\frac16},\sqrt{\frac23},\sqrt{\frac16},0\right)$.

For that $\alpha$, we have $$\alpha_1+\alpha_2=\alpha_2+\alpha_3=\sqrt{\frac32}$$ and so we indeed have equality of both sides.


1 Answer 1


Answer inspired by this great answer to a very related question by Paata Ivanishvili.

The right-hand side is equal to $\min_{m\in\operatorname{conv}(M)} \lVert m\rVert_2$, where $\operatorname{conv}(M)$ is the convex hull of $M$ in $\mathbb R^n$. Hence we have:

\begin{equation} \begin{split} \min_{m\in\mathrm{conv}(M)} \|m\|_{2}&=\min_{m \in \operatorname{conv} (M)} \max_{\|\alpha\|_{2}\leq 1} \langle \alpha, m\rangle \\ &\overset{(*)}= \max_{\|\alpha\|_{2}\leq 1} \min_{m \in \operatorname{conv}(M)}\langle \alpha, m\rangle \\ &\overset{(**)}= \max_{\substack{\alpha \in [0, \infty[^{n}\\\|\alpha\|_{2}\leq 1}} \min_{m \in M}\langle \alpha, m\rangle \\ &=\max_{\alpha\in[0,1]^n \\ \lVert\alpha\rVert_2=1}\min_{m \in M}\langle \alpha, m\rangle. \end{split} \end{equation}

(*): Here, a minimax Theorem was used.
(**): Here, the Bauer maximum principle was used (as the minimum of $m\mapsto\langle\alpha, m\rangle$ will be attained on the extremal points of $\operatorname{conv}(M)$, and they are contained in $M$.) Notice that it is also used that $M\subset\mathbb R_+^n$ in order to restrict the $\alpha$'s to $[0,\infty[^n$.

Note. This works for any compact $M\subset\mathbb R_+^n$, not just $M\subset\{0,1\}^n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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