基础术语与定义

1、向量和范式（vectors and norms）

1.1 向量定义

一个点或者向量 $x \epsilon R^{n}$ , 通常用小写字母表示，若不加说明，默认为列向量，即

$x=\begin{bmatrix}x1 \\ x2 \\ ... \\ xn \end{bmatrix} \, \, \, \, x_{i}\epsilon R\, \, \, \, \, \, \, \forall i$

1.2 欧几里得内积（Euclidean inner product）

性质

非负性（Positivity） $\left \langle x,x\right \rangle \geq 0\, \, and\, \left \langle x,x\right \rangle=0\,\: if\,\: and\,\: only\, \, if\, \, x=0$
对称性（Symmetry） $\left \langle x,y\right \rangle =\left \langle y,x\right \rangle$
线性（Linearity） $\left \langle \alpha x+\beta y,z\right \rangle =\alpha \left \langle x,z\right \rangle+\beta \left \langle y,z\right \rangle\, \, \, \: \: \forall \alpha ,\beta \epsilon R\, \, \, \, and\, x,y,z\epsilon R^{n}$

内积往往用来表示角度： $\left \langle x,y \right \rangle = x_{1}y_{1}+x_{2}y_{2}+...+x_{n}y_{n}=\left \| x \right \|\left \| y \right \|\cdot {\color{DarkRed} cos\left \langle x,y \right \rangle}$

1.3 欧几里得范式（Euclidean norm）

$\left \| x \right \|_{2} = \left \| x \right \|=\sqrt{\left \langle x,x \right \rangle}=\sqrt{x^{T}x}=\sqrt{x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}}$

性质：

非负性（Positivity） $\left \| x \right \|\geq 0 \, and\, \left \| x \right \|=0\,\: if\,\: and\,\: only\, \, if\, \, x=0$
同质性（Homogeneity） $\left \| \alpha x \right \|=\left | \alpha \right |\left \| x \right \|$ 其中 $\alpha$ 为常数。
三角不等性（Triangle inequality） $\left \| x+y \right \|\leq \left \| x \right \|+\left \| y \right \|$
柯西不等性（Cauchy-Schwarz inequality） $\left | \left \langle x,y \right \rangle \right |\leq \left \| x \right \|\left \| y \right \|$

其中，欧几里得范式又称为二阶范式。

其他范式：

一阶范式（ $l_{1-norm}$ ） : $\left \| x \right \|_{1}=\left | x_{1} \right |+\left | x_{2} \right |+...+\left | x_{n} \right |$

p阶范式 ( $l_{p-norm}$ ) : $\left \| x \right \|_{p}= \left [ \sum_{i=1}^{n}\left | x_{i}^ \right |^{p} \right ]^{1/p}=\sqrt[p]{\left | x_{1} \right |^{p} + \left | x_{2} \right |^{p} +...+ \left | x_{n} \right |^{p}}$

无穷阶范式( $l_{\infty -norm}$ ) : $\left \| x \right \|_{\infty } = max_{1\leq i\leq n} \left | x_{i} \right |$

（其中，一阶范式又称为曼哈顿距离，对应在欧几里得空间的固定直角坐标系上两个点所形成的线段对轴产生的投影的距离总和，如点P1(x,y)，P2(x,y)的一阶范式为 ||x-y|| = |x1-x2| + |y1-y2|

但要注意的是一阶范式依赖坐标系的转度，无穷阶范式又称为切比雪夫距离，而p阶范式是所有范式的通用表示，即一阶二阶无穷阶都可以用p阶表示）

2、集合

2.1 上确界、下确界（supremum/infimum）

if $X \subset R$ then sup X = max X
if $X \subset R$ then inf X = min X

2.2 开集、闭集、有界集、邻域、紧集

开集：在集合的任何一个点的任意方向走充分小的距离后仍然在开集内
闭集：在集合外的任意一点往任意方向走充分小的距离后仍然在闭集外

（ $-\infty ,2$ ）是开集
（ $-\infty ,2$ ] 是闭集
$(-\infty , 2 )\cup [2 , \infty)$ 是非开非闭集

邻域( $B_{\varepsilon }$ ): $B_{\varepsilon }(x)=\left \{ y\epsilon R^{n}:\left \| x-y \right \| \right \ < \varepsilon \}\: \: \: \: for \, x\epsilon R^{n},\varepsilon >0$
有界集 (bounded set): $X\epsilon R^{n} \ is \ bounded\ if\ \exists B \epsilon R \, with\, \left \| x \right \|\leq B\, \, for\ all\ x\epsilon X$
有界的闭集叫紧集（compact）

3、局部最小点和全局最小点

local minimal: 存在一个点x*属于可行集X，如果存在 $\varepsilon> 0$ 使得 f(x) $\geq$ f(x*) 恒成立，其中 $x\, \epsilon X\cap B_{\varepsilon }(x^{*})$
strict local minimal: 存在一个点x*属于可行集X，如果存在 $\varepsilon> 0$ 使得 f(x) $>$ f(x*) 恒成立，其中 $x\, \epsilon (X\cap B_{\varepsilon }(x^{*}))\setminus \left \{x^{*} \right \}$
global minimal: 对于所有的 $x\, \, \epsilon \, \, X$ ，都有 f(x) $\geq$ f(x*)
strict global minimal: 对于所有的 $x\, \, \epsilon \, \, X \setminus \left \{ x^{*} \right \}$ ,都有 f(x) $>$ f(x*)

目标函数求最小值和求最大值是等同的，只需要将大于号换成小于号即可。

求最大值和求最小值也是可以互换的，max f(x) $\Leftrightarrow$ min -f(x)

4、线性与仿线性（affine-linear）

如果一个函数 $f:R^{n}\rightarrow R^{m}$ 满足 $f(\alpha x+\beta y) = \alpha f(x) + \beta f(y),\, \, \, \forall x,y\epsilon R^{n},\, \, \alpha ,\beta \epsilon R$ ,则称f(x)为线性

如果一个函数可以用 $f(x)-b$ 表示，其中f(x)是线性函数 , $b\, \, \epsilon\, \, R^{m}$ ，则称该函数为仿线性。

如： $g(x) = Ax - b, A\, \epsilon R^{m\times n},b\, \epsilon R^{m}$ 就是一个仿线性函数。
线性优化问题（LP）的标准形式：
$min_{x\epsilon R^{n}}\,\, \, c^{T}x=\sum_{i=1}^{n}c_{i}x_{i}\, \, \,\, \, \, \, \, \, s.t.\,\, \, \, a_{i}^{T}x\leq b_{i}\, \, ,\, \, i=1,2...m$
即目标函数是线性，限制函数是线性或者是仿线性。

未完待续...

原文链接：https://blog.csdn.net/secular_/article/details/111827462