凸优化1
- 凸优化是什么
- 怎么求最大值、最小值
- 优化问题的形式
- 优化问题类别1:凸函数 和 非凸函数
- 优化问题类别2:带条件 和 无条件
- 优化问题类别3:离散 和 连续
- 优化问题类别4:平滑 和 非平滑
- 如何判断一个目标函数是凸函数?
- 在同样条件下,怎么设计为凸函数模型?
- 怎么求解非凸函数?
- 怎么对非凸函数松弛,变成凸函数?
凸优化是什么
基本上,机器学习就是 模型 + 优化。
重要性亦如,程序 = 数据结构 + 算法,缺一不可。
如果你只学模型,你就缺了一条腿,走的不稳不快,没核心竞争力。
学了凸优化,看论文就会很轻松,就能理解数学公式在做什么,就喜欢看数学公式了。
就和别的数学不一样,你学了在应用里基本用不到,但你会凸优化,你可以根据任务改更好的损失函数、在原有模型上创新。
应用优化、科研论文必备。
凸优化,目的是求一个函数的最大值或最小值。
怎么求最大值、最小值
像以前学习的求最大值、最小值算法(如堆、快排),都是在一个有无限集合的函数。
现在我们面临的是一个无限的集合,我们不可能穷尽所有的可能性。
在以前,我们把最优化问题看成是若干数量比较大小的问题。
而凸优化是看成研究函数动态变化趋势的问题了,变成了寻找函数变化拐点的问题。
这里转换的核心是,从静态的数值比较变成动态的函数变换趋势。
假设有一条山坡,我们想要找到这条山坡上的最高点。我们可以使用变换趋势来帮助我们找到最高点。
- 变换趋势:函数在该点的变化率,上升、下降、不变
我们的目标是找到变换趋势等于零的点,也就是山坡上的平稳点。
这些点是可能的最高点、最低点。
- 观察变换趋势的符号变化
- 在找到变换趋势等于零的点之后,看看它前后的点,如果从正变为负,那么这个点就是山坡上的最高点
- 之前为正代表一直在上升,而在这个点之后,山坡开始下降
- 这个变换趋势,在数学中叫导数
虽然这个方法,适用于任何函数,把求最大值问题就变成了简单的解方程的问题。
但ta找的最大值可能是局部最大值,而不是全局最大值。
比如上图,有左右两个高点,都满足:
- 变换趋势等于零的条件
- 变换趋势符号从正变成零,再变成负这个条件
但是最大值只能有一个,由于左边的那个点比右边的要高一些,因此左边的是真正的最大值,右边的是局部最大值(极大值)。
那如何在很多的那个局部的极大值中找到最大值的方法?
- 目前依然没有很好的方法系统性地解决这个问题,只能一个个比较。
这个问题在机器学习中尤为突出,因为我们通常需要在复杂的函数空间中找到最大值,而找到了最大值,很可能不过是很多局部极大值中的一个而已。
那你说学习是不是要最优化算法,帮助我们找到更大的局部最大值,或者全局最大值!!
最优化是寻找函数的最优解,凸优化是最优化的一个子集。
好处在于,对于一个凸优化问题,我们可以通过凸优化算法找到全局最优解,而不仅仅是局部最优解。
这是凸优化的一个重要优势,凸优化问题具有全局最优解的保证。
如果你懂得识别凸函数,能在同样条件下,把模型设计成偏向凸函数,那你就能找到全局最优解。
说实话,你搞机器学习,你面对的不都是别人解决好的问题,因为你在高科技公司的话,你面临的大多是尚未解决的问题。
同行极大概率找到都是比较大的局部最优解,那不就是你大显神威的时候吗!
优化问题的形式
任何一个优化问题都可以写成:
: 这是凸优化问题的目标,表示我们的目的是找到一个变量
x
的值,使得函数: 这些是所谓的不等式约束。
表示不同的函数,每个函数都有一个对应的不等式。
i
的范围是从1到某个整数,它表示有多少个这样的约束。这些约束限制了解决方案的可行性,即我们不能随便选择任何值来最小化;解决方案必须使所有的
: 是等式约束,用
表示。
j
的范围同样表示有多少个这样的约束。等式约束必须被严格遵守,意味着解决方案必须使所有的
将这些信息放在一起,我们可以这样理解这个公式:我们的目标是找到一组变量x
的值,这组值不仅要使目标函数 的值最小化,而且还要满足所有的不等式约束
和所有的等式约束
。
这就像是你在玩一场游戏,目标是得分最低(最小化f_0(x)
),同时你必须遵守游戏的规则(满足不等式和等式约束)。
优化问题类别1:凸函数 和 非凸函数
想象山的形状,就像一个凸形的曲线。
如果你在凸形的曲线里面放一个小球,无论小球在哪个位置,它最终都会滚到最低点。
在数学中,这个凸形的曲线就可以用凸函数来描述。
凸函数的优化问题非常重要,因为它们通常有唯一的最低点(全局最小值),就像碗底一样。
所以,当你的目标是最小化一个凸函数时,你可以使用任意的算法(比如梯度下降法)来寻找这个全局最小值,而不用担心找到一个“伪”最小值(局部最小值)。
但如果是非凸函数,会有很多局部最小值,要选择合适的算法,但也不容易找到全局最小值。
在处理非凸函数优化时,可以采取以下几种策略:
- 局部搜索方法:这类方法从某个初始点出发,通过迭代的方式尝试找到局部最优解。例如梯度下降、牛顿法等。它们通常会收敛到最近的局部最小值,但不保证找到全局最小值。
- 全局优化算法:这些算法旨在搜索整个函数空间以找到全局最小值。例如模拟退火、遗传算法、粒子群优化等。这些方法可能会消耗更多的计算资源,但更有可能接近或找到全局最优解。
- 启发式方法:这类方法包括对问题的特殊理解和创造性的算法设计,如分枝定界、割平面方法等。它们通常利用问题的特定结构来缩小搜索范围并找到更好的解。
- 凸松弛:当面对一个难以直接解决的非凸问题时,可以尝试将其松弛为一个凸问题,例如通过引入额外的变量或者放松一些约束条件。这样虽然可能无法得到原问题的精确解,但可以获得一个近似解,有时这个近似解足够接近真实的全局最优解。
- 集成方法:将上述方法组合使用,例如先用全局优化算法找到一个不错的起点,然后再使用局部搜索方法进行精细调整。
优化问题类别2:带条件 和 无条件
这种类别的优化问题就像是你在玩一个游戏,但是有一些规则限制你的动作。
在数学中,这些规则被称为约束条件。
这些约束可以是等式(比如,你需要在一个特定的预算内花费),也可以是不等式(比如,你不能超过一定的重量或体积)。
当你的目标是找到某个函数的最大值或最小值,但同时要满足一些额外的条件时,你就面临着一个带条件的优化问题。
这种问题需要特别的技巧来解决,因为你不能只关注函数值的优化,还要确保所有的约束都得到满足。
线性规划和非线性规划就是处理这类问题的常用方法。
优化问题类别3:离散 和 连续
这个类别的区分是根据优化问题的变量是离散的还是连续的。
离散就像计数一样,你可以数1、2、3,但不能数1.5、2.5等。
而连续则像用尺子量长度一样,可以量到任何小数点后的值。
离散优化问题通常涉及整数、图或网络等,在这类问题中,变量只能取有限的、分开的值。
举个例子,旅行商问题就是一个经典的离散优化问题,你需要找到一条路径,经过一系列城市一次且仅一次,并最终回到起点,同时路径长度最短。
连续优化问题中,变量可以在某个区间内任意取值。
比如,在设计一座桥时,你可能会调整桥的长度、宽度和曲率,这些都是连续的变量,你需要找到最佳的组合,以确保桥既安全又经济。
优化问题类别4:平滑 和 非平滑
平滑优化问题是指目标函数具有良好的数学性质,特别是它们在定义域内是连续可导的,这意味着它们有着连续的梯度(或者说斜率)。
你画这样一个函数的图像,你会得到一个光滑的曲线或曲面,没有任何尖锐的拐点或者断点。
这种光滑性让函数容易使用基于梯度的方法来优化,因为你可以通过计算梯度(梯度下降法或牛顿法等)来找到函数值上升或下降最快的方向。
常见的平滑函数包括多项式函数、指数函数和对数函数。
非平滑优化问题中的目标函数可能不是处处连续可导的,这意味着函数的图像可能有尖角、棱角或者不连续的跳跃。
你画这样一个函数的图像,你的笔在某些点上可能需要“跳过”一个间断,或者在转角处突然改变方向。
非平滑优化问题通常更难处理,因为没有连续的梯度信息可以指导优化过程,因此可能需要使用更复杂的算法,如次梯度方法、近似梯度方法或者基于非梯度的优化策略或启发式算法来求解。
常见的例子包括绝对值函数、最大值/最小值函数(如ReLU激活函数)。
最简单的情况是:无条件、凸函数、连续、平滑,这种情况特别好算的。
像其他复杂的情况,那需要学习各个优化算法了。
如何判断一个目标函数是凸函数?
判断一个函数是凸函数还是非凸函数可以采用以下两种方法:
- 通过二阶导数
- 利用凸性定义
方法一:通过二阶导数判断
对于一元函数,可以通过判断其二阶导数的符号来判断函数的凸性:
- 如果函数的二阶导数在定义域内始终大于等于零(即非负),则该函数是凸函数。
- 如果函数的二阶导数在定义域内始终小于等于零(即非正),则该函数是凹函数。
对于多元函数,可以通过计算其海森矩阵(Hessian Matrix)来判断函数的凸性:
- 如果海森矩阵在定义域内始终半正定(即所有特征值非负),则该函数是凸函数。
- 如果海森矩阵在定义域内始终半负定(即所有特征值非正),则该函数是凹函数。
方法二:利用凸性定义
函数的凸性定义如下:
- 对于一元函数,如果对于任意的 x1、x2 ∈ 定义域内,以及任意的 t ∈ [0, 1],都有
,则该函数是凸函数。
- 对于多元函数,如果对于任意的 x1、x2 ∈ 定义域内,以及任意的 t ∈ [0, 1],都有
,则该函数是凸函数。
对于凸函数来说,任意两个点的连线上的函数值都不大于连线两端点的函数值。
可以通过绘制函数图像和观察函数的形状来帮助判断凸性。
- 如果图像向上凸起,那么函数是凸函数;
- 如果图像向下凹陷,那么函数是凹函数。
在同样条件下,怎么设计为凸函数模型?
怎么求解非凸函数?
怎么对非凸函数松弛,变成凸函数?