最优化方法
最优化方法
1 引言
1.1 基础概念
- 基础数学模型：
$$
\min f(x)
$$
$$
\text{s.t. }\mathbf{x}\in \Omega
$$
$$
\Omega ={\mathbf{x}\in\R^n|c_i(\bold{x})}
$$
线性规划问题：目标函数与约束函数都是线性的规划问题
非线性规划问题：数学模型中含有非线性函数的规划问题
可行点（可行解）：满足约束条件的点
可行域（可行集）$\bold{S}$：全体可行点的集合
无约束问题：如果一个问题的可行域是整个空间
最优解：$\bold{x}^\in\Omega, \forall \bold{x}\in\Omega,f(\bold{x}^)\le f(\bold{x})$
局部最优解：$\bold{x}^\in\Omega, \exist N(\bold{x}^,\delta),\forall \bold{x}\in N(\bold{x}^*,\delta)\cap\Omega, f(\bold{x}^*)\le f(\bold{x})$
严格局部最优解：$\bold{x}^\in\Omega, \exist N(\bold{x}^,\delta),\forall \bold{x}\in N(\bold{x}^*,\delta)\cap\Omega,\bold{x}\ne \bold{x}^*, f(\bold{x}^*)\lt f(\bold{x})$
最优值：优化问题的目标函数在最优解处的点
若优化问题在可行域上有下界，但没有最优解，此时称目标函数在可行域身上的下确界为优化问题的最优值。
1.2 预备数学知识
线性相关与线性无关：设$V$为向量空间，$v^1, v^2,···,v^k\in V$，若存在不全为0的数$\lambda_1, \lambda_2,···,\lambda_k$使得$\lambda_1v^1+\lambda_2v^2+···+\lambda_kv^k=0$，则称$v^1, v^2,···,v^k$为线性相关向量组，否则称为线性无关向量组
范数：若函数$|·|:\mathbb{R}^n\rarr\mathbb{R}$满足以下条件：
- 正定型：$\forall x,y\in\mathbb{R}^n,|x|\ge0$并且$|x|=0\Leftrightarrow x=0$；
- 三角不等式：$\forall x,y \in\mathbb{R}^n,|x+y|\le|x|+|y|$；
- 齐次性：$\forall \alpha\in\mathbb{R},\forall x\in\mathbb{R}^n,|\alpha x|=|\alpha||x|$。
则称$|·|$为$\mathbb{R}^n$上的范数
常用范数：
$$
|x|2={\sqrt{\sum\limits{i=1}^{n}x_i^2}}
$$$$
|x|1=\sum\limits{i=1}^{n}|x_i|
$$$$
|x|\infin=\max\limits{1\le i\le n}{|x_i|}
$$序列极限
集合概念
梯度：
Hesse矩阵：
Taylor展开：
二次型的正定性：
二次型的半正定性：
凸集
超平面
半空间
射线
凸集性质
极点
极方向
多面集的表示定理
第2章 线性规划的基本性质
2.1 图解法
2.2 线性规划标准形式
2.3 基本性质
- 线性规划的可行域是凸集
- 若线性规划的可行域非空，则
- 线性规划存在有限最优解的充要条件是所有