1
$\begingroup$

Let $f:\mathbb R^n \to \mathbb R$ be a twice differentiable function with $\mathbf{dom}\,f$ open. The Hessian of $f$ is defined as usual to be the matrix $\nabla^2f(x) \in \mathbb R^{n \times n}$ with entries

$$\nabla^2f(x)_{ij}=\frac{\partial^2f(x)}{\partial x_i\partial x_j},\quad i,j = 1,2,\ldots,n,$$

which we assume exists at each point $x \in \mathbf{dom}\,f$. Boyd and Vandenberghe (2009) state that the function $f$ is convex if and only if $\mathbf{dom}\,f$ is convex and $\forall x \in \mathbf{dom}\,f:\nabla^2 f(x) \succeq 0$. Here, $\succeq$ denotes the componentwise inequality.

Question: Are the above conditions necessary and sufficient for convexity?

Additional notes: It appears the above definition is different than the usual definition of convexity for multivariate functions, which states that $f(x)$ is convex if and only if $\nabla^2f(x)$ is positive semidefinite. Recall that a symmetrix matrix $M$ is called positive semidefinite if the scalar $z'Mz$ is weakly positive for any nonzero vector $z \in \mathbb R^n$. Clearly, not every matrix with only positive entries is positive semidefinite, e.g. \begin{align} M = \left[ {\begin{array}{cc} 1 & 4 \\ 4 & 1 \\ \end{array} } \right] \end{align} Similarly, a matrix may have negative entries yet be positive semidefinite, e.g. \begin{align} M = \left[ {\begin{array}{cc} 1 & -1 \\ -1 & 4 \\ \end{array} } \right] \end{align}

In conclusion, it seems that the stated condition $\forall x \in \mathbf{dom}\,f:\nabla^2 f(x) \succeq 0$ is fundamentally different from the condition that $\nabla^2f(x)$ be positive semidefinite.

$\endgroup$
  • 2
    $\begingroup$ As far as I remember, Boyd & Vandenberghe use $\succeq 0$ to denote positive semi-definiteness rather than a component-wise comparison. Where exactly you found this in the book? $\endgroup$ – M. Winter May 8 '18 at 14:30
  • $\begingroup$ I found it on p.32 of the book, or slide 2-9 (on "polyhedra"). Also, on p.14 of the book they state that $\succeq$ denotes generalized inequality, i.e. componentwise inequality for vectors, and matrix inequality for matrices. I guess "matrix inequality" should be interpreted as "the difference between the two matrices is positive semidefinite"? $\endgroup$ – mcasolin May 8 '18 at 14:36
  • $\begingroup$ For the record, this is not the definition of convexity, only an equivalent. The definition is that the domain is convex and $ f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) $ for any $x,y$ and $0 \leq \lambda \leq 1$. $\endgroup$ – Chappers May 8 '18 at 14:40
  • $\begingroup$ Agreed, Chappers. $\endgroup$ – mcasolin May 8 '18 at 16:43
1
$\begingroup$

Boyd & Vandenberghe use the notation $X\succeq 0$ to denote that a matrix $X$ is positive semi-definite (or more general: $X\succeq Y\Leftrightarrow X-Y$ is positive semi-definite). This becomes more clear in "2.2.5 The positive semidefinite cone" where they define the positive semi-definite cone as

$$\mathbf S_+^n=\{X\in \mathbf S^n\mid X\succeq 0\}.$$

The initial definition of $\succeq$ for matrices as "matrix inequality" (in "1.6 Notation") was indeed a bit vague.

So these definitions agree.

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