最优化
最优化从一组可行点中找到“最佳”解决方案。
一个优化问题的形式是最小化（或最大化）目标函数，受制于约束条件： $$ \begin{array}{ll}\mathrm{Minimize}&f(x) \\ \mathrm{subject~to}&x\in\Omega.\end{array} $$
- $x\in\mathbb{R}^n$ 被称为决策变量。
- $f$ 被称为目标函数。
- $\Omega\subseteq\mathbb{R}^n$ 被称为约束集 / 可行集 / 可行区域。
在不失一般性的情况下，可以假设 $G$ 是对称的：
对于任何 $H\in\mathbb{R}^{n\times n}$ (非对称) 和 $x\in\mathbb{R}^n$，我们有：
$$\lbrack x^THx\rbrack_{1\times 1}=\lbrack x^THx\rbrack^T_{1\times 1}=x^TH^Tx$$
因此：
$$x^THx=x^TH^Tx=\frac12x^T(\underbrace{H^T+H}_{\text{对称矩阵 $G$}})x.$$
对于 $f(x)=\frac12x^TGx+c^Tx+\beta$ 其中 $G\in\mathbb{R}^{n\times n}$ 是对称的, 我们有:
$$\nabla f(x)=Gx+c.$$
下确界
$l=\inf S, \inf\emptyset=\infty$
令 $S\subseteq\mathbb{R}$ 为非空集。 我们有 $l\in[-\infty, \infty)$ 是 $S$ 的下确界，如果：
- 对于任意 $s\in S, s \geq l$
- 对于任意 $\zeta>l(\zeta\in\mathbb{R})$，可以找到 $s\in S$ 使得 $s<\zeta$
下确界是比 $S$ 中所有元素都小的最大数。
将集合的下确界值称为最优值。
范数
常见向量范数
- $l_1$ norm: $\vert\vert x\vert\vert_1:=\sum_{i=1}^{n}|x_i|\quad$ (sum of abs value)
- $l_2$ norm: $\vert\vert x\vert\vert_2:=\sqrt{\sum_{i=1}^{n}|x_i|^2}\quad$ ($\vert\vert x\vert\vert_2^2=\begin{bmatrix}x1&x2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}=x^Tx$)
- $l_\infty$ norm: $\vert\vert x\vert\vert_\infty:=\max_{i\leq i\leq n}|x_i|\quad$ (max abs value)
常见矩阵范数
$\vert\vert A\vert\vert_1=\underbrace{\max_j\sum_{i=1}^{n}|a_{ij}|}_{\text{maximum of the $l_1$ norms of columns}}$
- induced matrix norm
$\underset{||x||_1=1}{\max}||Ax||_1$
$\vert\vert A\vert\vert_2=\underbrace{\sqrt{\lambda_{max}(A^TA)}}_{\text{maximum eigenvalue of $A^TA$}}$
- induced matrix norm
$\underset{||x||_2=1}{\max}||Ax||_2$
$\vert\vert A\vert\vert_\infty=\underbrace{\max_i\sum_{j=1}^{n}|a_{ij}|}_{\text{maximum of the $l_1$ norms of rows}}$
- induced matrix norm
$\max_{\vert\vert x\vert\vert_\infty=1}||Ax||_\infty$
$\vert\vert A\vert\vert_F=\underbrace{\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{n}|a_{ij}|^2}}_{\text{known as the Frobenius norm}}$
对于对称矩阵 A
$$\underset{||x||=1}{\min}x^TAx=\lambda_{\min}(A)$$
$$\underset{||x||=1}{\max}x^TAx=\lambda_{\max}(A)\xlongequal[]{if A\succ0}||A||_2$$
正定矩阵
半正定矩阵
令 $A\in\mathbb{R}^{n\times n}$ 为对阵矩阵，如果对于所有 $x\in\mathbb{R}^{n}$，有 $x^TAx\geq0$，则称 $A$ 为半正定矩阵，记作
$A\succeq0$
Example:
$$A=\left[\begin{matrix}3&1\\1&2\end{matrix}\right]$$
$$x^TAx=\left[\begin{matrix}x1&x2\end{matrix}\right]\left[\begin{matrix}3&1\\1&2\end{matrix}\right]\left[\begin{matrix}x1\\x2\end{matrix}\right]$$
$$=3x_1^2+2x_1x_2+2x_2^2$$
$$=2x_1^2+(x_1+x_2)^2+x_2^2\geq0$$
正定矩阵
令 $A\in\mathbb{R}^{n\times n}$ 为对阵矩阵，如果对于所有 $x\in\mathbb{R}^{n}$\{0}，有 $x^TAx>0$，则称 $A$ 为正定矩阵，记作 $A\succ0$
if $D\succ0$ (正定)
$d=-D\nabla f(x)$ 是一个下降方向
泰勒定理
带余项
假设 $f$ 在包含 $[a,b]$ 的一个开区间上 (n+1) 阶可导。则： $$ f(b) = f(a) + f’(a)(b-a) + \frac{f’’(a)}{2!}(b-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(b-a)^n + \frac{f^{(n+1)}(\xi)}{(n+1)!}(b-a)^{n+1} $$ 其中 ${\xi \in (a,b)}$.
高维带余项
令 $f\in C^1(\mathbb{R}^n)$, $x$ 和 $y\in\mathbb{R}^n$。则存在 $\xi\in{(1-s)x+sy:s\in(0,1)}$ 使得 $$f(y)=f(x)+[\nabla f(\xi)]^T(y-x).$$
令 $f\in C^2(\mathbb{R}^n)$, $x$ 和 $y\in\mathbb{R}^n$. 则存在 $\xi\in {(1-s)x + sy : s \in (0,1)}$ 使得 $$f(y) = f(x) + [\nabla f(x)]^T (y - x) + \frac{1}{2}(y - x)^T \nabla^2 f(\xi) (y - x). $$
最后修改于 2023-09-22