精华内容
下载资源
问答
  • 最优化方法

    2018-10-25 13:31:59
    不用求导的最优化求解方法坐标轴下降法前向梯度算法 对于无约束的最优化问题,可以采用最小二乘法,梯度下降,牛顿法,拟牛顿法等来求解。但是当方程无法求导的时候(lasso回归)上述方法都失效了。可以采用下面的...

    1 优化目标的函数

    1.1 无约束优化

    在这里插入图片描述

    1.2 约束优化

    在这里插入图片描述在这里插入图片描述

    1.3 等式约束

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    容易发现,在关键的极小值点处,f(x)的负梯度和h(x)的梯度在同一直线上,如下图左下方critical point的蓝色和红色箭头所示。
    注意图中所示是同向的,但是这里并不一定是同向,有可能反向(因为等式约束h(x)=0,把h(x)变成-h(x)求解是一样的,这个时候h(x)的梯度就相反了)
    在这里插入图片描述
    由此可知,在极小值点,h(x)和f(x)的梯度在同一线上,有
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述特别注意:优化问题是凸优化的话,通过上图两个条件求得的解就是极小值点(而且是全局极小)。不是凸优化的话,这两个条件只是极小值点的必要条件,还需要附加多一个正定的条件才能变成充要条件,如下图所示(半正定得到的是极小,正定得到的是严格极小)。
    在这里插入图片描述

    1.4 不等式约束

    对于不等式约束g(x)<=0,和等式约束h(x)=0不一样,h(x)=0可以在平面上画出一条等高线,而g(x)<=0是一个区域,很多个等高线堆叠而成的一块区域,我们把这块区域称为可行域。

    不等式约束分两种情况来讨论,第一种是(不考虑可行域限制时的)极小值点落在可行域内(不包含边界),第二种是(不考虑可行域限制时的)极小值点落在可行域外(包含边界)。
    下面举两个例子来解释这两种情况,然后总结两种情况给出转换求解。

    1.4.1 极小值点落在可行域内(不包含边界)

    在这里插入图片描述在这里插入图片描述

    1.4.2 极小值点落在可行域外(包含边界)

    在这里插入图片描述在这里插入图片描述

    1.4.3 总结

    极小值点落在可行域内(不包含边界):这个时候可行域的限制不起作用,相当于没有约束,直接f(x)的梯度等于0求解,这个时候g(x极小值点)<0(因为落在可行域内)。

    极小值点落在可行域外(包含边界):可行域的限制起作用,极小值点应该落在可行域边界上即g(x)=0,类似于等值约束,此时有g(x)的梯度和f(x)的负梯度同向。
    在这里插入图片描述总结以上两种情况,可以构造拉格朗日函数来转换求解问题。对于不等式约束的优化,需要满足三个条件,满足这三个条件的解x*就是极小值点。这三个条件就是著名的KKT条件,它整合了上面两种情况的条件。

    特别注意:优化问题是凸优化的话,KKT条件就是极小值点(而且是全局极小)存在的充要条件。不是凸优化的话,KKT条件只是极小值点的必要条件,不是充分条件,KKT点是鞍点,是可能的极值点。也就是说,就算求得的满足KKT条件的点,也不一定是极小值点,只是说极小值点一定满足KKT条件。
    在这里插入图片描述不是凸优化的话,还需要附加多一个正定的条件才能变成充要条件,如下图所示(半正定得到的是极小,正定得到的是严格极小)。
    在这里插入图片描述

    1.5 优化问题总结

    拓展一下,对于同时有多个等式约束和多个不等式约束,构造的拉格朗日函数就是在目标函数后面把这些约束相应的加起来,KKT条件也是如此,如下图所示。

    在这里插入图片描述
    考虑凸优化问题:
    对于无约束的优化问题,直接令梯度等于0求解。
    对于含有等式约束的优化问题,拉格朗日乘子法,构造拉格朗日函数,令偏导为0求解。
    对于含有不等式约束的优化问题,同样构造拉格朗日函数,利用KKT条件求解。

    2. 最优解求解方法

    2.1 需要求导的方法

    目标函数知道以后,可以采用最小二乘法,梯度下降,牛顿法,拟牛顿法等来求解。梯度下降法我们都很清楚了,下面介绍一下牛顿法:

    2.1.1 牛顿法

    牛顿拉夫森迭代法求解方程f(x)=0:
    在这里插入图片描述

    2.2 不需要求导的方法

    但是当方程无法求导的时候(lasso回归)上述方法都失效了。可以采用下面的方法

    2.2.1 坐标轴下降法

    在这里插入图片描述在这里插入图片描述

    2.2.2 前向梯度算法

    在这里插入图片描述在这里插入图片描述

    附录 函数距离

    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 最优化方法:深度学习最优化方法

    千次阅读 2016-08-18 14:33:32
    深度学习最优化算法 ...深度学习框架中常见的最优化方法,如tensorflow中的最优化方法及相关参数如下: tf.train.Optimizer tf.train.GradientDescentOptimizer tf.train.AdadeltaOptimizer tf.tr...

    http://blog.csdn.net/pipisorry/article/details/52135832

    深度学习最优化算法

    深度学习框架中常见的最优化方法。

    tensorflow tf.keras.optimizers中的最优化方法及相关参数如下:

    Adadelta、Adagrad、Adam、Adamax、Ftrl、Nadam、Optimizer、RMSprop、SGD

    [https://www.tensorflow.org/api_docs/python/tf/keras/optimizers][tensorflow Optimizers]

    pytorch中的最优化方法及相关参数如下:

    SGD、Adagrad、Adadelta、RMSprop、Adam、AdamW、SparseAdam、Adamax、ASGD、LBFGS、Rprop

    [https://pytorch.org/docs/stable/optim.html#]

     

    基本算法

    SGD 随机梯度下降(Stochastic Gradient Descent)

            此处的SGD一般指mini-batch gradient descent。SGD就是每一次迭代计算mini-batch的梯度,然后对参数进行更新,是最常见的优化方法。即:

    θ^t+1 = θ^t + delta(θ^t)

    其中,η是学习率,g_t是梯度SGD完全依赖于当前batch的梯度。

    缺点:SGD 的缺点在于收敛速度慢,可能在鞍点处震荡,并且如何合理的选择学习率是 SGD 的一大难点。

    具体为1 选择合适的learning rate比较困难- 对所有的参数更新使用同样的learning rate。对于稀疏数据或者特征,有时我们可能想更新快一些(lz稀疏特征少,不平滑,影响更大),对于不经常出现的特征,对于常出现的特征更新慢一些,这时候SGD就不太能满足要求了。2 SGD容易收敛到局部最优,并且在某些情况下可能被困在鞍点【查阅论文发现,其实在合适的初始化和step size的情况下,鞍点的影响并没这么大】。

    [最优化方法:梯度下降(批梯度下降和随机梯度下降)]

    动量Momentum

          如果把要优化的目标函数看成山谷的话,可以把要优化的参数看成滚下山的石头,参数随机化为一个随机数可以看做在山谷的某个位置以0速度开始往下滚。目标函数的梯度可以看做给石头施加的力,由力学定律知:F=ma,所以梯度(施加的力)与石头下滚的加速度成正比。因而,梯度直接影响速度,速度的累加得到石头的位置,对这个物理过程进行建模,可以得到参数更新过程为:

    启发式算法:物体的动能 = 上一个时刻的动能 + 上一时刻的势能差(相对于单位质量),当前的速度取决于上一个时刻的速度和势能的改变量。由于有阻力和转换时的损失,所以两者都乘以一个系数。

    这样在更新参数时,除了考虑到梯度以外,还考虑了上一个时刻参数的历史变更幅度。如果参数上一次更新幅度较大,并且梯度还不小(当前还远未到达谷底),那么再更新时也应该很猛烈(不一定更猛烈,因为还有系数嘛,但是正因为有系数,不好定,所以不怎么自适应)。

    # Momentum update
    v = momentum * v - learning_rate * dx # integrate velocity
    x += v # integrate position

    代码中v指代速度,其计算过程中有一个超参数momentum,称为动量(momentum)。虽然名字为动量,其物理意义更接近于摩擦,其可以降低速度值,降低了系统的动能,防止石头在山谷的最底部不能停止情况的发生(除非momentum为0,不然还是停不下来的,可能通过NAG解决部分问题,但是怎么说momentum和nag都容易在谷底震荡停不下来,可以看下面的“鞍点”和“损失平面等高线”动图)。

    动量的取值范围通常为[0.5, 0.9, 0.95, 0.99],一种常见的做法是在迭代开始时将其设为0.5,在一定的迭代次数(epoch)后,将其值更新为0.99。

    在实践中,一般采用SGD+momentum的配置,相比普通的SGD方法,这种配置通常能极大地加快收敛速度。faster convergence and reduced oscillation振荡。

     

    NAG 加速梯度法(Nesterov accelerated gradient,NAG)

          还是以小球的例子来看,momentum方式有个缺点就是在临近最优点附近控制不住速度(梯度为0了,但是moment不为0,还是有速度,还会运动;lz并且快到最优点时,势能系数*势能还是>0的,还会运动)。我们希望小球很smart,它可以预判后面的"地形",要是后面地形还是很陡,那就继续坚定不移的大胆走下去;不然的话咱就收敛点。当然,小球自己也不知道真正要走到哪里,所以这里(θ−γv_{t−1})作为近似下一位置

    vt=γvt−1+η∇θJ(θ−γvt−1).  θ=θ−vt.

    Hinton的slides是这样给出的:

    momentum首先计算一个梯度(短的蓝色向量,势能),然后在加速更新梯度的方向进行一个大的跳跃(长的蓝色向量,动能);两个blue vectors分别理解为梯度和动能,两个向量和即为momentum方式的作用结果。

    nesterov项首先在之前加速的梯度方向进行一个大的跳跃(棕色向量,动能),计算梯度然后进行校正(绿色梯向量,势能)(反着来也没问题);靠左边的brown vector是动能,可以看出它那条blue vector是平行的,但是它预测了下一阶段的梯度是red vector,因此向量和就是green vector,即NAG方式的作用结果。

    -柚子皮-

     

    其实,momentum项和nesterov项都是为了使梯度更新更加灵活,对不同情况有针对性。但是,人工设置一些学习率总还是有些生硬(之前所讲的方法中所有参数在更新时均使用同一个learning rate),接下来介绍几种自适应学习率的方法。

    自适应学习率算法

    Adagrad

    Adagrad的每一个参数的每一次更新中都使用不同的learning rate,其实是对学习率进行了一个约束。即:

     (学习率为,当前梯度g_t在“所有历史梯度和”中的占比,占比大则更新快。这里很明显可以想到,应该只看最近几个历史梯度和更好,所以有了后面的adadelta)

    对迭代次数 t,基于每个参数之前计算的梯度值,将每个参数的学习率η按如下方式修正:

    其中G是一个对角阵,对角线上的元素是从一开始到 t 时刻目标函数对于参数梯度的平方和;\epsilon是一个平滑项,以避免分母为 0 的情况,它的数量级通常在1e^-8;一般超参数 η 就取 0.01。有趣的是,如果不开方的话,这个算法的表现会变得很糟。

    因为在其对角线上,含有过去目标函数对于参数 梯度的平方和,我们可以利用一个元素对元素的向量乘法,将我们的表达式向量化:

    [深度解读最流行的优化算法:梯度下降]

    特点:

    • 前期g_t较小的时候, regularizer较大,能够放大梯度;后期g_t较大的时候,regularizer较小,能够约束梯度;
    • 主要优势之一,是它不需要对每个学习率手工地调节。
    • 适合处理稀疏梯度。("It adapts the learning rate to the parameters, performing larger updates for infrequent and smaller updates for frequent parameters." 它对不同的参数调整学习率,具体而言,对低频出现的参数进行大的更新(lz因为累积和小),对高频出现的参数进行小的更新。因此,他很适合于处理稀疏数据,对于稀疏数据上有着良好的表现。)

    缺点:

    • 由公式可以看出,仍依赖于人工设置一个全局学习率
    • η设置过大的话,会使regularizer过于敏感,对梯度的调节太大
    • 主要劣势,是它在分母上的 Gt 项中积累了平方梯度和,中后期将会越来越大(每次加入的项总是一个正值),使gradient->0,使得训练提前结束——此时,这个算法已经不能从数据中学到额外的信息。RMSprop 和 Adadelta 都是为了解决 Adagrad 学习率急剧下降问题的。

    然而一般大多数自适应的learning rate都是有根据变化幅度而更改,并且具有逐渐收敛的特性。所以这种启发式方法仅是一种可行性方式,并不是唯一的,也绝不是最好的,把握其本质即可。

    Adadelta

    Adadelta是对Adagrad的扩展。

    计算上的简化,Adagrad会累加之前所有的梯度平方,而Adadelta只累加固定大小w的项,并且也不直接存储这些项,仅仅是近似计算对应的平均值。即:

    超参数设定值: 学习率 η 为 0.001。

    梯度值累积值按如下的方式递归地定义:它被定义为关于过去梯度值的衰减均值(decade average),当前时间 t 的梯度均值  是基于过去梯度均值  和当前梯度值平方  的加权平均,其中 p 是类似上述动量项的权值。此时Adadelta其实还是依赖于全局学习率。

    但后来的方案中,作者做了一定处理,经过近似牛顿迭代法之后:

    (其中,超参数一般设定为 0.9;E代表求期望。pytorch当前的adadelta基本就是这个版本的。)

    此时,可以看出Adadelta已经不用依赖于全局学习率了。

    因为分母表达式的形式与梯度值的方均根(root mean squared,RMS)形式类似,因而我们使用相应的简写来替换:

    特点:

    • 训练初中期,加速效果不错,很快
    • 训练后期,反复在局部最小值附近抖动

    RMSprop

    RMSprop 是 Geoff Hinton 提出的一种自适应学习率方法,和Adadelta法几乎同时被发展出来,他们解决Adagrad激进的学习率缩减问题。可以算作Adadelta的一个特例,实际上, RMSprop和我们推导出的Adadelta法第一个更规则相同

    当\rho=0.5时,就变为了求梯度平方和的平均数。

    (注:Hinton建议设定 \rho 为0.9,对\eta  而言,0.001是一个较好的默认值。)

    如果再求根的话,就变成了RMS(均方根)。

    此时,这个RMS就可以作为学习率\eta的一个约束:

    特点:

    • 其实RMSprop依然依赖于全局学习率
    • RMSprop算是Adagrad的一种发展,和Adadelta的变体,效果趋于二者之间
    • 适合处理非平稳目标- 对于RNN效果很好

    Adam 适应性动量估计法(Adaptive Moment Estimation)

    Adam(Adaptive Moment Estimation)本质上是带有动量项的RMSprop,它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。

    除了像 Adadelta 和 RMSprop 一样存储了过去梯度的平方 vt 的指数衰减平均值 ,也像 momentum 一样保持了过去梯度 mt 的指数衰减平均值:

          

    m_t、n_t分别是对梯度的一阶矩估计和二阶矩估计,可以看作对期望E|g_t|,E|g_t^2|的估计。
          

    \hat{m_t},\hat{n_t}是对m_t、n_t的校正,这样可以近似为对期望的无偏估计。如果 mt 和 vt 被初始化为 0 向量,那它们就会向 0 偏置,所以做了偏差校正, 通过计算偏差校正后的 mt 和 vt 来抵消这些偏差。

    (后面的n超参可以不要)

    Note:这个格式是不是非常像牛顿迭代法?牛顿迭代法就是二阶收敛的,快。[最优化方法:牛顿迭代法和拟牛顿迭代法]

    可以看出,直接对梯度的矩估计对内存没有额外的要求,而且可以根据梯度进行动态调整,而对学习率形成一个动态约束,而且有明确的范围。

    超参数设定值: 建议 u= 0.9,v = 0.999,ϵ = 10e−8。

    实践表明,Adam 比其他适应性学习方法效果要好。

    特点:

    • 结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点
    • 对内存需求较小
    • 为不同的参数计算不同的自适应学习率
    • 也适用于大多非凸优化- 适用于大数据集和高维空间

    Adamax

    Adamax是Adam的一种变体,此方法对学习率的上限提供了一个更简单的范围。公式上的变化如下:

    可以看出,Adamax学习率的边界范围更简单。

    Nadam

    Nadam类似于带有Nesterov动量项的Adam。Much like Adam is essentially RMSprop with momentum, Nadam is Adam with Nesterov momentum.[https://www.tensorflow.org/api_docs/python/tf/keras/optimizers/Nadam]

    公式如下:

    可以看出,Nadam对学习率有了更强的约束,同时对梯度的更新也有更直接的影响。

    一般而言,在想使用带动量的RMSprop,或者Adam的地方,大多可以使用Nadam取得更好的效果。

    -柚子皮-

     

    不同最优化算法对比

    经验之谈

    • 对于稀疏数据,尽量使用学习率可自适应的优化方法,不用手动调节,而且最好采用默认值。
    • 如果在意更快的收敛,并且需要训练较深较复杂的网络时,推荐使用学习率自适应的优化方法。
    • SGD通常训练时间更长,但是在好的初始化和学习率调度方案的情况下,结果更可靠。
    • Adadelta,RMSprop,Adam是比较相近的算法,在相似的情况下表现差不多。
    • 在想使用带动量的RMSprop,或者Adam的地方,大多可以使用Nadam取得更好的效果。

    学习速率 alpha

    如果 alpha 设置得非常大,那么训练可能不会收敛,就直接发散了;
    如果 alpha 设置的比较小,虽然可以收敛,但是训练时间可能无法接受;
    如果 alpha 设置的稍微高一些,训练速度会很快,但是当接近最优点会发生震荡,甚至无法稳定。

                       不同学习速率的训练效果

    理想的学习速率是:刚开始设置较大,有很快的收敛速度,然后慢慢衰减,保证稳定到达最优点。所以,前面的很多算法都是学习速率自适应的。

    How to adjust learning rate

    [https://pytorch.org/docs/stable/optim.html#how-to-adjust-learning-rate]

    效果比较

    几种最优化算法在“鞍点”(optimization on saddle point)和“损失平面等高线”(optimization on loss surface contours)上的表现:

    上面两种情况都可以看出,Adagrad, Adadelta, RMSprop 几乎很快就找到了正确的方向并前进,收敛速度也相当快,而其它方法要么很慢(SGD),要么走了很多弯路才找到(Momentum和NAG)。由图可知自适应学习率方法即 Adagrad, Adadelta, RMSprop, Adam 在这种情景下会更合适而且收敛性更好。[(Image credit: Alec Radford)]

    [深度学习优化器算法详解:梯度更新规则+缺点+如何选择]

    from: http://blog.csdn.net/pipisorry/article/details/52135832

    ref: [http://sebastianruder.com/optimizing-gradient-descent/]

    [深度学习最全优化方法总结比较(SGD,Adagrad,Adadelta,Adam,Adamax,Nadam)]*

    [David Silver 增强学习补充知识——梯度下降法]*

    [深度解读最流行的优化算法:梯度下降]

    [从 SGD 到 Adam —— 深度学习优化算法概览(一)]

     

    展开全文
  • 最优化方法:六、约束最优化方法

    千次阅读 2018-07-25 10:55:56
    最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印) 前面我们已经讨论无约束问题的最优化方法,但实际碰到的问题常常是存在约束的。一般的约束最优化问题的数学模型为: minf(X)s....

    主要参考书目:

    • 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印)

    前面我们已经讨论无约束问题的最优化方法,但实际碰到的问题常常是存在约束的。一般的约束最优化问题的数学模型为:

    minf(X)s.t.{gi(X)0,  i=1,2,,l,hj(X)=0,  j=1,2,,m.

    解决约束问题一般有两种思路,一是通过“罚函数”把约束问题转化为无约束问题解决;二则是构造某种迭代过程使之不能越出可行域。

    1、外点罚函数法

    • 基本思路
      构造一函数为
      F(X,Mk)=f(X)+Mkα(X),

      1
      该方法之所以叫做外点法,是因为在很多情况下(不是所有情况),当惩罚因子比较小的时候,最优解会落在可行域之外,随着惩罚因子的增加,向可行域内部移动,也就是说迭代过程中最优解一直在可行域之外。
    • 特点
      该方法实现了有约束问题向无约束问题的转化,但存在着一些问题:
      (1)惩罚因子选的小会使最优解更容易落在可行域外,而惩罚因子选的大又会使函数的Hesse矩阵性质变坏。
      (2)迭代过程中得到的解常常在可行域之外,难以观察到内点的变化情况也无法求得近似最优解。

    2、内点罚函数法

    • 基本思路
      对于纯不等式约束问题,为使得迭代过程中解一直在可行域内。我们通过罚函数在可行域边界处构造一个“壁垒”使得迭代过程中解不能离开可行域。
      1
    • 特点
      该方法保证了迭代过程中得到的解一直处于可行域内,但仍然面临过三个问题:
      (1)需要找到一个可行的初始点。
      (2)如果搜索步长过大,有可能一步跨过壁垒,所以在搜索过程中应适当控制步长,防止该情况发生。
      (3)无法解决等式约束的问题。

    3、混合罚函数法

    • 基本思路
      为解决内点法不能应对等式约束的问题,采用以下混合罚函数:
      F(X,rk)=f(X)+rki=1l1gi(X)+1rkj=1m[hj(X)]2
    • 外插技术
      F(X,r)的最优解X可以看做r的函数,当我们得到了前几点的X(r)后,可以通过外插法估计下一个最优值,并把该点当做下一次迭代的初始点,以加快收敛速度。
      通常使用两点外插或者三点外插。

    4、约束坐标轮换法

    • 基本思路
      与无约束优化问题的坐标轮换法类似,但是搜索时不再使用一般的以为搜索方法,而采用以下规则:
      1
      该方法可以引入一个步长缩放因子,当在t步长下的搜索已满足该步长下的终止限,而步长并不足够下,则缩短步长进行下一轮搜索。
    • 特点
      该方法算法简单明了,但存在以下问题:
      (1)收敛较慢;
      (2)可能出现“死点”,导致输出伪最优点;
      (3)可能出现在某几个点之间循环的现象。

    5、复合型法

    • 基本思路
      与单纯形法类似,但该方法使用的是顶点更多的复合型。(顶点可以使降维的可能性减小,而且由于约束边界的限制,使用单纯形容易“卡死”在某个地方,而复合型则提供了更多可能的搜索方向)
    • 具体细节
      (1)生成初始复合型
      1
      (2)跑出可行域的点一律认为是最坏的点。
      (3)如果无法利用最坏点搜索(即步长t降的很小仍不符合要求)则改用次坏点替代最坏点,并以此类推。
      (4)关于复合型的顶点数,当n5时,一般取k=2nn>5时一般取k=(1.251.5)n
    • 特点
      属于直接法,对目标函数要求少。
      但其收敛速度较慢,而且不能应对等式约束。
    展开全文
  • 最优化方法 概述

    2018-11-06 10:50:39
    最优化方法 概述

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   
     

    最优化方法--概述

    分类: mathematics 177人阅读 评论(0) 收藏 举报

    目录(?)[+]

    一个简单的问题描述如下:周长一定,围成怎样的形状能使得面积最大。

    公元前212~187年,古希腊数学家阿基米德(Archimedes)就曾证明了已知周长,圆所包围的面积最大的等周问题。这算是一个基本的最优化问题。


    最优化方法定义:应用数学的重要研究领域。它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。

    简单来说,即以最优化数学模型来解决实际运用中的各种最优化问题。

     

    一般数学模型:


    其中的X为n维向量,为实际运用中的解。

    s.t.为英文subject to的缩写,表示受限于。

    F(x)称为目标函数,如上式,我们要求f(x)的最小值。

    H(x)为等式约束;g(x)为不等式约束。

     

    分类:

    根据目标函数与约束函数的不同形式,可以把最优化问题分为不同的类型。

    1)根据约束函数,可分为:无约束最优化,等式约束最优化,不等式约束最优化。

    2)根据目标函数与约束函数类型分类:若f(x),h(x),g(x)都是线性函数,则称为线性规划;若其中至少有一个为非线性函数,则称为非线性规划。

    3)另外,对于特殊的f(x),h(x),g(x),还有特殊的最优化问题。

    目标函数为二次,约束全为线性:二次规划。

    目标函数不是数量函数而是向量函数:多目标规划。

     

    下降算法:

    对于无约束的最优化问题,我们通常给定一个初始的可行点x0,由这个可行点出发,依次产生一个可行点列,x1,x2…xk,使得某个xk恰好是问题的一个最优解,或者该点列收敛到最优解。也就是选取一个可行的方向,再往这个方向行进。这种方法称为下降算法。

    在迭代中,要求f(xk+1)<f(xk).


    在下降算法中,基本的问题有两个:方向与步长。

    对于性能的衡量,也有:收敛于不收敛,局部最优与全局最优。


    常见的下降算法有:

    最速下降法,Newton法,共轭方向法和共轭梯度法,拟Newton法,Powell方向加速法等。

    有约束的最优化问题则可以通过拉格朗日乘数转化为无约束最优化问题。


    其他一些流行的方法有:

    模拟退火,遗传算法,类免疫算法,演化策略,神经网络,支持向量机等。


    解析法与最优性条件:

    不同于前一部分通过迭代求解的方法,我们可以通过一些数学知识来直接求解最优化问题的最优点,这种方法称为解析法。比如我们一阶函数求导得极值的方法。

    所谓的最优性条件,也就是最优点满足的条件。

    不过,一般情况下,很难直接通过最优性条件求解最优化问题。但是最优性条件的研究,对于问题的求解以及判定结束状态都有帮助。

    以下面无约束优化的最优性条件为例:

    对于:

    根据微积分的知识,我们有如下结论:


    也就是无约束最优化问题的最优性条件;相应的我们还有等式约束最优化问题,不等式约束最优化问题的最优性条件。

     


     

    最优化--等式约束最优性条件

    分类: mathematics 182人阅读 评论(0) 收藏 举报

    目录(?)[+]

    所谓的最优性条件就是最优解的性质。

    我们通过最优性条件的研究,能够对于优化的步骤,以及迭代求解时的结束条件有很大帮助。

    最优化问题常见的有无约束优化,等式约束优化,不等式约束优化。这里用两篇blog分别讨论等式约束优化与不等式约束最优化的最优性条件。


    我们首先讨论等式约束的情况下,其最优解满足怎样的性质。


     三维空间:

    以下以三维空间为特例,看看最优解有哪些性质。

     


    如上图,X为局部最优解,那么其必在S1与S2的交线D(及可行域)上,并且目标函数与约束函数的 梯度 共面。如果不共面,那么f(x)梯度向可行域D上的投影不为零。于是沿着这个投影移动,可使得目标函数下降,也就不是最优解。

    根据共面的条件,我们可以推出:      

                           

    也就是三维空间的最优性条件。

     

    等式约束一阶必要条件:

    上述是三维空间上的特殊情况,对于等式约束的一般情况,我们可以通过微积分,来得到关于导函数的一些性质。下面直接写出其完整性质。

    一阶必要条件:


    上式为必要条件,不是充分条件。

     


    具体解法:

    我们可以定义如下的n+l元函数:


    称为lagrange函数。也就是把目标函数与约束函数写在一起求解,并用向量的形式来表示。

    上式分别对x与lamda求导为零求解后,即为可能极值点。

    不过上述的点可能是鞍点,也可能是极值点,具体判断要用到如下的二阶充分条件。

     


    二阶充分条件:

    在满足一阶必要条件的前提下,我们现在要判断所得的可能极值点到底是不是极值点,就要用到二阶充分判断条件:

    若 函数关于x的Hesse矩阵在约束超曲面的切平面上正定,则x就是严格局部极小点。

     

    Hesse矩阵的知识:

    在数学中,海森矩阵(Hessian matrix或Hessian)是一个自变量为向量的实值函数的二阶偏导数组成的方块矩阵,此函数如下:


    如果f所有的二阶导数都存在,那么f的海森矩阵即:


    其中 ,即


     

    小结:等式最优化问题,把约束条件与目标函数写在一起,称为langrang函数,对X,lamda求导取零后,在通过二阶的hesse矩阵是否正定来进一步判断。

     

    KKT条件--不等式约束最优性条件

    分类: mathematics 185人阅读 评论(0) 收藏 举报

    目录(?)[+]

    KKT条件是不等式约束的最优化问题的最优性条件。


    所谓的最优性条件就是最优解的性质。

    我们通过最优性条件的研究,能够对于优化的步骤,以及迭代求解时的结束条件有很大帮助。

    最优化问题常见的有无约束优化,等式约束优化,不等式约束优化。

    上一篇blog讨论过等式约束的最优性条件(http://blog.csdn.net/ice110956/article/details/17557795),这里我们讨论如下的不等式约束最优化,其最优解满足怎样的性质。

     


    可行方向与下降方向:

    下降方向:

    我们知道,在最优化求解的过程中,我们常常使用某种逼近的方法,如梯度下降法等等。那么使得目标函数f(x)变小的方向,也就是下降方向。

    根据微积分的知识,我们知道,取梯度的反方向,可得下降方向。也就是,P* <0,则P是一个下降方向。

    可行方向:

    一般来说,对于目标函数,有一定的约束条件,也就是我们的可行域,我们要在可行域允许的范围内求解。我们求解的方向在可行方位内,则称为可行方向。

    同样的,根据微积分的知识,我们也可以推导得到P* >0为可行方向。

    可行下降方向:

    现在我们要得到即可行,又下降的方向来求解问题,也就是要求得可行下降方向。

    综上,可行下降方向p满足条件为:


    其中f(x)表法向量,ci(x)表大于零的约束条件法向量。


    最优解性质:

    那么,如果X已经是极值点了呢?

    我们把下降方向集合写作S,可行方向集合写作G,如下:


    那么,如果当前点是最优点,应该是无处可去的,也就是没有可行下降方向,也就是,如下图:

     

    于是,我们得到最优点的性质:


    我们接下来推导如何解上面的集合问题。我们从两个引理出发,能够得到两个解,也就是对应的Fritz-John条件与KT条件。我们先来看Fritz-John条件的推导。

     

    Fritz-John一阶必要条件:

     

    我们看下面这个引理:

    Gordan引理:

    设a1,…ar是n维向量,则不存在向量,使得

    成立的充要条件是,存在不全为零的非负实数组,使得


    这条引理证明略,从几何意义上理解,如下:


    如果不存在使得向量ai*d全小于0的向量d,那么ai中不能够全都在某个超平面的一侧。否则,取超平面另一侧的任意一个向量作为d,都能够满足ai*d全小于0.

     

    再看我们上一部分推出的最优解条件:

    当x是最优解时,不存在可行的下降方向p,使得


    也就是不存在:


    把上式中分别看成Gordan引理中的a1,a2,….,ar,于是存在不全为0的数:,使


    这也称为Fritz-John一阶必要条件

     

    完整的定理如下:

    Fritz-John一阶必要条件:

    x为局部最优解,f(x),c(x)在点x可微,则存在非零向量,使得:

     

    上述Fritz-John条件中,如果lamda0=0,那么所得的点与目标函数无关,这样造成无论什么目标函数,只要约束条件一样,得到的可能极值点也就相同。也就是,这个条件过于宽松了。

    于是我们再加一个约束条件,如“有效约束函数的梯度线性无关”,那么lamda0就不会为0了。于是得到了我们如下的KT条件:

     

    KT条件:

     

    还是看一个定理:

    Farkas定理:

    已知a1,….,ar和b为n为向量。所有满足:

     

    的向量,同时也满足不等式的充要条件是:存在非负实数,使得


    上式的证明需要用到凸分析的知识,这里我们从几何意义来看。


    简单来说就是,所有满足与凸锥B中所有向量点乘大于零的向量,都在凸锥A中;

     

    那么,如果一个向量d,满足,那么b就处于a1与ar之间,也就是

    如上图中d1满足条件,d2不满足条件。


    还是两个集合交为空的条件:

    当x为最优解,不存在P,使得:

    反过来,也就是存在p,使得

    根据Farkas定理,约束条件ci(x)组成一个凸锥,f(x)处于这个凸锥之中,也就是:

    这也是KT条件。通过下图,我们能够直观地理解:

    完整地KT条件如下:

    Kuhn-Tucker一阶必要条件:

     

    上面的KT条件与Fritz-John条件,只在f(x)的系数上不同。KT条件是Fritz-John条件的特殊情况。

     

     

    二阶充分条件:

    这里略去,上述Fritz-John条件与KT条件得出的是可能的极致点,还要通过二阶的验证才能分辨是否为鞍点。

     

    凸规划的最优解:

    由于凸规划的良好性质,满足Fritz-John条件或KT条件的点就是其极值点。


    PS:据说blog的公式数量与受欢迎程度成反比,不过我今天一口气发了三篇公式的blog。。。

     

    外罚函数与内罚函数

    分类: mathematics 229人阅读 评论(0) 收藏 举报

    目录(?)[+]

    SUMT技术

    之前的两篇blog讨论了等式最优化的最优性条件和不等式最优化的最优性条件。

    http://blog.csdn.net/ice110956/article/details/17557795 )

    http://blog.csdn.net/ice110956/article/details/17562429 )

    关于无约束问题,我们通过最优性条件能够直接求出解,那么这种方法称为解析法。

    但是,对于有约束问题的一般情况是,我们很难通过最优性条件来得到最优解。通常情况下,使用KKT条件求解时,我们要求与约束个数同阶的矩阵的逆。我们可以容易验证某个点是否是最优解,但是很难直接求解。

    由于无约束的最优化问题我们已经有了许多高效的解法,于是,对于有约束的问题,我们可以转化为求解无约束问题,并且用迭代算法来求解。这么方法由称为序列无约束极小化技术SUMT(SequentialUnconstrained Minimization Technique)

     

    外罚函数法

    我们根据约束的特点,构造某种惩罚函数,然后加到目标函数中去,将约束问题求解转化为一系列的无约束问题。这种“惩罚策略”,对于无约束问题求解过程中的那些企图违反约束条件的目标点给予惩罚。如下图:


    通过上述方法,我们可以把有约束的问题化为无约束问题求解。也就是我们的外罚函数法。

     

    实例:

    我们改写为无约束规划:

    其中,我们设为非常大的数。

    那么,当x1,x2不在可行域上时,后一项由于乘了,变为很大的数,对不在可行域上的点加以惩罚,迫使下一次迭代在可行域周围。

    也就是,最优化(2)式的前一部分,得到最优解;最优化后一部分,使得解在可行域上。

    那么(2)式得到的最优解,会是(1)式的最优解吗?外罚函数收敛吗?考虑到公式的数量与日志受欢迎程度成反比,这里直接给出结论:(2)式收敛,并且最优解为(1)式近似最优解。

     

    具体算法:

    我们用迭代算法来求解,这里直接给出迭代结束条件:

    经证明,外罚函数法式收敛的,上式也随着收敛到0.

    当我们固定系数时,可求解无约束问题得到当前最优解,我们算出Xk之后,判断是否满足结束条件,满足则终止。否则修改惩罚力度,以xk为下一次初始点,,继续迭代。

    步骤如下:

     

    缺点:

    1.由于上述都是近似最优并且近似可行的,近似最优可以接受,但是近似可行在实际运用中让人无法接受。这一点内罚函数可以解决;

    2.根据收敛性,越大越好;但是我们直接求解时,用到求导以及hesse矩阵,越大,越趋于病态,也就是不好解,这是乘子法所要解决的问题。

     

    内罚函数法

    相比于外罚函数法在不可行区域加惩罚,内罚函数法在可行域边界筑起高墙,让目标函数无法穿过,就把目标函数挡在可行域内了。

    这种惩罚策略只适用于不等式约束问题,并要求可行域的内点集非空,否则,每个可行点都是边界点,都加上无穷大惩罚,惩罚也就失去意义了。

    考虑不等式约束:


    当x从可行域

    的内部趋近于边界时,则至少有一个ci(x)趋近于零,因此,不难想到可构造如下的增广的目标函数:


    称为内罚函数或障碍函数,参数r仍称为罚因子。

    上述的内罚函数,当x靠近边界时,会迅速增大,迫使在可行域之内进行求解。

    如下图:

     

    具体算法:

    同外罚函数法类似,我们考虑用迭代算法来求解。每次变化得到一个罚因子rk,从前一步关于罚因子rk-1的最优解出发,得到下一步关于rk的最优解;当满足条件是,迭代结束,得到近似最优解。

    经证明,内罚函数法也是收敛的,迭代结束的条件为

    步骤如下:

     


    小结

    1)        由于无约束最优化问题的解法目前已有许多很有效的算法,如DFP,BFGS等,所以在求解复杂得多的约束优化问题是,工程技术人员一般乐于采用罚函数法——SUMT外点法和内点法。

    2)        内点法适用于解含不等式约束问题,并且每次迭代的点都是可行点,这是设计人员所希望的。但要求初始点为可行域的内点,需要相当的工作量,同时它不能处理等式约束;外点法适于解既含等式约束又含不等式约束的优化问题,初始点可以是可行域之外的点,却不能保证近似最优解是可行的。

    3)        罚函数法对于增广的目标函数的Hesse矩阵的条件数随罚因子增大或减小而增大,造成在求解无约束最优化问题时的困难,如何选择罚因子往往进退维谷。如外罚函数法,欲使得无约束问题接近于原约束问题,应该选择尽可能大的罚因子;但为了减轻求解无约束问题的困难,又应选取较小的罚因子,否则增广矩阵病态。这也是罚函数法的固有弱点。


    解决这些问题,就要用到乘子法,关于乘子法,慢慢再整理出来。


               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • - 最优化方法及其应用/郭科,陈聆,魏友华.-北京:高等教育出版社,2007.7(2013.7重印) 在第四章中,我们解决了确定搜索步长的问题,现在解决确定搜索方向的问题。 1、最速下降法 基本思路 搜索方向总沿着f(X)f...
  • 最优化方法——Newton方法

    千次阅读 2019-03-19 11:03:11
    1. 问题介绍:在最优化方法中,Newton方法是一个比较经典的方法,它常用来求解无约束的优化问题或含有等式约束的优化问题。准确的说,Newton方法一般分为纯Newton方法和拟Newton方法。今天我们考虑的是无约束优化...
  • 非常好的一本书,学习最优化的必备,数值最优化方法高立
  • MATLAB最优化方法

    千人学习 2019-05-14 21:54:51
    结合实例介绍MATLAB最优化工具箱的主要功能。
  • 本文是Deep Learning 之 最优化方法系列文章的RMSProp方法。主要参考Deep Learning 一书。 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最优化方法之...
  • 本文是Deep Learning 之 最优化方法系列文章的Adam方法。主要参考Deep Learning 一书。 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最优化方法之...
  • 本文是Deep Learning 之 最优化方法系列文章的SGD方法。主要参考Deep Learning 一书。 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最优化方法之...
  • 本文是Deep Learning 之 最优化方法系列文章的AdaGrad方法。主要参考Deep Learning 一书。 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最优化方法之...
  • 目录1. 优化算法的结构2. 无约束问题的最优性条件3. 最速下降法3.1. 算法步骤3.2. 算法特点4. 牛顿法4.1....本文是最优化中使用导数的最优化方法的总结 1. 优化算法的结构 优化的步骤一般分为两步,一是...
  • 数值最优化方法

    千次阅读 2017-07-28 11:41:54
    算法来源:《数值最优化方法~高立》 算法目的:实现函数的局部最优化寻找,以二元函数为例,展示了最速下降法和牛顿寻优的算法过程 主要Python模块:numpy,sympy (1)Python实现 (2)MATLAB实现 ...
  • 最优化方法——综述

    2019-07-15 17:52:37
    最优化方法 一、关于该系列的简要说明   最优化方法是17级山东大学数学院理学大数据班的一门必修课,据教授介绍,涵盖算法设计与分析技术、线性规划、图与网络算法等组合最优化理论,推荐参考资料为:   组合最...
  • 最优化方法综述

    千次阅读 2016-11-12 11:47:45
    本篇文章对常用的最优化方法进行简要介绍和比较,主要涉及的方法有: 梯度下降法 牛顿法、拟牛顿法和高斯牛顿法 共轭梯度法 Levenberg–Marquardt 模拟退火法 1. 简介最优化问题简介2. 梯度下降法批量梯度下降法和...
  • 摘要:群体智能优化算法由于其易实现性及其高效性,已成为最优化方法的研究热点。本文介绍该领域一种近年来的新兴起的优化算法鲸鱼优化算法。在介绍其生物机制的基础上,论述了其捕食、攻击过程的数学模型。最后给出...
  • Deep Learning 之 最优化方法 2017年05月21日 22:18:40 阅读数:5910 写在前面本文主要是对Deep Learning一书最优化方法的总结,具体详细的算法,另起博文展开。 整个优化系列文章列表: Deep...
  • 机器学习中的最优化方法(一) 无约束优化方法* 掌握常用的优化方法对机器学习算法而言是必不可少的,本文只介绍无约束问题的优化,后续会介绍有约束的情况。 主要介绍以下几个内容: 1 优化概述 2 无约束问题的优化...
  • 本文是Deep Learning 之 最优化方法系列文章的Momentum(动量)方法。主要参考Deep Learning 一书。 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最优化...
  • 文章链接:Deep Learning 最优化方法之SGD 72615436 本文是Deep Learning 之 最优化方法系列文章 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最...
  • 本文是Deep Learning 之 最优化方法系列文章的Momentum(动量)方法。主要参考Deep Learning 一书。 整个优化系列文章列表: Deep Learning 之 最优化方法 Deep Learning 最优化方法之SGD Deep Learning 最优化...
  • 约束最优化方法之最优性条件

    万次阅读 2017-12-07 20:51:14
    一般性约束最优性条件前面几篇博客主要讲了无约束最优化问题的一些求解方法。从这一篇博客开始将开始讲有约束的最优化方法。首

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,377
精华内容 10,950
关键字:

最优化方法