0
$\begingroup$

As the title says, the problem I'm trying to solve gives that $Q \succcurlyeq 0$, but it doesn't seem to indicate that $Q$ is necessarily symmetric. So far I've tried

  • proving from the definition of convexity, which got me a monstrous expression which I did not manage to simplify
  • attempting to show $f$ is a norm (that went nowhere)
  • finding the Hessian (I did not get very far on this, as I wasn't sure how to properly derive and the just finding the gradient was difficult)

The fact that the function is of a vector, not a scalar is only complicating things. Any insight, strategies, or solutions to solve this problem? I'm totally puzzled!

$\endgroup$
  • $\begingroup$ By the common definition, $Q \succeq 0$ automatically assumes $Q$ is symmetric. $\endgroup$ – user1101010 Oct 16 '18 at 19:37
  • $\begingroup$ Oh, really? That means that I can take $x^T Qy$ to equal $y^T Qx$, right? I will keep trying using this information, although I'm still stuck for the moment. $\endgroup$ – Craveable Banana Oct 16 '18 at 19:46
  • $\begingroup$ even if $Q$ is not symmetric, $x^TQx = 0.5 x^T(Q+Q^T)x$ $\endgroup$ – LinAlg Oct 16 '18 at 22:03
5
$\begingroup$

Here is shorter proof. Since $f(x) = ||Ax + b||$ with $$A = \begin{pmatrix}Q^{1/2} \\ \bf{0}^T \end{pmatrix} \text{ and } b = \begin{pmatrix} \bf{0} \\ 1 \end{pmatrix},$$ which is just a convex function evaluated in an affine transformation of $x$, $f$ is convex. Here, $Q^{1/2}$ is the cholesky factor of $Q$.

$\endgroup$
3
$\begingroup$

As rightly stated in the comment by user9527, I assume that $Q = (q_{ij})_{i,j}$ is symmetric or $Q \geq 0$ does not make sense. First observe that $\langle x, y \rangle := x^T Qy$ is an inner product on $\mathbb{R}^n$, and hence we have the Cauchy-Schwarz inequality $$ \langle x, y \rangle^2 \leq (x^TQx)(y^TQy).$$

Then we compute the Hessian. $$f(x) = \sqrt{\sum_{i,j} q_{ij}x_ix_j + 1}$$ $$\frac{\partial f}{\partial x_k} (x)= \frac{1}{2 f(x)} \sum_j (q_{jk} + q_{kj}) x_j = \frac{1}{f(x)} (Qx)_k$$ $$\frac{\partial f}{\partial x_k \partial x_m} (x)= -\frac{1}{f(x)^3} (Qx)_k (Qx)_m + \frac{1}{f(x)} q_{km}$$ $$y^T H_f(x) y = \frac{1}{f(x)^3} \left( f(x)^2 \sum_{k,m} q_{km} y_ky_m - \sum_{k,m} (Qx)_k(Qx)_my_ky_m\right) = \frac{1}{f(x)^3} \left( f(x)^2 y^TQy - (y^T Qx)^2\right).$$

Using the fact that $f(x)^2 = x^TQ x + 1 \geq x^T Q x$, and the Cauchy-Schwarz inequality, we get $$y^T H_f(x) y \geq \frac{1}{f(x)^3} \left[(x^T Q x) (y^TQy) - (y^T Qx)^2\right] \geq 0.$$

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