1
$\begingroup$

In example 3.33 of Boyd & Vandenberghe's Convex Optimization, a proof of the convexity of a half-space (Euclidean ball when $\alpha \le 1$) is presented. I understand we can expand out the $2$-norm and square both sides. But I am not sure what is the "rearranging" that's being done here.

example 3.33

I have found another question that is very similar, Why this function describes a euclidean ball? After reading through it and trying it out myself, I am still not sure how did the equivalency came to be. If anyone could give me any pointers,it would be much appreciated. Thank you in advance.

Editing my question to be more specific:

When we square both sides and multiply out each squared terms, the squared terms will be cancelled out e.g., $x^2_1, x^2_2, \dots, x^2_n$. So all that's left over are the constant terms and the linearly scaled terms. I am unclear how did we get the transposed terms shown in the picture and overall how did we end with those terms.

$\endgroup$
3
  • $\begingroup$ As far as I remember, the idea of this example is to show how the characterization of sub-level sets of (quasi-)convex functions can be used to prove the desired property of the function. The "rearrangement" appears when considering sets of the form $f(x)\leq \alpha$ and then rearranging the latter inequation into an equivalent condition. $\endgroup$
    – Surb
    Jan 30, 2023 at 2:20
  • $\begingroup$ The verb is "to prove", not "to proof". "Proof" is the noun. $\endgroup$ Jan 30, 2023 at 2:39
  • $\begingroup$ Listed $\endgroup$ Jan 30, 2023 at 11:23

1 Answer 1

0
$\begingroup$

(1) That example doesn't show that the halfspace is convex ; rather it tries to show that $f$ is quasi-convex by showing that any sub-level set of $f$ is convex. ($f$ is quasi-convex iff every sub level set is convex)

(2) Now the rearrangement. First using simple vector algebra, you can show the following: \begin{align*} || a - b||_2^2 :&= (a - b)^T \cdot (a - b) \\ &= a^Ta + b^Tb - 2b^Ta \end{align*} Use this in your equations to get: \begin{align*} || x - a ||_2 &\le \alpha || x - b ||_2 \\ \Rightarrow || x - a ||^2_2 &\le \alpha^2 || x - b ||^2_2 \\ \Rightarrow x^Tx + a^Ta - 2a^Tx &\le \alpha^2 (x^Tx + b^Tb - 2b^Tx ) \\ \Rightarrow (1 - \alpha^2) x^Tx - &2(a - \alpha^2 b )^Tx + (a^Ta - \alpha^2 b^Tb) \le 0\\ \end{align*}

(3) Now you just need to check that is the equation of a L2 ball. In general consider an equation of the form $x^Tx - 2b^Tx + c \le 0$. \begin{align*} x^Tx - 2b^Tx + c &\le 0 \\ x^Tx - 2b^Tx + b^Tb &\le b^Tb - c \\ ||(x - b)||_2^2 &\le b^Tb - c \end{align*} So the equation $x^Tx - 2b^Tx + c \le 0$ represents a ball if $b^Tb - c \ge 0$, else it is an empty set. In either case, the set is convex.

(4) So in your original derived set, just divide throughout by $(1 - \alpha^2)$ to get an equation of the form in (3), and you can conclude it is a ball .... but wait, there's a case the book hasn't considered, check for the case $\alpha = 1$ separately, as it is not a ball in this case, but it is still convex ... check this yourself.

$\endgroup$
1
  • $\begingroup$ Amazing, thank you very much for your detailed explanation. It seems like I really need to go back and review some basic math skills. $\endgroup$ Jan 30, 2023 at 2:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .