ML算法——最优化|凸优化随笔【机器学习】【端午节创作】

来杯Sherry

发布于 2023-06-27 15:57:04

3040

数学预备知识

最优化问题指的是在给定条件下，找到一个目标函数的最优解，即找到能够使目标函数取得最大值或最小值的变量取值。常用的优化方法包括线性规划、整数规划、动态规划、遗传算法、模拟退火等。最终，通过对最优解的检验和实施，可以实现资源的最优分配或其他最优解决方案。

最优化的基本数学模型：

min f(x)

s.t. \quad h_i(x)= 0 ,\quad g_j(x)≤ 0

\quad h_i(x)= 0 ,\quad g_j(x)≤ 0

超平面和半空间

二维空间的超平面就是一条线（可以是曲线），三维空间下的超平面是一个面（可以是曲面）。

简单来说，超平面是具有一个变量的空间中的直线、平面等概念的推广。半空间是数学中的一个概念，通常指一个空间中，其中一个方向的值被限定为非负数。例如，在三维空间中，一个半空间可以表示为z≥0，其中z表示垂直于x-y平面的方向。数学表达式如下：

超平面：

H = \{x ∈R^n | a_1x_1+a_2x_2+...+a_nx_n=b\}

半空间：

H^+ = \{x ∈R^n | a_1x_1+a_2x_2+...+a_nx_n≥b\}

凸集分离定理

凸集，凸函数，详见数学预备知识 2.1梯度下降

凸集分离定理是凸集理论中最基本的定理之一，它表明两个不相交的凸集总可以用超平面分离。这个定理在凸优化理论中有重要的应用，因为它提供了将多变量问题转化为多个单变量问题的方法。

如何实现的多变量问题转换为多个单变量问题？

凸集分离定理可以将多变量问题转换为多个单变量问题。具体来说，如果需要将两个不相交的凸集C和D分离，可以通过以下步骤实现：

找到一个超平面，使得它与C和D的交点分别为x和y，且x和y分别位于超平面的两侧。
将超平面方程中的多个变量化为单个变量，例如将x1, x2, x3化为x1，将y1, y2, y3化为y1。
将超平面方程表示为一个关于x1的单变量函数f(x1)，使得f(x1) = 0。
对于每个变量xi，分别求解f(xi) = 0，得到一组单变量方程。
对于每个单变量方程，求解其根xi，如果xi同时满足C和D的定义域，则将xi代入超平面方程中得到超平面方程中的常数项a。
将超平面方程中的常数项a表示为多个变量的函数g(x1, x2, …, xn)，其中每个变量对应一个单变量方程。
将超平面方程中的常数项a表示为多个变量的函数g(x1, x2, …, xn)后，可以将其代入原多变量问题中，得到一个新的多变量问题，这个问题的解即为原问题的解。

通过以上步骤，就可以将多变量问题转换为多个单变量问题。这种方法在凸优化理论中有重要的应用，因为它可以将多变量问题转化为多个单变量问题，从而简化问题的求解。

（暂不理解这个步骤2的替换如何实现的）