Can you prove that this function is convex? $\sqrt{2x_1^2+3x_2^2+x_3^2+4x_1x_2+7} + (x_1^2+x_2^2+x_3^2+1)^2$.

Question

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?

Answer 1

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.

Answer 2

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$.