2
$\begingroup$

I am trying to prove the convexity for the following function: $$f(x) = \sqrt{(a^Tx)^2 + (b^Tx)^2}$$ where $\{a,b,x \} \in \mathbb{R}^n$. I showed that the Hessian is positive semidefinite (which proves the convexity), but the equations are very complicated, so I'm trying to use the definition of convex functions to prove it (i.e., $$f(tx_1 + (1-t)x_2) \leq tf(x_1) + (1-t)f(x_2); \ \forall t \in [0,1]$$

However, I cannot seem to be able to prove this. Any ideas on how to approach this? Your help is much appreciated!

$\endgroup$
3
$\begingroup$

Let $f : \mathbb R^n \to \mathbb R$ be defined by

$$f (\mathrm x) := \sqrt{ (\mathrm a^{\top} \mathrm x)^2 + (\mathrm b^{\top} \mathrm x)^2 } = \sqrt{ \mathrm x^{\top} \mathrm a \mathrm a^{\top} \mathrm x + \mathrm x^{\top} \mathrm b \mathrm b^{\top} \mathrm x } = \sqrt{ \mathrm x^{\top} \left( \mathrm a \mathrm a^{\top} + \mathrm b \mathrm b^{\top} \right) \mathrm x }$$

Let $\mathrm Q := \begin{bmatrix} | & |\\ \mathrm a & \mathrm b\\ | & |\end{bmatrix}$. Hence, $\mathrm a \mathrm a^{\top} + \mathrm b \mathrm b^{\top} = \mathrm Q \mathrm Q^{\top}$ is positive semidefinite and

$$f (\mathrm x) = \sqrt{ \mathrm x^{\top} \left( \mathrm a \mathrm a^{\top} + \mathrm b \mathrm b^{\top} \right) \mathrm x } = \sqrt{ \mathrm x^{\top} \mathrm Q \mathrm Q^{\top} \mathrm x } = \| \mathrm Q^{\top} \mathrm x \|_2$$

Exploiting the subadditivity of $\|\cdot\|_2$,

$$f \left( \gamma \mathrm x_1 + (1-\gamma) \mathrm x_2 \right) = \| \mathrm Q^{\top} (\gamma \mathrm x_1 + (1-\gamma) \mathrm x_2) \|_2 \leq \gamma \, \| \mathrm Q^{\top} \mathrm x_1 \|_2 + (1-\gamma) \, \| \mathrm Q^{\top} \mathrm x_2 \|_2$$

Thus, $f$ is convex.

$\endgroup$
  • $\begingroup$ Interesting. Thanks for the response! A couple of questions...I don't understand how the matrix $Q$ is defined...Is it an $n \times 2$ matrix? Also, did you use the triangle inequality in the last equation? $\endgroup$ – Johnny Que Mar 5 '17 at 16:14
  • $\begingroup$ Yes to both questions. $\endgroup$ – Rodrigo de Azevedo Mar 5 '17 at 16:18
  • $\begingroup$ Very nice, thanks :) $\endgroup$ – Johnny Que Mar 5 '17 at 16:53
2
$\begingroup$

Starting out from $f(tx_1 + (1-t)x_2) \leq tf(x_1) + (1-t)f(x_2)$ lets square both sides to get rid of the square-root on the left to get \begin{align*} (ta^Tx_1 + (1-t)a^Tx_2)^2 + (tb^Tx_1 + (1-t)b^Tx_2)^2 \leq t^2 ((a^Tx_1)^2 + (b^Tx_1)^2) + (1-t)^2 ((a^Tx_2)^2 + (b^Tx_2)^2) + 2t(1-t)\sqrt{((a^Tx_1)^2 + (b^Tx_1)^2)((a^Tx_2)^2 + (b^Tx_2)^2)}. \end{align*} Now writing out the squares on the left and canceling with right hand side terms leaves \begin{align*} 2ta^Tx_1(1-t)a^Tx_2 + 2tb^Tx_1(1-t)b^Tx_2 \leq 2t(1-t)\sqrt{((a^Tx_1)^2 + (b^Tx_1)^2)((a^Tx_2)^2 + (b^Tx_2)^2)}, \end{align*} where we can also drop the $2t(1-t)$ factor. We can square again both sides to get \begin{align*} (a^Tx_1 a^Tx_2 + b^Tx_1 b^Tx_2)^2 \leq ((a^Tx_1)^2 + (b^Tx_1)^2)((a^Tx_2)^2 + (b^Tx_2)^2). \end{align*} Now multiplying out both sides and canceling leaves \begin{align*} 2 a^Tx_1 a^Tx_2 b^Tx_1 b^Tx_2 \leq (a^Tx_1)^2(b^Tx_2)^2 + (b^Tx_1)^2 (a^Tx_2)^2, \end{align*} which is equivalent to \begin{align*} 0 \leq (a^Tx_1)^2(b^Tx_2)^2 + (b^Tx_1)^2 (a^Tx_2)^2 - 2 a^Tx_1 a^Tx_2 b^Tx_1 b^Tx_2 = \left(a^Tx_1 b^Tx_2 - b^Tx_1 a^Tx_2\right)^2, \end{align*} which now obviously is true and should show the convexity of your function.

$\endgroup$
  • $\begingroup$ Wow, great! Thanks for the detailed algebra! I thought there was a more simpler explanation (like for example, since we know that $(a^Tx)^2 + (b^Tx)^2$ is convex, then maybe there was a property that stated that the square root of this convex function is convex. But thanks again for the details :) $\endgroup$ – Johnny Que Mar 4 '17 at 18:34
  • $\begingroup$ I first considered properties of convex functions (en.wikipedia.org/wiki/Convex_function) but I didn't see a good way to combine them - the square root complicates things. So I thought I'll instead derive it from first principles. I hope it helps... :-) $\endgroup$ – user3456032 Mar 4 '17 at 19:02
  • $\begingroup$ Yes was a great explanation, thanks again :) $\endgroup$ – Johnny Que Mar 4 '17 at 19:24
  • $\begingroup$ If you think the answer was helpful and it (completely) solves your question you can accept it (set the green check mark) - this way the status is clear to other members of the community that look into it to either provide a different answer or look for the solution :-) $\endgroup$ – user3456032 Mar 4 '17 at 23:40

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.