优化_优化算法 - CSDN
精华内容
参与话题
  • 程序员的数学:优化理论

    千人学习 2020-03-11 14:43:07
    程序员的数学-优化理论
  • 优化理论与凸优化到底是干嘛的?

    万次阅读 多人点赞 2017-12-17 10:46:35
    优化的定义 1.1 凸优化 ...1.1 凸优化优化问题目前在机器学习,数据挖掘等领域应用非常广泛,因为机器学习简单来说,主要做的就是优化问题,先初始化一下权重参数,然后利用优化方法来优化这个
    1. 凸优化的定义
      1.1 凸优化
      1.2 全局最优化与局部最优化
    2. Least-squares and linear programming(最小二乘与线性规划)
      2.1 最小二乘
      2.2 线性规划
    3. 最优化方法的一般结构
    4. 优化理论在机器学习,深度学习中扮演的角色

    1.优化的定义

    1.1 凸优化

    最优化问题目前在机器学习,数据挖掘等领域应用非常广泛,因为机器学习简单来说,主要做的就是优化问题,先初始化一下权重参数,然后利用优化方法来优化这个权重,直到准确率不再是上升,迭代停止,那到底什么是最优化问题呢?

    它的一般形式为:

    minimize f0(x)
    使 fi(x)bi,i=1,,m
    第一个为优化的目标,即最小化目标函数f(x),而带大于号或小于号的,则是约束条件。我们希望找到一个满足约束条件的x,使得对于任意的z满足约束条件:
    f1(z)b1,,fm(z)bm
    f0(z)f0(x)
    x就是我们所求的最后结果。

    • 相当于你要从上海去北京,你可以选择搭飞机,或者火车,动车,但只给你500块钱,要求你以最快的时间到达,其中到达的时间就是优化的目标,500块钱是限制条件,选择动车,火车,或者什么火车都是x。

    满足所有约束条件的点集称为可行域,记为X,又可以写为:

    min f(x)   s.t xX
    ,s.t表示受限于(subject to)。

    在优化问题中,应用最广泛的是凸优化问题:

    • 若可行域X是一个凸集:即对于任给的x,yX,总有
      λx+(1λ)yX, λ(0,1)
    • 并且目标函数是一个凸函数:即
      f(λx+(1λ)y))λf(x)+(1λ)f(y)
      我们称这样的优化问题为凸优化问题。

    用图像来表示就是:
    这里写图片描述
    函数上方的点集就是凸集,函数上任意两点的连线,仍然在函数图像上方。

    一句话说清楚就是:希望找到合适的x,使得f0(x)最小。

    1.2 全局最优化与局部最优化

    全局最优化指的是在满足条件约束的情况下,找到唯一的一个点满足最大值或者最小值。

    局部最优化指的是在满足条件约束的情况下,有可能找到一个局部最大/小点,但不是全局最大或者最小的点。
    用图像表示为:
    这里写图片描述

    2.Least-squares and linear programming(最小二乘与线性规划)

    关于这两个问题的更详细的例子会在接下来的文章中说到,这次只是简单的介绍一下我们的内容。

    2.1 最小二乘

    最小二乘问题是无约束的优化问题,通常可以理解为测量值与真实值之间的误差平方和:

    minimize f0(x)=Axb22=i=1k(aTixbi)2
    其中ARk x nk>naTiAix

    这个问题既然没有约束条件,那应该怎么求解呢?我们的目标是求解出最好的x,观察这个式子可以发现,这个式子一定是大于等于0的,所以这样的最优化问题,我们可以把它转成线性方程来求解:

    ATAx=ATb
    AT为A的转置,因此根据矩阵的逆:
    (ATA)1ATA=1
    可以把上式表示为:
    x=(ATA)1ATb

    加权的最小二乘问题

    i=1kwi(aTixbi)2
    权值均为正数,代表每一个aTixbi对结果的影响程度。

    正则化的最小二乘问题:

    i=1k(aTixbi)2+ρi=1nx2i
    ρ是人为的选择的,用来权衡 最小化ki=1(aTixbi)2的同时,使得ni=1x2i不必太大的关系。

    2.2 线性规划
    另一类重要的优化问题是线性规划,它的目标函数和约束条件都是线性的:

    minimize cTx
    s.t    aTixbi,i=1,,m

    用画图的方法,就是根据条件,画出可行域,然后将目标函数在可行域上移动,直到得到最大值。
    这里写图片描述

    3.最优化方法的一般结构

    最优化的过程,相当于爬山,如图:
    这里写图片描述
    希望找到一个点列xk使得他的函数值是一直减少的,直到到达某一停止条件或者达到最小值的点xk.

    用数学上的术语可以表示为:

    • xk为第k次迭代点,dk为第k次搜索方向,αk为第k次迭代的步长因子,则第k次迭代为:
      xk+1=xk+αkdk

    从这里可以看到不同的步长和不同的搜索方向组成了不同的优化方法,这就是最优化理论中所讨论的。fxk的函数,搜索方向dkfxk处的下降方向,即dk满足:

    f(xk)Tdk<0
    或者
    f(xk+1)=f(xk+αkdk)<f(xk)

    而最优化的基本可以表示为:给定初始点xk

    1. 确定搜索方向dk,即按照一定规则画方法确定f在xk处的下降方向
    2. 确定步长因子αk,使得目标函数有一定的下降
    3. xk+1=xk+αkdk
      不断迭代,直到xk+1满足某种某种停止条件,即得到最优解xk+1

    最优化中的问题中,大部分都是在寻找各种各样的方法确定步长和方向,使得迭代的速度尽可能快,得到的解尽可能是最优的解。

    4.优化理论在机器学习,深度学习中扮演的角色

    凸优化,或者更广泛的说,是最优化理论,在目前的机器学习,数据挖掘,或者是深度学习的神经网络中,都要用到。

    他的地位相当于人的脊背一样的,支撑着整个模型的学习过程。因为模型,通俗来说就像人学习思考一样,我们自己知道自己该学什么,该怎么学,发现自己的知识学错了之后怎么调整,但计算机可没有人这么聪明,知道学什么,往哪里学。

    而最优化,就是告诉模型应该学什么,怎么学的工具。模型学习的往往都是一个映射函数,也就是模型中的参数W,这个参数的好坏,得看答案才能知道,但知道自己错了之后,该往哪里学,怎么学,怎么调整,这就是优化理论在其中扮演的角色。如果没有优化理论,那么模型是不知道该怎么学习的,也就是没有了最优化,模型的学习永远都是停滞不前的,这下你知道最优化理论的重要性了吧。

    展开全文
  • 深度学习各种优化函数详解

    万次阅读 2017-04-13 15:02:51
    深度学习中有众多有效的优化函数,比如应用最广泛的SGD,Adam等等,而它们有什么区别,各有什么特征呢?下面就来详细解读一下一、先来看看有哪些优化函数BGD 批量梯度下降所谓的梯度下降方法是无约束条件中最常用的...

    深度学习中有众多有效的优化函数,比如应用最广泛的SGD,Adam等等,而它们有什么区别,各有什么特征呢?下面就来详细解读一下


    一、先来看看有哪些优化函数


    BGD 批量梯度下降

    所谓的梯度下降方法是无约束条件中最常用的方法。假设f(x)是具有一阶连续偏导的函数,现在的目标是要求取最小的f(x) : min f(x)

    核心思想:负梯度方向是使函数值下降最快的方向,在迭代的每一步根据负梯度的方向更新x的值,从而求得最小的f(x)。因此我们的目标就转变为求取f(x)的梯度。

    当f(x)是凸函数的时候,用梯度下降的方法取得的最小值是全局最优解,但是在计算的时候,需要在每一步(xk处)计算梯度,它每更新一个参数都要遍历完整的训练集,不仅很慢,还会造成训练集太大无法加载到内存的问题,此外该方法还不支持在线更新模型。其代码表示如下:

    for i in range(nb_epochs):
      params_grad = evaluate_gradient(loss_function, data, params)
      params = params - learning_rate * params_grad

    我们首先需要针对每个参数计算在整个训练集样本上的梯度,再根据设置好的学习速率进行更新。

    公式表示如下:
    假设h(theta)是我们需要拟合的函数,n表示参数的个数,m表示训练集的大小。J(theta)表示损失函数。
    这里写图片描述

    这里写图片描述

    不难看出,在批量梯度下降法中,因为每次都遍历了完整的训练集,其能保证结果为全局最优,但是也因为我们需要对于每个参数求偏导,且在对每个参数求偏导的过程中还需要对训练集遍历一次,当训练集(m)很大时,这个计算量是惊人的!

    所以,为了提高速度,减少计算量,提出了SGD随机梯度下降的方法,该方法每次随机选取一个样本进行梯度计算,大大降低了计算成本。


    SGD随机梯度下降

    随机梯度下降算法和批量梯度下降的不同点在于其梯度是根据随机选取的训练集样本来决定的,其每次对theta的更新,都是针对单个样本数据,并没有遍历完整的参数。当样本数据很大时,可能到迭代完成,也只不过遍历了样本中的一小部分。因此,其速度较快,但是其每次的优化方向不一定是全局最优的,但最终的结果是在全局最优解的附近。

    需要:学习速率 ϵ, 初始参数 θ
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差并更新参数

    代码表示如下:(需要注意的是,在每次迭代训练中,需要重新洗牌训练集)

    for i in range(nb_epochs):
      np.random.shuffle(data)
      for example in data:
        params_grad = evaluate_gradient(loss_function, example, params)
        params = params - learning_rate * params_grad

    虽然BGD可以让参数达到全局最低点并且停止,而SGD可能会让参数达到局部最优,但是仍然会波动,甚至在训练过程中让参数会朝一个更好的更有潜力的方向更新。但是众多的实验表明,当我们逐渐减少学习速率时,SGD和BGD会达到一样的全局最优点。

    优点:
    训练速度快,避免了批量梯度更新过程中的计算冗余问题,对于很大的数据集,也能够以较快的速度收敛.

    缺点:
    由于是抽取,因此不可避免的,得到的梯度肯定有误差.因此学习速率需要逐渐减小,否则模型无法收敛
    因为误差,所以每一次迭代的梯度受抽样的影响比较大,也就是说梯度含有比较大的噪声,不能很好的反映真实梯度.并且SGD有较高的方差,其波动较大,如下图:
    这里写图片描述

    学习速率该如何调整:
    那么这样一来,ϵ如何衰减就成了问题.如果要保证SGD收敛,应该满足如下两个要求:

    这里写图片描述

    而在实际操作中,一般是进行线性衰减:

    这里写图片描述

    其中ϵ0是初始学习率, ϵτ是最后一次迭代的学习率. τ自然代表迭代次数.一般来说,ϵτ 设为ϵ0的1%比较合适.而τ一般设为让训练集中的每个数据都输入模型上百次比较合适.那么初始学习率ϵ0怎么设置呢?书上说,你先用固定的学习速率迭代100次,找出效果最好的学习速率,然后ϵ0设为比它大一点就可以了.

    • 另外,需要注意的是因为存在样本选择的随机性,所以在梯度下降过程中会存在较大的噪声,因此学习速率应该要逐渐减小,来寻找一个相对全局最优的方向。

    • 同时也考虑到每次只选择一个样本进行梯度更新存在较大的噪声,学者们开始尝试每次选择一小批样本进行梯度更新,在降低噪声的同时提高速度,因此就有了下面的MBGD小批量梯度下降法。


    MBGD小批量梯度下降

    为了综合上述两种方法,提出了小批量梯度下降。它:(1)降低在SGD中高方差的问题,能使得收敛更加稳定;(2)可以利用深度学习中最先进的库进行矩阵优化的操作,加速操作;(3)一般的小批量介于50~256,但是当适用很小的批量时,有时也统称为SGD。

    核心思想:在每次迭代时考虑一小部分样本,比如考虑10个样本,同时计算在这10个样本点上的每个参数的偏导数,对于每个优化参数,将该参数在这10个样本点的偏导数求和。

    代码表示:

    for i in range(nb_epochs):
      np.random.shuffle(data)
      for batch in get_batches(data, batch_size=50):
        params_grad = evaluate_gradient(loss_function, batch, params)
        params = params - learning_rate * params_grad

    但是,需要注意的是因为这里也存在样本选择的随机性,学习速率应该要逐渐减小,同时上述方法并不能保证好的收敛性。主要存在的挑战有:

    1. 选择适当的学习率可能很困难。 太小的学习率会导致收敛性缓慢,而学习速度太大可能会妨碍收敛,并导致损失函数在最小点波动。
    2. 使用学习率计划:尝试在训练期间调整学习率。 比如根据预先制定的规则缓慢的降低学习速率,或者当每次迭代之间的偏导差异已经低于某个阈值时,就降低学习速率。但是这里面的学习速率更新规则,以及阈值都是需要预先设定的,因此不适应于所有的数据集。
    3. 此外,使用梯度更新的方法会导致所有参数都用学习速率更新。但是当训练集数据是稀疏的,或者特征的频率是不同的,我们可能不希望它们更新到同样的程度,因此使用相同的学习速率会导致那些很少出现的特征有较大的变化。
    4. 在求取那些高度非凸的误差函数的最小值时,我们应该避免陷入局部最优解,实验表明,最困难的不是从局部最优而是鞍点,鞍点就是沿着某一个方向他是稳定的,沿着另一个方向不稳定,既不是最小点也不是最大点。这会使得该点在所有维度上梯度为0,让SGD难以逃脱。

    基于上述问题,又有了如下更多的优化策略!


    momentum

    上述SGD和MBGD算法都存在样本选择的随机性,因此含有较多的噪声,而momentum能解决上述噪声问题,尤其在面对小而较多噪声的梯度时,它往往能加速学习速率。

    这里写图片描述

    核心思想:Momentum借用了物理中的动量概念,即前几次的梯度也会参与运算。为了表示动量,引入了一个新的变量v(velocity)。v是之前的梯度的累加,但是每回合都有一定的衰减。

    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,并更新速度v和参数θ:

    ĝ ←+1m∇θ∑iL(f(xi;θ),yi)
    v←αv−ϵĝ
    θ←θ+v

    其中参数α表示每回合速率v的衰减程度.同时也可以推断得到,如果每次迭代得到的梯度都是g,那么最后得到的v的稳定值为 ϵ∥g∥/1−α

    也就是说,Momentum最好情况下能够将学习速率加速1/1−α倍.一般α的取值为0.9或者更小。当然,也可以让α的值随着时间而变化,一开始小点,后来再加大.不过这样一来,又会引进新的参数.

    特点:
    本质上来说,就和我们把球从山上退下来一样,球的速度会越来越快。和我们的参数更新一样,当方向一致时,动量项会增加;当方向不一致时,动量项会降低。
    即:
    前后梯度方向一致时,能够加速学习
    前后梯度方向不一致时,能够抑制震荡


    Nesterov Momentum

    仅仅有一个追求速度的球往山下滚是不能令人满意的,我们需要一个球,它能知道往前一步的信息,并且当山坡再次变陡时他能够减速。因此,带有nesterov的出现了!

    在momentum里,先计算当前的梯度(短蓝色线),然后结合以前的梯度执行更新(长蓝色线)。而在nesterov momentum里,先根据事先计算好的梯度更新(棕色),然后在预计的点处计算梯度(红色),结合两者形成真正的更新方向(绿色)。
    这里写图片描述
    这是对之前的Momentum的一种改进,大概思路就是,先对参数进行估计(先往前看一步,探路),然后使用估计后的参数来计算误差
    具体实现:
    需要:学习速率 ϵ, 初始参数 θ, 初始速率v, 动量衰减参数α
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,并更新速度v和参数θ:

    ĝ ←+1m∇θ∑iL(f(xi;θ+αv),yi)
    v←αv−ϵĝ
    θ←θ+v

    注意在估算ĝ 的时候,参数变成了θ+αv而不是之前的θ

    推荐好文——揭开nesters momentum的面纱


    AdaGrad

    AdaGrad可以自动变更学习速率,只是需要设定一个全局的学习速率ϵ,但是这并非是实际学习速率,实际的速率是与以往参数的模之和的开方成反比的.也许说起来有点绕口,不过用公式来表示就直白的多:

    这里写图片描述

    其中δ是一个很小的常亮,大概在10−7,防止出现除以0的情况.

    核心思想:对于频繁出现的参数使用更小的更新速率,对于不频繁出现的参数使用更大的更新速率。
    正因为如此,该优化函数脚适用于稀疏的数据,比如在Google从YouTube视频上识别猫时,该优化函数大大提升了SGD的鲁棒性。在训练GloVe词向量时该优化函数更加适用。

    具体实现:
    需要:全局学习速率 ϵ, 初始参数 θ, 数值稳定量δ
    中间变量: 梯度累计量r(初始化为0)
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,更新r,再根据r和梯度计算参数更新量

    在SGD中,我们对所有参数进行同时更新,这些参数都使用同样的学习速率。
    比图用gt,i表示在t时间点,对i参数求得的偏导。
    这里写图片描述
    那么在SGD中就会用同一个学习速率对i参数进行更新:
    这里写图片描述
    但是在adagrad里,会综合考虑i之前的所有梯度值来更新学习速率,其中Gt,ii是一个对角矩阵,i行i列存储了目前时间点为止的所有i参数的偏导的平方和。后面的项是一个很小的值(1e−8),为了防止除0错误。
    这里写图片描述
    优点:
    能够实现学习率的自动更改。如果这次梯度大,那么学习速率衰减的就快一些;如果这次梯度小,那么学习速率衰减的就慢一些。

    缺点:
    最大的缺点在于分母中那个G是偏导的累积,随着时间的推移,分母会不断的变大,最后会使得学习速率变的非常小,而此时会使得模型不再具备学习其他知识的能力。
    经验表明,在普通算法中也许效果不错,但在深度学习中,深度过深时会造成训练提前结束。因为它到后面的衰减可能越来越慢,然后就提前结束了。为了解决提前结束的问题,引入了如下的算法:Adadelta!RMSprop!


    Adadelta
    adadelta是adagrad的延伸,不同于adadelta将以前所有的偏导都累加起来,adadelta控制了累加的范围到一定的窗口中。
    但是,并非简单的将窗口大小设置并且存储,我们是通过下式动态改变的上述的G:
    这里写图片描述
    这里面的gamma类似于momentum里面的项(通常取值0.9),用来控制更新的权重。
    因此以前的:
    这里写图片描述
    将被改变为:
    这里写图片描述


    RMSprop

    RMSProp通过引入一个衰减系数,让r每回合都衰减一定比例,类似于Momentum中的做法。(我觉得和Adadelta没啥区别)

    具体实现:
    需要:全局学习速率 ϵ, 初始参数 θ, 数值稳定量δ,衰减速率ρ
    中间变量: 梯度累计量r(初始化为0)
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,更新r,再根据r和梯度计算参数更新量

    这里写图片描述

    算法的提出者建议如上式所示,gamma取0.9,学习速率为0.001

    优点:
    相比于AdaGrad,这种方法很好的解决了深度学习中过早结束的问题
    适合处理非平稳目标,对于RNN效果很好

    缺点:
    又引入了新的超参,衰减系数ρ
    依然依赖于全局学习速率


    Adam

    Adam(Adaptive Moment Estimation)是另外一种给每个参数计算不同更新速率的方法,其本质上是带有动量项的RMSprop,它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。它和上述的adadelta和RMSprop一样,都存储了以前的偏导平方衰减平均值,此外,它还存储以前的偏导衰减平均值。

    具体实现:
    需要:步进值 ϵ, 初始参数 θ, 数值稳定量δ,一阶动量衰减系数ρ1, 二阶动量衰减系数ρ2
    其中几个取值一般为:δ=10−8,ρ1=0.9,ρ2=0.999
    中间变量:一阶动量s,二阶动量r,都初始化为0
    每步迭代过程:
    1. 从训练集中的随机抽取一批容量为m的样本{x1,…,xm},以及相关的输出yi
    2. 计算梯度和误差,更新r和s,再根据r和s以及梯度计算参数更新量

    这里写图片描述

    其中的Mt和Vt分别表示平均值角度和非中心方差角度的偏导。
    这里写图片描述
    这里写图片描述

    才方法的作者建议 β1取0.9, β2取0.999 ,ϵ取10-8。并且声称Adam在实践中比其他的自适应算法有更好的表现。


    二、可视化

    让我们来可视化的看看它们的表现:

    比较一下速度:
    这里写图片描述

    比较一下在鞍点的性能:
    这里写图片描述


    三、如何选择


    • 如果你的数据很稀疏,那应该选择有自适应性的优化函数。并且你还可以减少调参的时间,用默认参数取得好的结果。
    • RMSprop是adagrad的一个拓展,旨在解决它提前结束的问题。
    • 而RMSprop和Adadelta类似,只是adadelta采用了RMS的方法更新参数。
    • 在RMSprop基础上增加了偏差校正和momentum,形成了Adam。
    • 综上,RMSprop、Adadelta、Adam都是类似的。
    • Kingma【Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13.】的实验表示,偏差校正使得Adam在优化到后面梯度变的稀疏的时候使得其优化性能最好。
    • 所以,可能Adam是最好的优化函数。
    • 所以,如果你希望你的训练能变的更快,或者你要训练的是一个复杂的深度的网络,尽量选择自适应的优化函数。

    参考

    展开全文
  • Matlab数学建模(五):优化模型之标准模型

    千次阅读 多人点赞 2018-11-18 20:34:38
    (1)了解最优化模型。 (2)掌握线性规划的优化求解。 (3)掌握整数规划的优化求解。 (4)了解Matlab的图形化应用。 二、实例演练  1、谈谈你对最优化模型的了解。  最优化模型是数学建模大赛中最常见的...

    一、学习目标

    (1)了解最优化模型。

    (2)掌握线性规划的优化求解。

    (3)掌握整数规划的优化求解。

    (4)了解Matlab的图形化应用。

    二、实例演练

         1、谈谈你对最优化模型的了解。

            最优化模型是数学建模大赛中最常见的问题类型之一。一般说来,凡是寻求最大、最小、最远、最近、最经济、最丰富、最高效、最耗时的目标,都可以划入优化问题的范畴。MATLAB 优化工具箱和全局优化工具箱对多个优化问题提供了完整的解决方案,前者涵盖了线性规划、混合整型线性规划、二次规划、非线性优化、非线性最小二乘的求解器,后者囊括了全局搜索、多初始点、模式搜索、遗传算法等求解算法。

           最优化即在一定的条件下,寻求使目标最小(大)的设计参数或决策。在优化问题中有两个关键对象:目标函数约束条件。哈哈哈,这让笔者想起来高中学到的线性规划,其实,本节谈到的最优化模型跟高中的线性规划还真有点像。不过,高中的线性规划问题约束条件很少,一般是通过作图法来求解。本节的最优化模型约束条件一般比高中的线性规划多很多,并且我们要通过写代码去求解,而不是作图。常规优化问题,其数学表达可以描述为:

    其中x 为长度n的决策变量向量,f(x) 为目标函数,G(x) 为约束函数。

    以上数学表达式看不明白也没关系,因为下面我们会通过两个具体的例子去讲解分析。

    求解目标函数的最小(大)值,一个高效而精确的解决方案不仅取决于约束条件和变量数量,更取决于目标函数和约束函数的特性。明确优化类型是确认优化方案的前提,让我们看一下这些特性如何划分:

    常见的目标函数有:

    线性规划:被广泛的应用于变量之间可线性表示的财务、能源、运营研究等现代管理领域中。

    混合整数线性规划:扩展了线性规划问题,增加了最优解中部分或全部变量必须是整数的约束。例如,如果一个变量代表要认购的股票数量,则只应取整数值。同样,如果一个变量代表发电机的开/关状态,则只应取二进制值(0 或 1)。

    二次规划:目标函数或约束函数为多元二次函数。此优化应用于财务金融中投资组合优化、发电厂发电优化、工程中设计优化等领域。

    最小二乘:分为线性和非线性,通过最小化误差的平方和寻找变量的最优函数匹配。非线性最小二乘优化还可用于曲线拟合。

     

    对 MATLAB 提供的各类优化问题的算法,我们称之为求解器(Solver)。根据其求解目标,被分为四大组:

    • 极小值优化组:找到目标函数出发点 x0 附近的局部极小值

    • 多目标优化组:找到最小化一组函数的最大值或指定的值

    • 方程求解组:找到非线性方程 f(x) = 0 出发点 x0 附近的解

    • 最小二乘法(曲线拟合)组:最小化平方和

    仅优化工具箱就提供了近 20 种求解器,面对如此繁多的选项,用户往往一头雾水。幸好,MATLAB 提供了简单明了的参考工具 —— 优化决策表。可谓一表在手,优化不愁:

    上表中*表示算法由全局工具箱提供。

    我的天呀,你是不是已经被上面的内容吓傻了。看不太懂?没关系。我们现在只需知道有那么一回事即可,不必苦恼。等遇到相应的问题时我们再去结合具体的例子去深入学习和理解。

        2、已知目标函数和约束条件如下,试求解目标函数的最小值。

                                 

           初一看,HPS、PP、EP、P1、I1,……等等,这些是什么东东?别紧张,它们只是变量,把它们当成x,y,z这种常见的变量去看待即可。我数了一下,约束函数中共有19条数学表达式,涉及16个变量。是挺难搞的,用高中的作图法怕是解决不了。别怕,我们有Matlab,通过代码去搞定它。

           好,现在我们开始一步步去求解它。

    a. 首先,根据题目确认这是一个线性规划问题。而线性规划的通用数学表达式和MATLAB标准形式为:

    这个标准形式很重要,上面的A,b,Aeq,beq,lb,ub我们后面要用到。

    b. 对于线性规划的优化求解步骤(也适用于其他优化方案),建议如下:

        1 ) 选择优化求解器

        2 ) 将所有变量合并为一个向量

        3 ) 创建边界约束(lb,ub)

        4 ) 创建线性不等式约束(A,b)

        5 ) 创建线性等式约束(Aeq,beq)

        6 ) 创建目标函数

        7 ) 优化问题求解

        8 ) 结果检验

    上面的求解步骤非常重要,我们的代码整体框架跟求解步骤差不多。

    现在我们按照上面的求解步骤去求解:

    (1)选择优化求解器。

    这道题目是这是一个线性规划问题。求解线性规划问题,我们一般选用linprog。linprog在写代码将要写完才需用到。在第一步我们只需要知道一个线性规划问题,代码按照求解线性规划问题去写即可。

    (2)将所有变量合并为一个向量。

    目标函数和约束条件中共有HPS、PP、EP、P1、I1等16个变量,我们需要将其合并为一个向量。除了合并为一个向量外,我们还将每个变量依次分别赋值1,2,3,4,……16。

    %% 将所有变量合并为一个向量,共16个变量
    variables = {'I1','I2','HE1','HE2','LE1','LE2','C','BF1','BF2','HPS','MPS','LPS','P1','P2','PP','EP'}
    N = length(variables)
    for v = 1:N
        eval([variables{v},'=',num2str(v),';'])
    end

    (3)创建边界约束(lb,ub)

    lb是指low boundary,即最低边界。ub是指up boundary,即最高边界。在这一步中,我们需要把约束条件里的不等式(该不等式只含单个变量,如2500<=P1<=6250,3000<=P2<=9000)找出来,并根据它们的上下边界写代码。

    %% 设置上下限约束(lb<=x<=ub)
    % 设置下限约束,即lb<=x
    lb = zeros(size(variables)); % 1x16的矩阵,每个数都是0
    lb([P1,P2,MPS,LPS]) = [2500,3000,271536,100623];
    % 设置上限约束,即x<=ub
    ub = Inf(size(variables)); % 1想6的矩阵,每个数都是无穷大
    ub([P1,P2,I1,I2,C,LE2])= [6250,9000,192000,244000,62000,142000];

    (4)创建线性不等式约束(A,b)。

    在这一步需要将约束条件里的不等式(该不等式含两个或两个以上变量)找出来,并根据它们的上下边界写代码。

    %% 创建线性不等式约束(A*x<=b)
    A = zeros(3,16); % 3x16的矩阵,每个数均为0,为什么是3x16,因为约束条件有3个不等式
    % 由不等式I1-HE1<=132000得到下面一行代码
    A(1,I1)=1; A(1,HE1)=-1; b(1) = 132000;
    % 由不等式-EP-PP<=12000得到下面一行代码
    A(2,EP)=-1; A(2,PP)=-1; b(2) = -12000;
    % 由不等式-P1-P2-PP<=-24550得到下面一行代码
    A(3,[P1,P2,PP])=[-1,-1,-1];b(3)=-24550;

    (5)创建线性等式约束(Aeq,beq)。

    在这一步需要把约束条件中的等式找出来,并通过移项,让等式的右边为0。

    %% 创建线性等式约束(Aeq*x=beq)
    Aeq=zeros(8,16);beq=zeros(8,1) % 约束条件中共有8个等式
    % 把等式I2=LE2+HE2转化为LE2+HE2-I2=0后,得到下面一行代码
    Aeq(1,[LE2,HE2,I2])=[1,1,-1];
    Aeq(2,[LE1,LE2,BF2,LPS])=[1,1,1,-1];
    Aeq(3,[I1,I2,BF1,HPS])=[1,1,1,-1];
    Aeq(4,[C,MPS,LPS,HPS])=[1,1,1,-1];
    Aeq(5,[LE1,HE1,C,I1])=[1,1,1,-1];
    Aeq(6,[HE1,HE2,BF1,BF2,MPS])=[1,1,1,-1,-1];
    Aeq(7,[HE1,LE1,C,P1,I1])=[1267.8,1251.4,192,3413,-1359.8];
    Aeq(8,[HE2,LE2,P2,I2])=[1267.8,1251.4,3413,-1359.8];

    (6)创建目标函数。

    %% 创建目标函数
    f = zeros(size(variables));
    % 由目标函数0.002614HPS+0.0239PP+0.009825EP
    f([HPS,PP,EP]) = [0.002614,0.0239,0.009825];

    (7) 求解问题

    %% 由linprog实现线性规划问题求解
    options = optimoptions('linprog','Algorithm','dual-simplex');
    % 将前面已经确定的各个参数传入linprog()中
    [x, fval] = linprog(f,A,b,Aeq,beq,lb,ub,options);
    for d=1:N
        fprintf('%12.2f\t%s\n',x(d),variables{d})
    end

    fprintf函数是将求解后每个变量的打印出来。

    求解结果如下:

    下面把完整的源代码贴上:

    clc,clear,close all
    %% 选择优化求解器,线性规划求解可由linprog实现
    
    %% 将所有变量合并为一个向量,共16个变量
    variables = {'I1','I2','HE1','HE2','LE1','LE2','C','BF1','BF2','HPS','MPS','LPS','P1','P2','PP','EP'}
    N = length(variables)
    for v = 1:N
        eval([variables{v},'=',num2str(v),';'])
    end
    
    %% 设置上下限约束(lb<=x<=ub)
    % 设置下限约束,即lb<=x
    lb = zeros(size(variables)); % 1x16的矩阵,每个数都是0
    lb([P1,P2,MPS,LPS]) = [2500,3000,271536,100623];
    % 设置上限约束,即x<=ub
    ub = Inf(size(variables)); % 1想6的矩阵,每个数都是无穷大
    ub([P1,P2,I1,I2,C,LE2])= [6250,9000,192000,244000,62000,142000];
    
    %% 创建线性不等式约束(A*x<=b)
    A = zeros(3,16); % 3x16的矩阵,每个数均为0,为什么是3x16,因为约束条件有3个不等式
    % 由不等式I1-HE1<=132000得到下面一行代码
    A(1,I1)=1; A(1,HE1)=-1; b(1) = 132000;
    % 由不等式-EP-PP<=12000得到下面一行代码
    A(2,EP)=-1; A(2,PP)=-1; b(2) = -12000;
    % 由不等式-P1-P2-PP<=-24550得到下面一行代码
    A(3,[P1,P2,PP])=[-1,-1,-1];b(3)=-24550;
    
    %% 创建线性等式约束(Aeq*x=beq)
    Aeq=zeros(8,16);beq=zeros(8,1) % 约束条件中共有8个等式
    % 把等式I2=LE2+HE2转化为LE2+HE2-I2=0后,得到下面一行代码
    Aeq(1,[LE2,HE2,I2])=[1,1,-1];
    Aeq(2,[LE1,LE2,BF2,LPS])=[1,1,1,-1];
    Aeq(3,[I1,I2,BF1,HPS])=[1,1,1,-1];
    Aeq(4,[C,MPS,LPS,HPS])=[1,1,1,-1];
    Aeq(5,[LE1,HE1,C,I1])=[1,1,1,-1];
    Aeq(6,[HE1,HE2,BF1,BF2,MPS])=[1,1,1,-1,-1];
    Aeq(7,[HE1,LE1,C,P1,I1])=[1267.8,1251.4,192,3413,-1359.8];
    Aeq(8,[HE2,LE2,P2,I2])=[1267.8,1251.4,3413,-1359.8];
    
    %% 创建目标函数
    f = zeros(size(variables));
    % 由目标函数0.002614HPS+0.0239PP+0.009825EP
    f([HPS,PP,EP]) = [0.002614,0.0239,0.009825];
    
    %% 由linprog实现线性规划问题求解
    options = optimoptions('linprog','Algorithm','dual-simplex');
    % 将前面已经确定的各个参数传入linprog()中
    [x, fval] = linprog(f,A,b,Aeq,beq,lb,ub,options);
    for d=1:N
        fprintf('%12.2f\t%s\n',x(d),variables{d})
    end

      3、下面是一个整数规划问题,已知目标函数和约束条件如下,求解目标函数的最大值。

                                          

         求解最大值问题和求解最小值问题本质上是一致的,求解最大值也可以转换为求解最小值。

    例如:本题要求解z=3*x1-2*x2+5*x3的最大值,也就是要求解y=-3*x1+2*x2-5*x3的最小值。求解线性规划最小值问题我们在上面已经学过。本题还有一个比较特殊的问题是,约束条件中的三个变量均为整数,而且是0或1,这也是所谓的0-1规划问题。

    求解整值问题要用到专门的求解器 intlinprog。

    clc,clear,close all
    % 求z=3*x1 - 2*x2 + 5*x3的最大值转化为求y=-3*x1 + 2*x2 - 5*x3的最小值。
    f = [-3;2;-5]; % 创建目标函数
    intcon=[1,2,3];
    A=[1 2 -1; 1 4 1; 1 1 0; 0 4 1]; % 四个不等式中的变量系数
    b=[2;4;3;6]; % 约束条件中不等式右边的常数
    lb=[0,0,0]; % x1,x2,x3=0
    ub=[1,1,1]; % x1,x2,x3=1
    Aeq=[0,0,0];
    beq=0;
    x=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

    我想提一下intcon=[1,2,3]这句代码是怎么回事。

    下面我举一个简单的例子来说明intcon的用法。

    X=[x1,x2,x3,x4,x5,x6],其中x2, x3, x6只能取整数
    intcon = [2,3,6]
    如果所有变量都只能取整数,则:intcon = [1,2,3,4,5,6]; 比较方便的写法是:intcon = 1:6
    如果只有x4取整数,则:intcon = 4;就是约束整形变量

    在本题中,除了x1,x2,x3=0或1外,没有其它的等式了。故Aeq=[0,0,0];beq=0;

     4、图形化应用

    在数学建模竞赛中,我们一般通过代码来进行求解问题,图形化应用可以用来检验结果是否正确。

    MATLAB 在数据分析领域如此受欢迎,除了其提供丰富的内置算法集,还有各类友好的应用界面。在优化工具箱中,也有这么一个强大的工具—— Optimization App,可以在 MATLAB Apps 窗口或者运行 optmitool 命令打开。它是一个交互式的图形化应用工具,无需手写代码,直接在图形界面中设置各类求解器、配置目标函数、约束条件,即可运行优化算法并使中间结果和最终结果可视化。

    在 Optimization App 中,只需点击菜单栏中的 File > Generate Code,即可将 App 中的各项设置自动生成 MATLAB 代码,用户可实现算法的复用和二次开发。

    展开全文
  • 优化理论与方法

    千次阅读 2019-04-23 12:28:47
    优化问题 :eg:,其中x在控制问题中被称为为控制决策变量;在数学优化中叫做决策量。无论是最优控制还是数学优化(数学规划)都是优化问题,即都是这样的形式。 1. 优化的两个基本问题 确定一个优化的必要或/和...

    优化问题 :eg:{min}_xf\left ( x \right ) st. x\in D,其中x在控制问题中被称为为控制决策变量;在数学优化中叫做决策量。无论是最优控制还是数学优化(数学规划)都是优化问题,即都是{min}_xf\left ( x \right ) st. x\in D这样的形式。

    1. 优化的两个基本问题

    • 确定一个优化的必要或/和充分的条件(建模)。
    • 设计一个数值程序(算法的设计+程序的实现)。

    遗传算法在弱优化或无约束优化问题中应用较好。

    2. 优化的相关概念

    静态    vs    动态    数学优化\leftrightarrow最优控制;

    连续    vs   离散    数学优化的离散与连续问题\leftrightarrow控制问题的连续与离散问题;

    凸   vs   非凸   既可能与目标有关,又可能与约束有关;

    完美   vs   满意   结果的完美解与满意解;

    严格   vs   启发   方法在数学上是否严格收敛到最优与否。

    2.1 静态优化(参数优化、数学规划等方法)

    • 对变量进行优化;
    • 约束条件与目标为代数方程或不等式。

    2.2 动态优化(变分问题、最优控制)

    • 对函数进行优化(例如最优决策路径)(函数未知)
    • 目标为积分型泛函;
    • 约束条件包含微分方程。

    2.3 连续优化与离散优化

    • 可行域(决策空间)
    •     0-1规划
    •     整数规划
    • 时间序列
    •     离散时间的动态规划——差分描述
    •     连续时间的动态规划——微分描述

    2.4 确定性优化与随机优化

    • DP 动态优化 确定性;
    • MDP Markov决策过程 随机性

    2.5 凸与非凸

    • 凸集;
    • 凸函数

    2.6 启发与随机化搜索

    • 启发式+随机化=高级启发或超级启发(遗传算法、模拟退火算法、蚁群算法);

    2.7 完美解与满意解

    • 一般需要对满意解进行评价

    3 优化方法

    迭代    vs   解析    计算机喜爱迭代方法,并且这种方法效率高;

    串行    vs    并行    

    求导    vs    搜索

    点对点    vs    集到集

    解析    vs    启发

    注:结构知识绝对重要,搜索方法应当在结构信息的指导下进行搜索。启发、学习、人的才智以及软优化在求解方法中占有重要地位。

    一些常用的迭代方法

    • 梯度法(利用了梯度结构信息)
    • 牛顿法(利用了梯度+Hessen矩阵等结构信息)
    • BFGS (共轭梯度结构信息)
    展开全文
  • 常见的web性能优化方法

    万次阅读 多人点赞 2017-06-07 15:47:49
    前端优化是复杂的,针对方方面面的资源都有不同的方式。那么,前端优化的目的是什么 ?  1. 从用户角度而言,优化能够让页面加载得更快、对用户的操作响应得更及时,能够给用户提供更为友好的体验。  2. 从服务商...
  • 【排序】:冒泡排序以及三种优化

    万次阅读 多人点赞 2019-01-05 12:16:46
    冒泡排序(BubbleSort) 一般冒泡排序的写法 //假设排序arr[] = { 1, 3, 4, 2, 6, 7, 8, 0 }; void BubbleSort(int arr[],int len) { int i = 0; int tmp = 0; for (i = 0;... ...
  • 页面优化

    万次阅读 2014-05-07 10:52:25
    前端优化是复杂的,针对方方面面的资源都有不同的方式。那么,前端优化的目的是什么   1. 从用户角度而言,优化能够让页面加载得更快、对用户的操作响应得更及时,能够给用户提供更为友好的体验。 2. 从...
  • 前端优化方案

    千次阅读 2019-06-11 18:10:10
    1 优化css 1.1 避免使用CSS表达式 用CSS表达式动态设置CSS属性,是一种强大又危险的方式。从IE5开始支持,但从IE8起就不推荐使用了。例如,可以用CSS表达式把背景颜色设置成按小时交替的 尽量减少标签选择器的使用...
  • sql优化的几种方式

    万次阅读 多人点赞 2019-11-11 09:15:50
    一、为什么要对SQL进行优化 我们开发项目上线初期,由于业务数据量相对较少,一些SQL的执行效率对程序运行效率的影响不太明显,而开发和运维人员也无法判断SQL对程序的运行效率有多大,故很少针对SQL进行专门的优化...
  • 优化方法总结:SGD,Momentum,AdaGrad,RMSProp,Adam

    万次阅读 多人点赞 2018-11-21 13:32:30
    1. SGDBatch Gradient Descent在每一轮的训练过程中,Batch Gradient Descent算法用整个训练集的数据计算cost fuction的梯度,并用该梯度对模型参数进行更新:Θ=Θ−α⋅▽ΘJ(Θ)\Theta = \Theta -\alpha \cdot \...
  • intelliJ IDEA 自动优化导入包

    万次阅读 2019-01-23 14:04:58
    Intellij IDEA使用教程相关系列 目录 步骤:Settings→Editor→General→Auto Import,如图所示 选中Optimize imports on the fly和Add unambiguous imports on the fly 勾选Optimize imports on the fly ...
  • C++ 手动开O2优化

    万次阅读 多人点赞 2017-09-02 19:45:47
    O2优化能使程序的编译效率大大提升 从而减少程序的运行时间,达到优化的效果。 C++程序中的O2开关如下所示: #pragma GCC optimize(2) 只需将这句话放到程序的开头即可打开O2优化开关。
  • 超直白win7性能优化方案

    万次阅读 2017-08-30 10:41:43
    超直白win7性能优化方案
  • 数值优化(Numerical Optimization)学习系列-目录

    万次阅读 多人点赞 2015-12-27 19:07:11
    数值优化对于最优化问题提供了一种迭代算法思路,通过迭代逐渐接近最优解,分别对无约束最优化问题和带约束最优化问题进行求解。 该系列教程可以参考的资料有 1. 《Numerical Optimization 2nd》–Jorge Nocedal ...
  • O1优化会消耗少多的编译时间,它主要对代码的分支,常量以及表达式等进行优化。  O2会尝试更多的寄存器级的优化以及指令级的优化,它会在编译期间占用更多的内存和编译时间。  O3在O2的基础上进行更多的优化,...
  • 优化方法答案(部分)

    万次阅读 多人点赞 2019-03-04 10:08:35
    学霸的资料,偷偷拿来与大家共勉…希望有帮助 ^^ 第一章 第二章 第三章 第四章
  • 有时候,在VS调试中,会出现下面的报错: 导致无法进行正常调试的现象。这是因为我们设置了代码优化,在项目/XXX属性中,把代码优化关闭即可 过早优化是万恶之源 ...
  • 优化理论视频网站

    万次阅读 2018-01-24 13:57:18
    找了好久的最优化理论视频,主要是针对凸优化的,视频列表如下 上交大最优化-youku:http://list.youku.com/albumlist/show?id=6461357&ascending=1&page=1 上交大最优化-bilibili:...
  • 优化问题(OPT,convex optimization problem)指定义在凸集中的凸函数最优化的问题。一般形式为: 凸优化问题 虽然凸优化的条件比较苛刻,但仍然在机器学习参数最优化领域有广泛的应用。凸优化问题的优势...
1 2 3 4 5 ... 20
收藏数 2,417,998
精华内容 967,199
关键字:

优化