优化模型是一类重要的数学模型,它是利用数学的方式来刻画一个真实问题。建模的过程通常涉及以下步骤:定义目标,查找相关文献,建立模型并收集数据,初始测试,验证模型。优化建模是对一个实际问题建立合适的优化模型,即要确定优化问题的目标函数和决策变量所在的可行域。
最小二乘法(least squares method),又称最小平方法,是一种数学优化建模方法。它通过最小化误差的平方和寻找数据的最佳函数匹配。最小二乘法建模常用于线性/非线性方程问题中。假设求解如下方程组:
式(1)的求解在实际中应用广泛,但这个问题并不总是可解的。首先,方程组的个数m 可以超过自变量个数n,因此方程组的解可能不存在;其次,由于测量误差等因素,式(1)的等 式关系可能不是精确成立的。为了能在这种实际情况下求解出x,最小二乘法的思想是极小化误差的二范数平方,即 最小二乘的思想:若式(1) 存在解,则求解问题式(2)的全局最优解就相当于求出了方程的解;当方程的解不存在时,式(2)实际给出了某种程度上误差最小的解。
最小二乘采用了二范数,主要假设噪声服从独立高斯分布,如噪声服从其他分布则对应最小一乘(拉普拉斯分布),即保证偏差的绝对值之和最小,对应模型为: 若保证最大偏差最小化,则对应如下模型
正则化(regularization)是指为解决适定性问题或过拟合而加入额外信息的过程。在建模的时候,通常需要利用解的先验信息。比如式(1)方程个数小于未知变量个数时,可能存在多个解,这些需要利用解的性质(如稀疏性),来对解空间进行约束。为了使解具有光滑性以及克服问题的病态性(海森矩阵奇异),该井模型如下: 若想得到稀疏解,可以借助0范数构建如下模型:
实际上式很难处理(NP-Hard),通常用1范数对上式进行松弛,即构建模型:
在图像/信号处理中,变量本身可能不具有稀疏性质,但在变换域中是稀疏的,对应的模型为
图中左侧是训练集,右侧是验证集。训练集和验证集数据均是由线性函数加上一定的随机扰动生成的。图中橙色直线是以线性模型拟合训练集数据得到模型的函数曲线;绿色虚线则是以15-阶多项式模型拟合训练数据得到模型的函数曲线。由此可见,尽管多项式模型在训练集上的误差小于线性模型,但在验证集上的误差则显著大于线性模型。此外,多项式模型为了拟合噪声点,在噪声点附近进行了高曲率的弯折。这说明多项式模型过拟合了训练集数据。
在实际问题中有很多数据来自未知的概率分布,从数据反推分布的具体形式是非常重要的课题。最大似然估计就是统计中常用的一种估计概率分布的方法,其通过最大化似然函数,使得观测数据尽可能地服从假定的模型。因为最大似然估计的直观性,其在实际中非常流行。似然函数:定义为在参数作用下样本数据集发生的概率,即 似然函数实际上是样本集合的联合概率分布,只是自变量为参数x,参数的最大似然估计定义为
假设最大似然估计存在,则求解最大似然估计本质上是在一族分布中寻找最有可能产生该样本的参数。实际中似然函数的最大值往往更容易求解,即考虑如下最大化问题
因为对数函数为严格单调递增的,式(11)和式(10)解一致。对数可将乘法变为加法,实际更易操作,所以在统计中更倾向于使用对数似然函数。对于很多模型来说,似然函数的表达式是已知的,但是其最优解的显式表达式是未知的,因此我们需要利用数值优化算法求其全局最优解。可参考Weibull和Gamma分布参数的最大似然估计数值求解。
在不同比例参数值下一个二项式过程的可能性曲线t=3, n=10;其最大似然估计值发生在其众数并在曲线的最大值处。
运筹学中的很多问题就是极小化代价(损失)并极大化收益的过程。比如,我们在玩俄罗斯方块的时候,每走一步都会有相应的分数奖励,我们期望的自然是最后的得分越高越好;在旅行的时候,我们一般会提前规划好想去的城市并确定行程此时,我们希望在游览所有城市的情况下路程最短或者差旅费最少;在超市物品定价的时候,我们一般会根据价格与可能销售数量之间的关系来确定一个能带来最大利润的定价。这些实际问题,都可以写成优化问题的形式,其目标函数或者是极小化代价(损失),或者是极大化收益,或者是两者兼顾。
各种代理损失函数的曲线。蓝色为0–1指示函数,绿色为平方损失函数,紫色为铰链损失函数,黄色为逻辑损失函数。
泛函(functional)指以函数构成的向量空间为定义域,实数为值域为的“函数”,即某一个依赖于其它一个或者几个函数确定其值的量,往往被称为“函数的函数”。
弧长泛函以可求长曲线组成的向量空间(的一个子集)为定义域,以实标量为输出值。这是一个非线性泛函的例子。
变分法是处理泛函的数学领域,和处理函数的普通微积分相对。譬如,这样的泛函可以通过未知函数的积分和它的导数来构造。变分法最终寻求的是极值函数:它们使得泛函取得极大或极小值。
物理、化学中的很多问题都可以表述为能量极小化的形式。比如,在电子结构计算中,我们通过极小化原子和电子之间的相互作用能量来计算稳定态。在玻色– 爱因斯坦凝聚问题中,我们也是通过极小化能量泛函来找到玻色子的物质状态。一般来说,能量泛函是定义在函数空间上的,即相应优化问题的自变量是无穷维空间中的函数。我们可以通过变分来得到其相应的最优性条件等。实际中常用的另一种方式,是利用合适的离散化,将能量泛函的极小化问题从无穷维空间中拉回到有限维空间中,从而得到相应问题的离散解。注意,不同的离散化一般对应于不同的目标函数及不同的优化问题。
当原始问题不容易求解时,优化中一个常用的技巧是松弛。这一技巧的基本思想是:在保留原问题部分性质的条件下,使用简单的项替代目标函数中难以处理的项,进而使得问题更易求解。如0范数为不可微且非凸的,可以用1范数对其进行松弛近似。
另一种松弛的方法是找到目标函数的一个下界替代源目标函数进行求解,新的目标函数在可行域内小于原函数,且具有简单函数形式。
一个整数规划及其LP松弛如下图所示。
根据实际问题的具体形式,优化问题的决策变量需要满足各种各样的约束。比如,在电子结构计算中,我们假设轨道函数之间是相互正交的。在化学反应过程当中,各成分的浓度随着时间的变化对应于一个微分方程组。在最优设计中,我们有时需要优化物体的形状。如在飞机机翼设计中,受机翼周围的气流影响,机翼形状的改变对应于一个微分方程。在很多情况下,我们还需要非负约束,比如图像的像素值,物体的浓度,拥有的资源数量,等等。当线性或者一般的等式观测带有噪声或者需要更多的鲁棒性时,我们也将等式约束放宽为不等式约束。
对于一个优化问题,如果其目标函数是复合函数的形式,可以进行如下转化 对于无约束优化问题,也可以进行如下转化
也可以利用上方图进行优化问题转化如
将优化问题的约束进行等价转换有助于研究该问题的数学性质。表面上看起来不相似的问题经过等价转化之后可能会变成类型相同的优化问题,并最终能够找到统一的算法来求解这些问题。
当原始优化模型的约束过于复杂时,我们同样可以采用松弛的技巧将难处理的约束替换为容易处理的约束。松弛后的可行域会放大。放大可行域需遵循两点原则:一是将原有约束进行简化,即松弛后的问题更易处理;二是不宜将可行域放得过大,过分放大可行域会丢失原问题的关键信息,进而使得求解松弛问题变得没有意义。
回归分析(Regression Analysis)是一种统计学上分析数据的方法,目的在于了解两个或多个变数间是否相关、相关方向与强度,并建立数学模型以便观察特定变数来预测研究者感兴趣的变数。更具体的来说,回归分析可以帮助人们了解在只有一个自变量变化时因变量的变化量。一般来说,通过回归分析我们可以由给出的自变量估计因变量的条件期望。
回归分析的一般观测模型为: 线性回归:观测函数是线性,假设噪声服从高斯分布,则有对应的优化问题为最小二乘问题如下:
Tikhonov 正则化: 为了平衡模型的拟合性质和解的光滑性,Tikhonov 正则化或岭回归(ridge regression)添加二范数平方为正则项:
由于正则项的存在,该问题的目标函数是强凸函数,解的性质得到改善。
LASSO 问题:如果希望得到的解x 是稀疏的,那么可以考虑添加1范数为正则项,对应的模型为
简单线性回归分析的例子:
在分类问题中,输出变量取值于离散空间。给定特征,逻辑回归假定样本属于1类别的概率为 属于-1类别的概率为
上面两个概率可以简洁写成
假设特征a与b之间独立同分布,则给定特征label的联合概率密度为
那么最大似然估计是求解如下最优化问题:
与稀疏优化类似,常用模型还需要考虑参数x 的性质,加上正则项,如Tikhonov 正则化模型
支持向量机(英语:support vector machine,常简称为SVM,又名支持向量网络)是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。以二分类为例,其基本思想是使得保证数据分类正确的情况下要求点到分类超平面的最小距离尽可能大。其原始模型为 上式约束条件可以等价转化为:
由于对参数的尺度缩放不会影响问题的解,因此将可行域缩小,原问题可以等价转化
通过整理消除间距的影响,上式转化为
当线性不可分时,即允许有分类错误的点,引入松弛变量,经等价转化后,问题为
上式为约束优化问题,可以转化为无约束优化问题如下:
图中核函数Φ,将低维非线性可分离函数(左)计算成高维线性可分离函数(右)。
设样本属于两个类,用该样本训练SVM得到的最大间隔超平面。在边缘上的样本点称为支持向量。
在概率论、统计学及机器学习中,概率图模型(Graphical Model)是用图论方法以表现数个独立随机变量之关联的一种建模法。
相位恢复是信号处理中的一个重要问题,它是从信号在某个变换域的幅度测量值来恢复该信号。
在多元统计分析中,主成分分析(Principal components analysis,PCA)是一种统计分析、简化数据集的方法。它利用正交变换来对一系列可能相关的变量的观测值进行线性变换,从而投影为一系列线性不相关变量的值,这些不相关变量称为主成分(Principal Components)。具体地,主成分可以看做一个线性方程,其包含一系列线性系数来指示投影方向。PCA对原始数据的正则化或预处理敏感(相对缩放)。
主成分分析是数据处理和降维中的一个重要技巧,它提供了一种将高维空间中的点在低维子空间中表达的方法。主成分分析寻找方差最大的子空间投影,实际上是极小化投影点的重构误差。其优化模型即其等价问题如下:
一个高斯分布,平均值为(1, 3),标准差在(0.878, 0.478)方向上为3、在其正交方向上为1的主成分分析。黑色的两个向量是此分布的协方差矩阵的特征向量,其长度为对应的特征值之平方根,并以分布的平均值为原点。
矩阵分离问题也是一类重要的低秩矩阵计算问题。矩阵分离问题有时候也称为鲁棒主成分分析(robust PCA),目标是在图像处理中最大程度地去除原有数据中的噪声,寻找数据在低维空间上的最佳投影。其对应的凸优化问题为
稀松字典学习是一种表征学习方法,其目的在于找出一组基本元素让输入信号映射到这组基本元素时具有稀松表达式。我们称这些基本元素为“原子”,这些原子的组合则为“字典”。字典里的“原子”并不需要满足正交基这一特性,且往往它们会是过完备的生成集合。过多的原子除了可以让我们在叙述一个讯号的时候可以由很多种表达式,同时也提升了整个表达式的稀松性,让我们可以以较简单的表达式来诠释讯号
正如各种各样的知识都可以用一本字典里的字通过排列组合来表达一样,字典学习的目的就是将已有的(超)大规模的数据集进行压缩,找到蕴藏在这些数据点背后的最基本的原理。其优化模型为
聚类分析是统计学中的一个基本问题,其在机器学习、数据挖掘、模式识别和图像分析中有着重要应用。其优化模型为:
k均值的收敛示意图如下
标准算法演示:
小波分析是图像重构的另外一种方法。它通过不同尺度变化对失真图像进行多尺度分析,进而保留想要的尺度信息,去掉噪声等对应的干扰信息。小波分析的一个最重要的概念是小波框架,它是空间中基函数的推广。其分解优化模型为
对具有频率间断点的信号使用五阶消失矩的symlet 进行连续小波变换:
介绍了的建模技术,也回顾了统计学习、机器学习、图像和信号处理中一些常见的优化问题
[1]. 维基百科。
[2]刘浩洋等《最优化:建模、算法与理论》。