5.1 最优化与计算复杂度
5.1.1 最优化理论
5.1.2 最优化的数学描述
最优化问题的基本数学模型如下：
在上述模型中：
- x是位于实数域（R）范围内的n维向量，x被称为决策变量或问题的解。
- s.t.为英文subject的缩写，表示受限于。
- f(x)称为目标函数或代价函数（Cost Function），如上式，我们要求f(x)的最小值（或最大值）
- h(x)为等式约束：g(x)为不等式约束
初次之外，最优化问题的无约束问题还可能被表述为如下这个方式：
其中argmax符号是指求解当函数f(x)达到最大值（或最小值）时的x取值。
根据目标函数与约束函数的不同形式，可以把最优化的问题分为不同的类型：若f(x)、h(x)、g(x)三个函数都是线性函数，就称为线性规划；若其中任一一个是非线性函数，那么就称为非线性函数；若目标函数为二次函数，约束全为线性函数，就为二次规划；若目标函数是向量函数，则成为多目标规划等。
5.1.3 凸集与分离定理
如图5.1所示。在实数域R上的向量空间中，如果集合S中的任一两点的连线上的点都在S内，则成为S为凸集。
1、凸集的满足条件
设X€Rn是一个凸集，当且仅当：
其中X是一个集合（矩阵），x1，x2是集合中的两个向量，α位于[0,1]。
这个公式说明，如果一个集合X是凸集，则该集合中的任一两个点x1和x2连成一条线段，该线段的任一一点也位于集合X中。
2、超平面和支撑平面
超平面被定义为点集X：
X={x|cTx=z}
其中，x是集合X中的一组向量，c是同纬度的系数向量：cT是c的转置；z是一个标量。
支撑超平面：设凸集X上的一个超平面cTx=z，现在我们给出凸集X的边界点w，得到cTw=z为凸集X的支撑超平面。
3、凸集的分离定理
如果两个凸集之间没有交叉和重合的部分，就可以用超平面将两者隔开，这就是凸集分离定理。
设S1，S2∈Rn为两个非空集合，如果存在非零集合p∈Rn及α∈R，使得：
5.1.4 凸函数及其性质
凸函数：f(αx1+(1-α)x2)≤f(α）x1+f(1-α)x2
凸函数判定（略）
5.1.5 局部最优与全局最优
5.1.6 算法复杂度
时间复杂度与空间复杂度 、结果确定性与不确定性
资料来源：郑捷 《机器学习算法原理与编程实践》 仅供学习研究