A short story of positive semi-definite matrices (PSD).

A is symmetric if A equals A^T and

- It has only real eigenvalues,

- Always diagonalizable,

- Orthogonal eigenvectors.

The symmetric matrix A is positive definite if all its eigenvalues are positive.

The symmetric matrix A is PSD if all its eigenvalues are non negative.

Any of the following checks is sufficient:

- All eigenvalues >= 0,

- Energy x^T S x >= 0,

- Leading determinants have to be >= 0,

- All pivots in elimination >= 0.

Explore: read here and watch here.

Fun facts from here:

- All the diagonal elements of PSD are non-negative, thus, tr(A)>=0.

hint: try putting standard basis vector in x^T S x >=0.

- off-diagonal elements Aij <= Aii and Ajj diagonal elemetns.

hint: use x with two non-zero elements.

- The set of PSD matrices is a convex cone in R^n(n+1)/2.

hint: convex combination aA+bB, a,b>0 is in, -A is not in S.

Some convex functions

-Affine functions

Both convex and concave

-Norms

All norms ||x||_p are convex for p >= 1.

-Functions on matrices

-Affine f(X) = tr(A^T X) + b = (sum of Aij Xij) + b

-Spectral norm f(X) = ||X||_2 = root of largest eigenvalue of X^T X.

-Quadratic

x^T P x + q^T x + r with (P being symmetric in n-dimensions) is

convex if P is PSD, i.e., its Hessian H of P is >= 0.

- Least squares objective

||Ax - b||^2 _2 is convex for any A.

- Quadratic-over-linear

f(x, y) = x^2/y is convex for y > 0.

- Log-sum-exp or soft-max

f(x) = log (sum of exp (x_k)) for k in 1 to n.

- Geometric mean

f(x) = n-th root of (product of x_k's) for x_k being non-negative.

``A quick validation could be to check if a function a convex,

it is better be convex in each variable separately. Obviously!

diagonals of H >= 0 as H >=0, and thus the converse is completely false .``

Fun fact:

Relation between convex functions and convex sets is established from epigraph. f is convex if and only if epigraph of f is a convex set.

Explore: read here and watch here

Operations that preserve convexity

Now that we have learned some basic convex functions (atoms), if we encounter a new function f, it is preferred to identify we can decompose f in terms of atoms. The operation between atoms can help us get hints about the convexity of overall combination, i.e., f.

- Non-negative multiple

c x f is a convex for c >= 0.

- Sum

f1 + f2 is convex if f1,f2 convex (extends to infinite sums, integrals)

- Composition with affine function

f (Ax + b) is convex if f is convex.

- Pointwise maximum

if f_i's are convex, then f(x) = max {f1(x), ..., f2(x)} is convex.

eg. max of piecewise linear functions max_i (a_i^T x + b_i) is convex.

sum of r largest components of x in n-dimensions.

-Composition with scalar functions

f(x) = h(g(x))

f is convex if

g is convex, h is convex, h is non-decreasing, or

g is concave, h is convex, h is non-increasing.

can be proved by f''(x) = h''(g(x))g'(x)^2 + h'(g(x))g''(x).

Note: the rules hold even if h', h'', g', g'' do not exist!

Slogan to remember:

``A convex increasing function of a convex function is convex.``

Note: increasing here refers to non-decreasing, a great example is here.

Duality

- Lagrangian augments objective function with the weighted sum of constraints in the standard form described by Boyd in chapter 5. The weights are called dual variables or Lagrange multiplier.

- Lagrange dual function (or just dual) g is infimum of Lagrangian over x. Thus, it becomes a function of lambda and nu.

- What if g is unbounded below in x?--The dual takes minus infinity value.

- g is concave?--Yes, because it is pointwise minimum of affine function and g is concave irrespective if the original problem is not convex.

Feasibility problem

- min {0: given inequality constraints are convex f(x)<=0, equality are affine h(x)=0}

- Useful?--Find if a given set completely lies inside a polyhedron. Reformulate it to be a feasibility convex problem to find if there exists any element in the set that lies outside the polyhedron.

-Many more applications to come...