Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to ask that, what is a support function intuitively. It is defined as:

$$\sup_{z \in K} \langle z, x \rangle$$ where $z \in K$, $K$ is a nonempty set. In this formulation, $\langle \cdot, \cdot \rangle$ is inner product.

As a function of $x$, what does it mean? Why it can be useful for instance? Thanks.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

If you take $K$ to be convex, the support function is, in some sense, a tool for a dual representation of the set as the intersection of half-spaces.

Let's assume that we're in $\mathbb R^n$ for simplicity. A hyperplane can be characterized by a direction $\boldsymbol x\in\mathbb R^n$ and a scalar $b\in\mathbb R$, let's write $H=(\boldsymbol x;b)$ one such hyperplane, the set of points $\boldsymbol z\in\mathbb R^n$ on the hyperplane $H$ are then given by $$ \langle \boldsymbol z,\boldsymbol x\rangle \quad = \quad b. $$ The set of points $\boldsymbol z$ lying on one side of the hyperplane $H$ can thus always be written as $\langle \boldsymbol z, \boldsymbol x\rangle\le b$ (modulo a change of sign). So considering $$\sup_{\boldsymbol z\in K} \langle \boldsymbol z,\boldsymbol x\rangle $$ amounts to finding the $b(\boldsymbol x)$ for the direction $\boldsymbol x$ such that set $K$ lies on one side of the hyperplane $(\boldsymbol x,b(\boldsymbol x))$ or equivalently, such that all $z\in K$ verify $\langle \boldsymbol z, \boldsymbol x\rangle \le b(\boldsymbol x)$.

Then $K$ can be understood as the intersection of all the half-spaces thus defined.

It can maybe be useful to look at a basic example: consider the region $K=[0,1]\times [0,1]$. Then let's consider the $x$-direction with the vector $\boldsymbol v=(1,0)^t$, we get $$ h_K(\boldsymbol v) = \max_{\boldsymbol w\in K} \langle\boldsymbol w,\boldsymbol v \rangle = \max_{w_1\in[0,1]} w_1 = 1 $$ and the hyperplane $(\boldsymbol v,1)$ (i.e, the vertical line $x=1$) is indeed such that $K$ lies on strictly one side of it. Doing the same thing for the direction $-\boldsymbol v$, and the perpendicular directions will bring us the for sides of the region. This is a bit of a trivial example but hopefully it can help somewhat for the intuition.

share|improve this answer
    
Thanks! Do you have knowledge about the norms can be represented as support functions? So, let us take $\|x\|_p$. It can be written as $\|x\|_p = \sup_{z \in B_q} \langle z, x \rangle$ where $B_q$ is the norm ball of $\ell_q$ norm and the relationship between $p$ and $q$ is $1/p + 1/q = 1$. I wonder about how this representation is possible? A proof may be. Thanks... –  Deniz Nov 24 '12 at 17:54
1  
you might want to ask another question for that to get a more complete answer. You can think of lp norms in Rn and check for yourself: a good tool for intuition might be to consider the lp-balls ($\{x\in\mathbb R^n|\|x\|_p\le 1\}$ and see that for 0<p<1 the balls are not convex. You might also want to check "Legendre-Fenchel convex conjugates" with, for example, $(\ell^1)^*\sim (\ell^\infty)$ (using sloppy notations) –  tibL Nov 25 '12 at 12:21
    
Thanks again. I will ask another question about dual representations of $\ell_p$ norms. –  Deniz Nov 25 '12 at 12:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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