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...