Let $S=A\cup B$ where $A=\{(x_1,x_2):x_1<0,x_1^2+x_2^2\le4\}$ and $B=\{(x_1,x_2):x_1\ge0,-2\le x_2 \le2\}. $ Find the support function.

The support function is defined as $f(y)=\text{sup} \{y^tx:x\in S\},$ where $S$ is a convex and bounded set in $\mathbb R^n$ and $f:\mathbb R^n\to\mathbb R.$

From here, $$f(y)=\text{sup} \{y^t(x_1,x_2):(x_1,x_2)\in A\cup B\}=\text{sup} \{(y_1x_1+x_2y_2):(x_1,x_2)\in A\cup B\}$$

What do I do from here?

Should I consider cases for $(x_1,x_2)?$ i.e. if $(x_1,x_2)\in A$ or in B or in both?

  • $\begingroup$ "S" is not convex in your question ! does that matter at all? $\endgroup$ – Red shoes Dec 31 '17 at 2:15
  • $\begingroup$ @Redshoes Sorry I forgot it was a circle. $\endgroup$ – user441848 Dec 31 '17 at 2:16
  • $\begingroup$ By $\sup$ do you mean least upper bound? I'm confused because of the word "support". $\endgroup$ – Shine On You Crazy Diamond Dec 31 '17 at 3:47
  • $\begingroup$ @EnjoysMath yes, sup means the least upper bound $\endgroup$ – user441848 Dec 31 '17 at 3:55
  • 1
    $\begingroup$ Note that even if $S$ is not convex, the support function is convex, being the supremum of an (potentially infinite) set of affine functions. $\endgroup$ – Michael Grant Jan 2 '18 at 17:27

The dot product $y^t x$ equals $\cos \theta |y||x|$ where $\theta$ is the smaller angle between the two vectors. So to maximize $y^t x$ you choose a vector $x$ that is parallel to $y$ since then $\cos (0) = 1 = $ the maximum value $\cos$ can take.

Thus the $x$ maximizing the orange $y$ vector pictured is always going to be on the boundary of $S$. Thus $f(y)$ is simply the magnitude $|y| \equiv \sqrt{y^t y}$ times the distance from the origin to where the boundary of $S$ intersects the ray along $y$.

It seems weird to me that you'd have to compute the actual expression for that, which will usually be some conditionals for the square on the right half plane, and a little simpler for the circle on the left half plane.

If you have to compute the explict description of it, you can find where the ray $r(t) = y t$ intersects each line in the square and similarly where it intersects the circle.

enter image description here

  • $\begingroup$ I agree with you that it seems "weird" to have to compute this explicitly. But the original question reads like a homework exercise, frankly. Support functions are useful constructs in general, even if this specific example seems contrived, as many homework problems are. $\endgroup$ – Michael Grant Jan 2 '18 at 17:28
  • 1
    $\begingroup$ That said, thanks to your diagram, we can determine the expression by inspection: $$f(y) = \begin{cases} +\infty & y_1 > 0 \\ 2 \|y\|_2 & y_1 \leq 0 \end{cases}$$ This follows directly from the fact that, on the right side of the plot, we can choose $x_1$ arbitrarily large, so $x^T y$ is unbounded above. And on the left side, $\|x\|_2=2$ on the boundary, and $x^T y \leq \|y\|_2 \|x\|_2 \leq 2\|y\|_2$. $\endgroup$ – Michael Grant Jan 2 '18 at 17:37
  • $\begingroup$ Why $x^T y \leq \|y\|_2 \|x\|_2 \leq 2\|y\|_2$? $\endgroup$ – user441848 Jan 16 '18 at 7:05
  • $\begingroup$ The first inequality is simply the Cauchy Schwartz inequality. (If you don't know it, look it up; you need it to do just about anything useful in convex analysis). The second inequality follows from the fact that $\|x\|_2\leq 2$, given that the left-half side of the region is a circle of radius 2. $\endgroup$ – Michael Grant Jan 17 '18 at 5:09

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.