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$
4
  • 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
    Commented May 8, 2018 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
    Commented May 8, 2018 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
    Commented May 8, 2018 at 14:40
  • $\begingroup$ Agreed, Chappers. $\endgroup$
    – mcasolin
    Commented May 8, 2018 at 16:43

1 Answer 1

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$

You must log in to answer this question.

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