2. Introduction

Posted on In

in general, Hessian $H_f(\mathbb x)$ is not symmetric. But, if $f$ has continuous second order derivatives, then the Hessian matrix $H_f( \mathbb x)$ is symmetric.

Positive semidefinite: if $\mathbb x^T \mathbf A \mathbb x \ge 0, \forall \mathbb x \in \mathbb R^n$.

positive definite: if $\mathbb x^T \mathbf A \mathbb x \ge 0, \forall \mathbb x \neq 0$.

if $\mathbf A$ is a real symmetric $n\times n$ matrix.

  • if $\mathbf A$ is positive semidefinite $\iff$ every eigenvalue of $A$ is nonnegative $\lambda > 0$.
  • $\lambda_{\min} (\mathbf A) | \mathbb x |^2 \leq \langle \mathbb x, \mathbf A \mathbb x\rangle \leq \lambda_{\max} (\mathbf A) |\mathbb x |^2, \ \forall \mathbb x \in \mathbb R^{n\times n}$

Inner product of matrix:

  • $A,B \in \mathbb R^{m\times n}$, have $\langle A,B \rangle = \sum\limits_{i=1}^{m} \sum\limits_{j=1}^{n} A_{ij} B_{ij} = \operatorname{Tr}(A^TB)$

Frobenius norm:

  • $|A|F = \sqrt{ \sum\limits{i=1}^{m} \sum\limits_{j=1}^{n} |A_{ij}|^2} = \sqrt{\operatorname{Tr}(A^TA)}$

Sherman-Morrison-Woodbury (SMW) formula

Suppose $U,V \in \mathbb R^{n\times p}$ and $| UV^T | <1$, Then
$$
(I+UV^T)^{-1} = I-UG^{-1} V^T \quad \in \mathbb R^{n\times n}
$$
where $G=I_p + V^TU \in \mathbb R^{p\times p}$

When $n$ is large, it’s hard to compute the inverse of $(I+UV^T)$. But if using the SMW formula, it’s easy to compute by transforming it as $I-UG^{-1} V^T$, because the inverse of $G$ is easy to compute ($p$ is small).

If $(I+UV^T)$ is nonsingular, than the SMW formula $(I+UV^T)^{-1} = I-UG^{-1} V^T$holds without requiring $| UV^T | <1$

Bounded: $|\mathbb x | \leq M, \forall \mathbb x \in S$. If $C_1, C_2$ are bounded, then $C_1 \cup C_2$ is bounded.

Closed: $\lim\limits_{n\rightarrow \infin} \mathbb x_n \in S$. If $C_1, C_2$ are closed, then $C_1\cap C_2$ is closed.

Prove method: if function $g$ is continuous, then set $S={\mathbb x\in \mathbb R^n | g(\mathbb x) \le 0}$ is closed. Or $S={\mathbb x\in \mathbb R^n | g(\mathbb x) \ge 0}$ is closed. Or $S={\mathbb x\in \mathbb R^n | g(\mathbb x) = 0}$ is closed.

Example:

Prove $C = \left{ \begin{pmatrix} x \ x^2 \end{pmatrix} \in \mathbb R^2 \right}$ is closed.

Solution:
$$
C = \left{ \begin{pmatrix} x \ x^2 \end{pmatrix} \in \mathbb R^2 \right} = \left{ \begin{pmatrix} x_1 \ x_2 \end{pmatrix} \in \mathbb R^2 \quad \vert \quad g(\mathbb x) := x_2-x_1^2 = 0 \right}.
$$
since $g$ is continuous, so $C$ is closed.

Compactness: Closed + Bounded

Coercive function:
$$
\lim\limits_{|\mathbb x| \rightarrow \infty} f(\mathbb x) = +\infty
$$
Which means that the function value $f(\mathbb x)$ will increase without bound as $\mathbb x$ moves away from the origin in all possible directions.

==Existence of optimal solution:==

  1. a continuous function $g:\mathbb R^n \rightarrow \mathbb R$ on a nonempty closed and bounded set $S \subset \mathbb R^n$ has a global maximum and a global minimum point in $S$.

  2. $f:\mathbb R^n \rightarrow \mathbb R$ is continuous function. If $f$ is coercive, then $f$ has at least one global minimizer. (when x is not bounded)

A stationary point $\mathbb x^*$ with $H_f(\mathbb x^*)$ positive semi-definite, the status of $\mathbb x^*$ can only be determined by analyzing $f(\mathbb x^*)$ is a neighborhood of $\mathbb x^*$. Can obtain a global minimizer by comparing the objective value at the stationary points.