Theorem. A twice continuous differentiable function $f:\mathbb{ R } ^n \mathbb{ R } ightarrow \mathbb{ R } $ is convex if and only if ∇2f(x)⪰0\nabla^2 f(x) \succeq 0 for x∈Rnx \in \mathbb{ R } ^n.

Proof. We use that fact that ff is convex iff f(y)≥f(x)+∇f(x)T(y−x)f(y) \ge f(x) + \nabla f(x)^T (y - x) for all y,x∈Rny, x \in \mathbb{ R } ^n.

  1. If: For x,y∈Rnx, y \in \mathbb{ R } ^n, exists z=λx+(1−λ)yz = \lambda x + (1 - \lambda) y, where λ∈[0,1]\lambda \in [0, 1], such that (by Taylor series expansion and Lagrange reminder)
f(y)=f(x)+∇f(x)T(y−x)+12(y−x)T∇2f(z)(y−x)≥f(x)+∇f(x)T(y−x) \begin{aligned} f(y) &= f(x) + \nabla f(x)^T (y - x) + \frac{1}{2} (y - x)^T \nabla^2 f(z) (y - x) \\ &\ge f(x) + \nabla f(x)^T (y - x) \end{aligned}

  1. Only If: Rearranging the Taylor series we get,

    f(y)−f(x)−∇f(x)T(y−x)=12(y−x)T∇2f(z)(y−x) \begin{aligned} f(y) - f(x) - \nabla f(x)^T (y - x) &= \frac{1}{2} (y - x)^T \nabla^2 f(z) (y - x) \end{aligned}

    Which implies that,

    (y−x)T∇2f(z)(y−x)≥0 \begin{aligned} (y - x)^T \nabla^2 f(z) (y - x) \ge 0 \end{aligned}

    Since ∇2f(x)\nabla^2 f(x) is continuous, ∀ϵ>0,∃δ>0\forall \epsilon > 0, \exists \delta > 0, such that ∀z∈B(x,δ)\forall z \in \mathbb{B}(x, \delta), it holds that

    ∥∇2f(z)−∇2f(x)∥F≤ϵ2/n4 \| \nabla^2 f(z) - \nabla^2 f(x) \|_F \le \epsilon^2 / n^4

    where ∥A∥F≐Tr(ATA)\| A \|_F \doteq Tr(A^TA) for A∈Rn×nA \in \mathbb{ R } ^{n \times n}. Note that ∥A∥F≤ϵ2/n4\| A \|_F \le \epsilon^2 / n^4 implies that Ai,j≥−ϵ/n2A_{i,j} \ge -\epsilon / n^2.

    Without lose of generality, suppose that s≐y−xs \doteq y - x is a unit vector. Then x+δs∈B(x,δ)x + \delta s \in \mathbb{B}(x, \delta), and z∈[x,x+δs]⊂B(x,δ)z \in [x, x + \delta s]\subset \mathbb{B}(x, \delta) (where [x,x+δs][x, x+ \delta s] is the line segment between xx and x+δsx + \delta s). It follows:

    δ2sT(∇2f(x)−∇2f(z))s≥∑i,jϵn2δ∣si∣⋅δ∣j∣=δϵn2(∣s∣)2 \begin{aligned} \delta^2 s^T \left(\nabla^2 f(x) - \nabla^2 f(z) \right) s &\ge \sum_{i, j} \frac{\epsilon}{n^2} \delta |s_i| \cdot \delta | _j| \\ &= \delta \frac{\epsilon}{n^2} (|s|)^2 \end{aligned}

    where ∣s∣=∑i∈[n]∣si∣≤n∥s∥|s| = \sum_{i \in [n]} |s_i| \le \sqrt n \| s \|. Therefore,

    sT(∇2f(x)−∇2f(z))s≥−ϵ∥s∥2=−ϵ \begin{aligned} s^T \left(\nabla^2 f(x) - \nabla^2 f(z) \right) s &\ge -\epsilon \| s \|^2 = -\epsilon \end{aligned}

    Finally,

    sT∇2f(x)s=sT∇2f(z)s+sT(∇2f(x)−∇2f(z))s≥−ϵ \begin{aligned} s^T \nabla^2 f(x) s &= s^T \nabla^2 f(z) s + s^T \left(\nabla^2 f(x) - \nabla^2 f(z) \right) s \\ &\ge -\epsilon \end{aligned}

    As ϵ\epsilon can be arbitrary small, it hold that sT∇Tf(x)s≥0s^T \nabla^T f(x) s \ge 0. This holds for any ∥s∥=1\| s \| = 1, it concludes that ∇2f(x)⪰0\nabla^2 f(x) \succeq 0.

□\square