4
$\begingroup$

My analysis: The second term can be proven to be convex as follows. It is basically a composition of norm with an affine transformation to the power of four: $(x_1^2+x_2^2+x_3^2+1)^2 = \|(x_1^2, x_2^2, x_3^2, 1)^T\|^4$. We know that (1) norm is convex (2) composition of norm as a convex function with an affine transformation is convex and (3) raising to the power of an even number, i.e. 4, preserves the convexity of a convex function. Thus, the above term is a composition of a non-decreasing convex function, i.e power of four, with an affine transformation of a norm and thus $(x_1^2+x_2^2+x_3^2+1)^2$ is convex.

The first is term is a challenge for me. I know that $2x_1^2+3x_2^2+x_3^2+4x_1x_2$ can be written as $\mathbf{x}^T A \mathbf{x}$ where $$ A= \left[ \begin{array}{ccc} 2 & 2 & 0 \\ 2 & 3 & 0 \\ 0 & 0 & 1 \end{array} \right] $$

It is easy to check that all the eigen values of $A$ are strictly positive which makes $\mathbf{x}^T A \mathbf{x}$ convex. Thus, $2x_1^2+3x_2^2+x_3^2+4x_1x_2+7$ is convex. Now, the issue is that square-root is concave and does not preserve the convexity. How should I proceed from here?

$\endgroup$
3
  • $\begingroup$ Have you considered looking into the Hessian of the first term? $\endgroup$ Commented Apr 18, 2016 at 5:49
  • $\begingroup$ Good question. No. I am sure that there should be an easier way to prove this. The way I am looking is composing convex functions and using the transformations like affine transformation, norm, even power that preserve the convexity. The reason I need to prove this way is that I need to solve with CVX and CVX understands that the function is convex only if it is using the atoms they have defined, namely, norm, affine transformation, square, even power, inverse of a positive variable, quadratic over linear and quadratic from $\mathbf{x}^T A \mathbf{x}$ with $A>0$ $\endgroup$
    – Vahidn
    Commented Apr 18, 2016 at 5:57
  • $\begingroup$ Humm, I'll try and see where completing squares takes us. $\endgroup$ Commented Apr 18, 2016 at 6:00

2 Answers 2

4
$\begingroup$

Notice that $\mathrm{x} \mapsto f(\mathrm{x})$ is convex if and only if $y \mapsto f(B\mathrm{y})$ is convex for some invertible matrix $B$. (This is because linear transform preserves lines.)

Now using the spectral theorem, choose a symmetric matrix $B$ such that $AB = BA$ and $A^{-1} = B^2$. Then with the transform $\mathrm{x} = B\mathrm{y}$, we see that the given formula is equal to

$$ (|\mathrm{y}|^2 + 7)^{1/2} + (\mathrm{y}^{T} A^{-1}\mathrm{y} + 1)^2. $$

Now this function is easier to work with, and it is not hard to check that each term is convex. Especially for the first term, following computation may be useful:

Observation. If $f : \Bbb{R}^n \to \Bbb{R}$ be defined by $f(\mathrm{x}) = (|\mathrm{x}|^2 + c)^{1/2}$ for some $c \geq 0$, then $$ \operatorname{Hess}f = \frac{1}{f} ( I - (\nabla f) (\nabla f)^T). $$ Consequently, eigenvalues of $\operatorname{Hess}f$ is $c/f^3$ with multiplicity $1$ and $1/f$ with multiplicity $n-1$.

$\endgroup$
6
  • $\begingroup$ Very nice solution; I like especially that there is one general, good idea behind it (the first sentence). $\endgroup$ Commented Apr 18, 2016 at 6:10
  • $\begingroup$ @Fimpellizieri, Thank you! $\endgroup$ Commented Apr 18, 2016 at 6:15
  • $\begingroup$ I did not get the second paragraph: "Now using the spectral theorem, choose a symmetric ..... " $\endgroup$
    – Vahidn
    Commented Apr 18, 2016 at 6:27
  • $\begingroup$ @Vahidn, It is easier than it may seem. Use spectral theorem to write $A = P^{T}DP$ for some orthogonal matrix $P$ and a diagonal matrix $D$. Your computation shows that $D = \operatorname{diag}(\lambda_1, \cdots, \lambda_n)$ consists only of positive diagonals, i.e., $\lambda_i > 0$. Then $D^{-1/2} = \operatorname{diag}(\lambda_1^{-1/2}, \cdots, \lambda_n^{-1/2})$ is well-defined and $$B = P^{T}D^{-1/2}P$$ satisfies all the required property. $\endgroup$ Commented Apr 18, 2016 at 6:30
  • $\begingroup$ @SangchulLee, Awesome. You got it right! Thank you. I need to update myself on the Spectral Theorem. $\endgroup$
    – Vahidn
    Commented Apr 18, 2016 at 6:33
2
$\begingroup$

Th function can be reformulated as follows, \begin{align} & \sqrt{2(x_1+x_2)^2+x_2^2+x_3^2+7}+(x_1^2+x_2^2+x_3^2+1)^2 \\ &= \|(\sqrt{2}(x_1+x_2), x_2, x_3, \sqrt{7})^T\| + \|(x_1, x_2, x_3, 1)^T\|^4 \label{pvii:1r} \end{align}

where $\|.\|$ is 2-norm. The above reformulated function is sum of two convex functions. Here, $\|(\sqrt{2}(x_1+x_2), x_2, x_3, \sqrt{7})^T\|$ is a composition of a 2-norm with an affine transformation and is convex. The second term $\|(x_1, x_2, x_3, 1)^T\|^4$ is a composition of an even power function with power 4 which is convex in $\mathbb{R}$ and nondecreasing in $\mathbb{R^+}$ with a norm function which is convex and non-negative. Thus, we can safely say that the composition is convex. Note that we need the fact that norm is nonnegative otherwise the convexity of the composition is not guaranteed.

$\endgroup$

You must log in to answer this question.

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