What is the second-order test for convexity of a twice-differentiable function?

## The criterion Let `f` be twice continuously differentiable on an **open convex** domain `D` in `R^n`, with Hessian `H(x)` (the matrix of second partial derivatives at `x`). Then ``` f is convex on D <=> H(x) is positive semidefinite for every x in D ``` A symmetric matrix `H` is **positive semidefinite (PSD)** when `z^T H z >= 0` for every vector `z`, equivalently when all its eigenvalues are `>= 0`. It is **positive definite (PD)** when `z^T H z > 0` for every `z != 0`, equivalently when all eigenvalues are strictly positive. In one variable the Hessian is the single number `f''(x)`, and the criterion is the familiar `f''(x) >= 0` on the whole interval. ## Three things candidates routinely get wrong **1. It is a condition at every point, not at one point.** Convexity is a global property of the function on its domain, so the test must hold throughout. `f(x) = x^3` satisfies `f''(0) = 0 >= 0` at the origin, yet `f''(x) = 6x < 0` for `x < 0`, and the function is not convex on the real line. Verifying the Hessian only where you happen to have landed proves nothing about the shape elsewhere. **2. PSD is not `all entries are non-negative`.** The matrix with rows `(1, 2)` and `(2, 1)` has all-positive entries but eigenvalues `3` and `-1`, so it is indefinite. Conversely the matrix with rows `(1, -1)` and `(-1, 1)` has a negative entry and is PSD, with eigenvalues `2` and `0`. Use the quadratic-form test `z^T H z >= 0`, the eigenvalue signs, or the leading-principal-minor rules — never the entry signs. **3. Strict convexity is not equivalent to PD.** A positive definite Hessian at every point **implies** strict convexity, but the converse fails. `f(x) = x^4` is strictly convex on the real line, yet `f''(x) = 12x^2` vanishes at `x = 0`. So `PD everywhere => strictly convex => convex <=> PSD everywhere`, with the first arrow one-directional. ## The first-order alternative When `f` is differentiable but you do not want second derivatives, there is an equivalent first-order characterisation: ``` f is convex <=> f(y) >= f(x) + grad f(x) . (y - x) for all x, y in D ``` In words: the tangent hyperplane at any point is a **global underestimator** of the function. This is the differentiable counterpart of the chord condition, and it is often the cleanest thing to invoke in a proof, because it turns a local object (the gradient) into a global bound. ## Worked example: the squared-error surface Take `f(w) = ||X*w - y||^2` as a function of the parameter vector `w`, with `X` and `y` fixed. Expanding gives `f(w) = w^T (X^T X) w - 2*y^T X w + y^T y`, a quadratic in `w`. Its Hessian is the constant matrix `2 * X^T X`, and for any vector `z`, ``` z^T (X^T X) z = (X z)^T (X z) = ||X z||^2 >= 0 ``` So the Hessian is PSD everywhere, for any `X` whatsoever, and the surface is convex in the parameters. It is **strictly** convex precisely when `||X z|| > 0` for all `z != 0`, i.e. when `X` has full column rank; with collinear or duplicated columns there are directions `z` along which the surface is perfectly flat, and the Hessian is singular. A second standard example is the logistic log-loss `g(z) = log(1 + exp(-z))` viewed as a function of the score `z`. Its second derivative is `s(z)*(1 - s(z))` where `s(z) = 1/(1 + exp(-z))`, and that product is strictly positive for every real `z`, so `g` is strictly convex in its argument. Composing a convex function with an **affine** map preserves convexity, so the surface remains convex when the score is a linear function of the parameters. ## Convexity-preserving constructions The second-order test is a checker; in practice you usually build convexity instead. Non-negative weighted sums of convex functions are convex; composition with an affine map is convex; and the pointwise maximum of convex functions is convex. Those three rules, plus a small library of known-convex atoms, cover most objectives you will meet without your ever differentiating twice.