1
$\begingroup$

Given an arbitrary set $A ⊂ \mathbb{R}^n$ , the support function associated with the set $A$

$ σ_A : \mathbb{R}^n \to \mathbb{R} ∪ \{+\infty\}$ is defined as

$\sigma_A(x):= \sup_{z \in A} \langle x,z \rangle$

Prove that $\sigma_A$ is convex.

Can I confirm that the inner product $\langle x, z \rangle$ is just a line orthogonal to $x$

I am confused by the meaning of "support function" and also what $\sigma_A(x)$ is. If it's the supremum of the inner product of $x$ and $z$ (which tells us what exactly?) isn't it just going to be a single point/value?

How can I prove this, and where has my interpretation failed me?

$\endgroup$
  • 1
    $\begingroup$ Any supremum of convex functions is convex. For each $z$ the function $x \mapsto \langle z, x \rangle$ is convex. So $\sigma_A(x) = \sup_{z \in A} \langle z,x \rangle$ is convex. $\endgroup$ – littleO Jun 6 at 1:45
0
$\begingroup$

First of all, \begin{align*} \sigma_A(x)=\sup_A\langle x, z\rangle=\sup\{\langle x,z\rangle\ |\ z\in A\}. \end{align*} To prove that $\sigma_A$ is convex, let $x,y\in\mathbb R^n$ and $t\in[0,1]$. Then \begin{align*} \sigma_A(tx+(1-t)y)&=\sup_{z\in A}\langle tx+(1-t)y,z\rangle \\ &= \sup_{z\in A}\left(t\langle x,z\rangle+(1-t)\langle y,z\rangle\right) \\ &\leq t\sup_{z\in A}\langle x,z\rangle+(1-t)\sup_{z\in A}\langle y,z\rangle \\ &=t\sigma_A(x)+(1-t)\sigma_A(y), \end{align*} which shows that $\sigma_A$ is convex.

$\endgroup$
  • $\begingroup$ $\langle x, y \rangle$ does not measure the angle between $x$ and $y$, which is given by $\arccos((\langle x, y \rangle)/(||x||\cdot ||y||))$. What $\sigma_A(x)$ represents is the largest value $\alpha$ such that $A$ is contained in the hyperplane $\{z \in \mathbb{R}^n \mid \langle z,x \rangle \leq \alpha\}$. $\endgroup$ – Pedro M. Jan 20 '15 at 18:13
  • $\begingroup$ I know that this is not really the angle, but I thought that this might be easier to imagine than the hyperplane-thing. But you are right, I changed my answer. $\endgroup$ – sranthrop Jan 20 '15 at 18:18
  • $\begingroup$ The problem was not whether it is easier or not to imagine, but the conclusion that $\sigma_A$ has something to do with "the largest angle" was not correct: for instance, if $A$ is the unit sphere, then $\sigma_A(x) = ||x||$ (you could argue that this has to do with the smallest angle, but that also does not hold every time). $\endgroup$ – Pedro M. Jan 20 '15 at 18:27
  • $\begingroup$ So what exactly does $\langle x,z \rangle$ represent? What is the purpose of a 'support function' and why are we taking the supremum of $\langle x,z \rangle$ ? @sranthrop thank you for your answer $\endgroup$ – diabloescobar Jan 20 '15 at 19:30
0
$\begingroup$

When $f(x)=\sup_{a\in A}\ a\cdot x$, then for $x,\ y$ s.t. they are close, there are two affine hyperplane $P_x,\ P_y$ s.t. $$(1)\ P_x\perp x\ {\rm and}\ P_y\perp y$$ $(2)$ $A,\ x$ (resp $y$) are in different sides wrt $P_x$ (resp $ P_y$) and $(3)$ $P_x\bigcap A,\ P_y\bigcap A$ are non-empty.

Note that $f(x)= p\cdot x$ for any $p\in P_x$. When $z$ is a mid point in $[xy]$, then \begin{align*} f(z) &\leq \sup_{p\in P_x^+ \bigcup P_y^+}\ z\cdot p \\ &=\frac{1}{2}\sup_{p\in P_x^+ \bigcup P_y^+}\ x\cdot p + y\cdot p\\ &= \frac{1}{2} \sup_{p\in P_x^+\bigcup P_y^+}\ x\cdot p + \frac{1}{2}\sup_{p\in P_x^+ \bigcup P_y^+}\ y\cdot p\\&= \frac{1}{2}\{ f(x)+f(y)\} \end{align*}

where $P_x^+$ is a closed half plane intersecting $A$ whose boundary is $P_x\bigcap P_y$.

$\endgroup$

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.