7
$\begingroup$

I came across a question which contained this $\sqrt{x_1^2+4x_1x_2+5x_2^2+2x_1+6x_2+5}$
I needed to prove $x_1^2+4x_1x_2+5x_2^2+2x_1+6x_2+5\geq0$ which I've done by just showing that the minimum is 3 and it's convex function.
The second part asked to show that the whole problem is convex but I didn't know how to prove $\sqrt{x_1^2+4x_1x_2+5x_2^2+2x_1+6x_2+5}$ is convex which is same as asking $\sqrt{x^TAx+b^Tx+c}$ is convex where $x^TAx+b^Tx+c\geq0$. any help?

$\endgroup$
0
8
$\begingroup$

Extended hint: a non-negative quadratic function with positive-definite $A$ can be written as $$ x^TAx+b^Tx+c=\|M(x-x_0)\|^2+d^2. $$ It can be done by completing the square in $x$ or simply identifying $M$, $x_0$ and $d$ from the equation: $A=M^TM$, $d^2$ is the minimum value ($3$ in your case) and $x_0$ is the minimizer.

Now the function you are dealing with is $$ f(x)=\left\|\begin{matrix}M(x-x_0)\cr d\end{matrix}\right\|. $$ It could be proven to be convex directly by definition using triangle inequality (or as a composition of the convex norm-function and the affine one).

$\endgroup$
1
  • 1
    $\begingroup$ cool cool, you use $(x-x_0)A(x-x_0) + d^2 = x^TAx + b^Tx + c$, which is true since $x_0$ satisfies $2Ax+b=0$ $\endgroup$
    – LinAlg
    Feb 1 at 2:37
5
$\begingroup$

Note that $$ x^\top A x + b^\top x + c = \begin{bmatrix}x^\top&1\end{bmatrix}\begin{bmatrix}A&b/2\\b^\top/2 & c\end{bmatrix}\begin{bmatrix}x\\1\end{bmatrix} = \tilde{x}^\top\tilde{A}\tilde{x}. $$

Now, we test $\tilde{A}$ for positive definiteness by calculating its principal minors (I'll skip most of the calculations). We have $$ A = \begin{bmatrix}1&2\\2&5\end{bmatrix},\quad b=\begin{bmatrix}2\\6\end{bmatrix},\quad c = 5, $$ thus, the first principal minor is $1$, and we have $\det(A)>0$, which is the second principal minor of $\tilde{A}$. All that remains is to test $\det{\tilde{A}}$, which is (using Schur): $$ c\det(A - \frac{bb^\top}{4c}) = 5\begin{vmatrix}1 - 1/5& 2-3/5\\2-3/5 &5-9/5\end{vmatrix} = 3 > 0. $$

Since $\tilde{A}$ is positive definite, then $\lVert \tilde{x} \rVert_{\tilde{A}} = \sqrt{\tilde{x}^\top \tilde{A} \tilde{x}}$ is a norm, and thus convex.

$\endgroup$
2
  • 1
    $\begingroup$ your test for positive definite is not complete, it should depend on $b$ $\endgroup$
    – LinAlg
    Feb 1 at 3:28
  • $\begingroup$ @LinAlg My mistake, you're right, I'll edit the answer. $\endgroup$
    – V.S.e.H.
    Feb 1 at 3:35
2
$\begingroup$

$f(x)=\sqrt{x^TAx+b^Tx+c}$ is convex where $x^TAx+b^Tx+c\geq0$

$A$ should be assumed positive definite (e.g., $\sqrt{25-x^2}$ is not convex on $[0,5]$).

Proof

Some nonnegative polynomials can be written as a sum of squares. By Hilbert's Theorem, that is the case for every second degree polynomial. This allows you to write the function as a norm.

Failed attempt below

For convenience I assume that $A$ is symmetric. The gradient of $f$ is $$Df=\frac{2Ax + b}{2\sqrt{x^TAx+b^Tx+c}}$$ and the Hessian is: $$Hf =\frac{4\sqrt{x^TAx+b^Tx+c}A - (2Ax+b)(2Ax+b)^T/\sqrt{x^TAx+b^Tx+c}}{4(x^TAx+b^Tx+c)}$$ Multiplying the numerator and denominator with $\sqrt{x^TAx+b^Tx+c}$ yields: $$Hf =\frac{4(x^TAx+b^Tx+c)A - (2Ax+b)(2Ax+b)^T}{4(x^TAx+b^Tx+c)^{3/2}}$$ The denominator is positive on the interior of the feasible region, so all we need to check is if the numerator is positive semidefinite. In the one dimensional case, the numerator simplifies to $4ac-b^2$, which is indeed nonnegative because $ax^2+bx+c=0$ has at most one solution. Looking at derivations of the abc-formula, completing the square might be the key to a solution, but I do not yet see how it can be done. Another issue in higher dimensions is that $x^TAxA$ does not cancel against $Axx^TA$. Perhaps the statement is false after all.

$\endgroup$

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.