1
$\begingroup$

So, I have trouble proving the following, I'd be grateful if somebody helps me with this.

Let $z$ be a given point in $\mathbb{R}^m$. Then, $x\in \mathbb{R}^m$ is a dual vector of $z$ with respect to $\|.\|$ if it satisfies $\|x\|=1$ and $z^Tx=\|z\|'$.
A norm $\|.\|$ is said to be strictly convex if the unit sphere $\{x:\|x\|=1\}$ contains no line segment.

Now, how does one prove that

The norm $\|.\|$ is strictly convex if and only if each $z\in \mathbb{R}^m$ has a unique dual vector.

Here is my attempt: Suppose that $\|.\|$ is strictly convex, that is, $\{x:\|x\|=1\}$ does not contain any line segment.
Let us take $x$ such that $\|x\|=1$. Then,
$\|z\|'=\underset{\|x\|=1}{\max}\frac{z^Tx}{\|x\|}.$
Then, can I say $\|z\|'=z^Tx$ since $\|x\|=1$ and hence $x$ is a dual vector of $z$?
For uniqueness, let $x_0$ be another dual vector of $z$, hence $\|x_0\|=1$.

Now, how do I use the strict convexity of $\|.\|$ to show that $x_0=x$?
Conversely, suppose that $z$ has a unique dual vector $x$. So, $\|z\|'=z^Tx$ and $\|x\|=1$. We know that $\|.\|$ is strictly convex when the sphere $\{x:\|x\|=1\}$ does not contain any line segments.
How do I connect these two ideas?

$\endgroup$
  • $\begingroup$ To confirm, $\|z\|'$ is the dual norm of $z$? Which definition of dual norm do you use? $\endgroup$ – Theo Bendit May 30 at 5:43
  • $\begingroup$ I am downvoting your post and opting to close it, because just as in your previous lengthy post on the definition of a norm of a convex body, you put a lot of effort in copying the problem, but no effort whatsoever to solve it yourself. $\endgroup$ – uniquesolution May 30 at 5:46
  • 1
    $\begingroup$ @TheoBendit $\|z\|'=\underset{\|x\|\le 1}{\max} z^Tx$. $\endgroup$ – Octagonal Monk May 30 at 6:03
  • $\begingroup$ @uniquesolution Aww, you put so much effort into writing this lengthy comment but put no effort into helping me? I didn't solve it because I have no idea where to start it. $\endgroup$ – Octagonal Monk May 30 at 6:04
  • $\begingroup$ I'm not sure this is true. Should we instead be proving $\|\cdot\|'$ is strictly convex? $\endgroup$ – Theo Bendit May 30 at 6:16
1
$\begingroup$

Sorry, I got it backwards. Yes, this indeed holds.

Fix $z \in \Bbb{R}^m$, and consider the set $$C_z =\left\{x \in \Bbb{R}^m : \|x\| = 1 \text{ and } z \cdot x = \|z\|' = \max\limits_{\|y\| \le 1} z \cdot y\right\}.$$ Note that $C_z$ is a subset of the unit sphere (of $\| \cdot \|$). I claim that $C_z$ is convex. Take two $x_1, x_2 \in C_z$ and $\lambda \in [0, 1]$. Then $$z \cdot (\lambda x_1 + (1 - \lambda)x_2) = \lambda \|z\|' + (1 - \lambda)\|z\|' = \|z\|'.$$ Also, $$\|\lambda x_1 + (1 - \lambda)x_2\| \le \lambda \|x_1\| + (1 - \lambda)\|x_2\| = 1.$$ We now have to show that the above inequality is not strict. Let $$y = \frac{\lambda x_1 + (1 - \lambda)x_2}{\|\lambda x_1 + (1 - \lambda)x_2\|}.$$ Note that $y$ is in the unit sphere (of $\| \cdot \|$), and $$z \cdot y = \frac{z \cdot (\lambda x_1 + (1 - \lambda)x_2)}{\|\lambda x_1 + (1 - \lambda)x_2\|} = \frac{\|z\|'}{\|\lambda x_1 + (1 - \lambda)x_2\|} \ge \|z\|' \ge z \cdot y.$$ Hence $\|\lambda x_1 + (1 - \lambda)x_2\| = 1$, so $$\lambda x_1 + (1 - \lambda)x_2 \in C_z$$ and $C_z$ is convex.

Therefore, if $\|\cdot\|$ is strictly convex, then the sphere contains no line segments. That is, the only non-empty convex subsets of the sphere are singletons. So, $|C_z| = 1$ in such a case, i.e. there is a unique dual vector $x \in C_z$.

On the other hand, suppose $\| \cdot \|$ is not strictly convex. Pick a line segment $L = \operatorname{conv} \{x_1, x_2\}$ in the unit sphere, and let $x$ be their midpoint. Find a supporting hyperplane $H = \{y \in \Bbb{R}^m : z \cdot y = z \cdot x\}$, where $z \in \Bbb{R}^m$ is some fixed non-zero vector. In particular, we choose the direction of $z$ so that the halfspace $S = \{y \in \Bbb{R}^m : z \cdot y \le z \cdot x\}$ contains the unit sphere, and hence its convex hull, the unit ball.

In particular, this means that $z \cdot y$ achieves its maximum over $y$ in the unit ball at $x$, and, indeed, any other point in the intersection of $H$ and the unit sphere. Such points are dual to $z$, by definition!

Now, I claim that $x_1$ and $x_2$ are two such points. We have, \begin{align*} z \cdot x_1 \le z \cdot x &= z \cdot \frac{x_1 + x_2}{2} \\ z \cdot x_2 \le z \cdot x &= z \cdot \frac{x_1 + x_2}{2}. \end{align*} Assume either of the inequalities above was strict. Then, adding these inequalities together, $$z \cdot x_1 + z \cdot x_2 < 2 z \cdot \frac{x_1 + x_2}{2},$$ which is absurd. Thus, equalities hold above, and $x_1, x_2 \in H$, as claimed. Thus, $z$ is dual to (more than) two points $x_1, x_2$.

$\endgroup$
  • $\begingroup$ $x=\frac{x_1+x_2}{2}$, how? And, $z$ is dual to more than two points $x_1, x_2$? But we have to prove that $z$ has a unique dual. $\endgroup$ – Octagonal Monk May 30 at 7:42
  • $\begingroup$ That was my definition of $x$: the midpoint between $x_1$ and $x_2$. The thrust of that part of the proof is to show that, if $\|\cdot\|$ is not strictly convex, then dual points are not unique. Contrapositively, this shows that unique dual points implies strict convexity. $\endgroup$ – Theo Bendit May 30 at 7:45
  • $\begingroup$ Oh, ok. Is that why put $z.x_1\le z.x$? $\endgroup$ – Octagonal Monk May 30 at 7:47
  • $\begingroup$ I put $z \cdot x_1 \le z \cdot x$ because $x_1$ lies in the unit sphere, and hence lies in the halfspace $S$. $\endgroup$ – Theo Bendit May 30 at 7:48
  • $\begingroup$ Ok, thank you so much. I now fully understand it. $\endgroup$ – Octagonal Monk May 30 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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