2. Introduction

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,\mathrm{\forall }\mathbb{x}\in {\mathbb{R}}^n$.

positive definite: if ${\mathbb{x}}^T\mathbf{A}\mathbb{x}\ge 0,\mathrm{\forall }\mathbb{x}\ne 0$.

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

• if $\mathbf{A}$ is positive semidefinite $⟺$ every eigenvalue of $A$ is nonnegative $\lambda >0$.
• ${\lambda }_{min}(\mathbf{A})|\mathbb{x}{|}^2\le ⟨\mathbb{x},\mathbf{A}\mathbb{x}⟩\le {\lambda }_{max}(\mathbf{A})|\mathbb{x}{|}^2,\mathrm{\forall }\mathbb{x}\in {\mathbb{R}}^{n\times n}$

Inner product of matrix:

• $A,B\in {\mathbb{R}}^{m\times n}$, have $⟨A,B⟩=\sum _{i=1}^m\sum _{j=1}^n{A}_{ij}{B}_{ij}=\mathrm{Tr}(A^{T}B)$

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 $|U{V}^T|<1$, Then
$$(I+U{V}^T{)}^{-1}=I-U{G}^{-1}{V}^T\in {\mathbb{R}}^{n\times n}$$
where $G=I_p+V^{T}U\in {\mathbb{R}}^{p\times p}$

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

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

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

Closed: $\underset{n\to \text{infin}}{lim}{\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 $\text{Missing or unrecognized delimiter for left}$ is closed.

Solution:
$$\text{Missing or unrecognized delimiter for left}$$
since $g$ is continuous, so $C$ is closed.

Compactness: Closed + Bounded

Coercive function:
$$\underset{|\mathbb{x}|\to \mathrm{\infty }}{lim}f(\mathbb{x})=+\mathrm{\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\to \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\to \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}}^{\ast }$ with $H_f({\mathbb{x}}^{\ast })$ positive semi-definite, the status of ${\mathbb{x}}^{\ast }$ can only be determined by analyzing $f({\mathbb{x}}^{\ast })$ is a neighborhood of ${\mathbb{x}}^{\ast }$. Can obtain a global minimizer by comparing the objective value at the stationary points.