14
$\begingroup$

According to Wikipedia, any quadratic function can be written as $z^TMz$, where $z$ is a column vector and $M$ is a symmetric real matrix. However, this quadratic function is strictly convex only when $M$ is symmetric positive definite. Why? I thought any quadratic function should be convex?

Doesn't $z^TMz>0$ shows only that the range of this function is greater than zero?

  1. Why isn't any symmetric matrix $M$ (which represents a quadratic function) convex?

  2. Why is it only the case that when $z^TMz > 0$ the function is strictly convex?

$\endgroup$
5
  • 2
    $\begingroup$ Suppose $M=\pmatrix{1&0\cr0&-1\cr}$. Then $M$ is symmetric and real, and $z^tMz=x^2-y^2$. Is $x^2-y^2$ convex? What's your definition of convex? $\endgroup$ Commented Oct 10, 2012 at 1:17
  • $\begingroup$ For function to be convex I mean: en.wikipedia.org/wiki/Convex_function $$f(tx_1+(1-t)x_2) <tf(x_1) +(1-t)f(x_2) $$ for any 0 < t < 1, x1 != x2. $\endgroup$
    – Jing
    Commented Oct 10, 2012 at 1:24
  • 1
    $\begingroup$ OK, so, does $f=x^2-y^2$ fit that definition? What if you pick points with $f(x_1)=f(x_2)=0$, say? $\endgroup$ Commented Oct 10, 2012 at 1:30
  • $\begingroup$ hmm... I am confused, can you give me some sketch of mathematical proof? f(x) is convex iff M(f(x)) is SGD ? thankx $\endgroup$
    – Jing
    Commented Oct 10, 2012 at 1:42
  • $\begingroup$ First, have you found an example to show that for the $M$ I gave, the function is not convex? Second, what is SGD? $\endgroup$ Commented Oct 10, 2012 at 1:59

2 Answers 2

6
$\begingroup$

UPDATE: As pointed out in the comments by @Erik, positive definiteness is a sufficient condition for strict convexity. However in these case, positive definiteness is indeed directly implied since the second derivative is a positive definitive matrix.

PREVIOUS ANSWER: For any twice differentiable function, it is strictly convex if and only if, the Hessian matrix is positive definite. You can find it from any standard textbook on convex optimization. Now here the function at hand is $z^TMz$ which is clearly twice differentiable (by virtue of being quadratic). Now the Hessian of this function is $M$ (please verify yourself, it helped me a lot to memorize it). So $M$ should be positive definite for that quadratic function to be convex.

$\endgroup$
1
  • 7
    $\begingroup$ The Hessian matrix does not need to be positive definite for a strictly convex function. Take the function $f(x) = \sum_{i=1}^Nx_i^4$, where $x = (x_1,\ldots,x_N)$; this has a Hessian matrix of $H(x) = 12\cdot\text{diag}(x_1^2,\ldots,x_N^2)$ which is only positive semi-definite (substitute $x=0$ to see this). Positive definiteness of the Hessian is only a sufficient condition for strict convexity, not a necessary one. A function is strongly convex if and only if its Hessian is positive definite. Your statement is true for quadratic forms, however. $\endgroup$
    – Erik M
    Commented Aug 30, 2015 at 3:47
1
$\begingroup$

Ok so here is my explanation using second order directional derivatives and hessian matrix.

1)Real Symmetric Hessian matrix $H$(at some point $x^{(0)}$) of our function $f(x):R^{n}\rightarrow R $ can be decomposed into $H=D\lambda D^{T}$ (eigendecomposition of symmetric matrix. $\lambda$ is identity matrix with eigenvalues of $H$ on its diagonal), which implies $D^{T}HD=\lambda$, which implies $d_{i}^{T}Hd_{i}=\lambda_{i}$ (where $d_{i}$ is i-th eigenvector of $H$ and $\lambda_{i}$ is corresponding eigenvalue, at point $x^{(0)}$)

2) Second order directional derivative in some direction $c$ is given by $c^{T}Hc$. In case $c$ equals to eigenvector of $H$, value of directional derivative is given by eigenvalue corresponding to $c$. In case $c$ is not equal to eigenvector, then directional derivative ($c^{T}Hc$) equals to weighted average of eigenvalues ( so value of directional derivative in any direction $c$ are bounded by minimal and maximal eigenvalues). Additionaly, eigenvector corresponding to maximal eigenvalue gives us maximal second order directional derivative, similarly eigenvector corresponding to minimal eigenvalue gives us smallest possible value of second order directional derivative.So maximal and minimal eigenvalues indicate the greatest and smallest possible value of second order directional derivative.

3) If Hessian is positive semi-definite then all its the eigenvalues are positive or zero. As a consequence second order directional derivative in any direction $c$ has also to be positive or zero (because their values are bounded by eigenvalues).

4) If second order directional derivatives are always positive or zero, then no matter what direction $c$ we will choose, second order directional derivative is positive or zero, and as a result curvature is positive or flat($c^{T}Hc>=0$). In univariate case: $f^{"}(x)>=0$ for every $x\ \epsilon\ R$. So function is convex (but not strictly, we can come across flat regions).

5) In this case we are talking about Hessian $H=H(x^{(0)})$ (in given point) !!!! So Hessian has to be positive semi-definite in every possible point $x^{(0)}$

6)If $H$ is positive definite then function is stritly convex

$\endgroup$

You must log in to answer this question.

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