1 Norms

1.1 l^p norms for p ≥ 1 satisfy the triangle inequality (based on Royden)

We wish to show that _p ≤_p + _p for p ≥ 1.

For p = ∞, this is max_i≤ max_i ≤ max_i + max_i. □

For 1 ≤ p < ∞, first assume without loss that x,y≠0 (the inequality is trivial if either vector is zero). Let α = _p, and β = _p, from which we define x₀ = x, and y₀ = y. Then:

Since f = ^p is convex for 1 ≤ p < ∞, and noting that , ≥ 0 and + = 1:

Recalling that _p^p = _p^p = 1:

WLOG But α = _p and β = _p, so:

□

1.2 Norms are convex

A norm, by definition, satisfies the triangle inequality. Suppose that is a norm. Then, if λ :

2 Hessians

Suppose that f : ^d → is twice differentiable. The gradient of f is the vector of partial derivatives:

The Hessian is the matrix of partial second derivatives:

Note that since = , this matrix is symmetric. It’s important to realize that, like a derivative (or gradient), the Hessian is a function of the vector x–it takes on different values on different parts of the domain.

A word on notation: ▽² is frequently used for the Laplacian operator ▽²f = ∑ _i=1^d, but not in this class.

2.1 Positive definiteness

An eigenvalue is a scalar λ which satisfies the following:

For some x≠0 (which is called an eigenvector). Note that if the above holds for x, it holds for αx where α≠0 is an arbitrary scalar. That is, the scale of eigenvectors is irrelevant. A n × n symmetric matrix will always have exactly n eigenvalue/eigenvector pairs, though the eigenvalues are not necessarily distinct. Additionally, the eigenvectors may always be taken to be orthogonal.

For small matrices, we may solve for the eigenvalues & eigenvectors explicitly:

Soving for x₁ gives that x₁ = x₂ and x₁ = x₂, so that:

A matrix is positive definite if all of its eigenvalues are strictly positive, and positive semi-definite if they are all nonnegative. Is the above matrix positive definite? (yes)

One simple test for positive (semi-)definiteness is that a matrix A is positive (semi-)definite if x^TAx is positive (nonnegative) for all x≠0.

A twice-differentiable function is convex if its Hessian is positive semidefinite everywhere, and is strictly convex if its Hessian is positive definite.

The definitions of negative (semi-) definite and (strictly) concave are the same, with the signs reversed.

2.2 Quadratic-over-linear is convex (page 73 of Boyd)

Consider f = for y > 0. Then:

And:

Which we may write as:

By inspection, one eigenvector of is , with eigenvalue y² + x² ≥ 0:

While the other eigenvalue is zero, since has rank 1 (eigenvector ). Since ≥ 0 for y > 0, this gives that:

Showing that f is convex. Is it strictly convex? (no)

2.3 Arithmetic-geometric means inequality

Consider f = for x > 0. We may write log f = ∑ _i=1ⁿ log x_i. By the concavity of the logarithm:

Exponentiating both sides gives:

Which is the arithmetic-geometric means inequality.

2.4 Geometric mean is concave (page 74 of Boyd)

Again consider f = for x > 0. Its gradient is:

And its Hessian is:

Which we may write as:

Consider v^T ▽²fv:

Note that we may write ∑ _i=1ⁿ as:

And by the Cauchy-Schwarz inequality (² ≤₂²₂²) with a = 1 and b_i = :

So that v^Tv ≤ 0, showing that f is concave.