9
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – user48547 Nov 24 '12 at 17:54
  • 1
    $\begingroup$ 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) $\endgroup$ – tibL Nov 25 '12 at 12:21
  • $\begingroup$ Thanks again. I will ask another question about dual representations of $\ell_p$ norms. $\endgroup$ – user48547 Nov 25 '12 at 12:56
  • $\begingroup$ nice and useful answer $\endgroup$ – sleeve chen Jun 8 '15 at 22:18

Your Answer

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