精华内容
下载资源
问答
  • 约束优化算法

    千次阅读 2019-09-25 13:13:01
    一、“拉格朗日乘子法和罚函数法都用于将有约束优化问题转化为无约束优化问题” 比如最小化目标函数 ,约束等式为 ,这里的是维向量,是矩阵,,那么使用拉格朗日乘子将约束条件合并到目标函数中,得到拉格朗日...

    下面内容是根据自己看书,对拉格朗日乘子法、罚函数法、增广拉格朗日乘子法做一个小结:

    一、“拉格朗日乘子法和罚函数法都用于将有约束的优化问题转化为无约束的优化问题”


    • 比如最小化目标函数 f(x) ,约束等式为  Ax-b=0  ,这里的xn维向量,Am*n矩阵,,那么使用拉格朗日乘子将约束条件合并到目标函数中,得到拉格朗日函数:L(x,\lambda)=f(x)+{\lambda}'(Ax-b)
    • 对变量和拉格朗日乘子的更新遵循这两个式子:x_{k+1}=arg min_{x} L(x,\lambda_{k});    \lambda_{k+1}=\lambda_{k}+\mu_{k}(Ax_{k+1}-b),这里的\mu_k是步长
    • 这里涉及到对偶方面的相关知识,我在这里的知识比较欠缺,所以就只是说明一下拉格朗日乘子法是这么个东西,后面再加一篇博客讲清楚点。

    • 罚函数添加的项跟拉格朗日乘子法不同。但顾名思义,就是对约束条件之外的点进行惩罚,或者说进行最小化处理
    • 罚函数可以有两种添加方式:加法罚函数,即直接把惩罚项p(x)与目标函数相加;另一种是乘法罚函数,将惩罚项和目标函数相乘,通常加法罚函数的使用更多,个人感觉应该是为了后面的求解更加方便,而且加法罚函数在目标函数中会先乘以惩罚系数\rho再加上目标函数,也就是f(x)+\rho*p(x),用来选择一个适当的权重,也可以认为是标志惩罚的分量,所以一般取值是大于0的
    • p(x)内部是怎么设置的,下面分成等式和不等式约束两种进行说明

    在等式约束中,对于约束条件为f(x)=0,罚函数取p(x)=f^{2}(x)。即满足等式时该项为0,不满足该项时取平方加到目标函数中对它做最小化处理;

    在不等式约束f(x)\geq 0中有两种形式,内罚p(x)=\frac{1}{f(x)}或者p(x)=\frac{log(f(x))}{f(x)},而外罚是p(x)=(max\{0,-f(x)\})^{r};

    有三个点要注意:1、内罚法由于f(x)位于分母,所以得到的解并不满足等于0的情况,阻挡了可行集边界的点,而外罚法没有这一缺点;2、外罚法可以用可行集外的点做为初始点,所以要经过比较大量的迭代才能收敛到可行集中,所以收敛慢,而内罚法要求初始点是可行集中的点,所以收敛相对较快;3、通常适用外罚法,因为内罚法的初始点搜索是件很难的事情。


    缺点(书里说的,我自己也不是特别理解)

    拉格朗日乘子法的两个缺点:1、当约束优化问题有局部凸结构时,对偶的无约束优化问题才是良好定义,拉格朗日乘子的更新才是合理的;2、拉格朗日目标函数收敛比较耗时,因为乘子的迭代式上升迭代。

    罚函数法的两个缺点:1、收敛慢,这个应该是跟内罚法的初始点可以选择为可行集外的点有关系,一般都会做随机初始,所以选到可行集外的点就会收敛慢;2、惩罚系数太大会使得无约束优化问题产生病态,造成算法不稳定。

     

    二、“增广拉格朗日乘子法”

    增广拉格朗日乘子法把上面两种方法结合到一起。下面介绍下等式和不等式约束的增广拉格朗日乘子法


    等式约束:比如等式约束为h(x)=Ax-b,罚函数取\frac{1}{2}\|Ax-b\|^2_2,那么增广拉格朗日函数为

    L_{\rho}(x,\lambda)=f(x)+{\lambda}^T(Ax-b)+\frac{\rho}{2}\|Ax-b\|^2_2,而更新的式子如下:

    x_{k+1}=arg min_{x} L_{\rho}(x,\lambda_{k});  \lambda_{k+1}=\lambda_{k}+\rho_{k}(Ax_{k+1}-b),注意这里更新乘子跟前面标准的拉格朗日乘子法不同,步长变成惩罚系数。


    不等式约束:在上面等式约束基础上,添加一不等式约束Bx\preceq h(我不太理解这里为啥用的是这个符号,跟小于等于有什么区别吗,如果你知道麻烦给我留言哦,万分感谢),这时采取的做法是将不等式变成等式,添加松弛变量s,使得Bx+s=h,并构造出如下的拉格朗日目标函数:

    L_{\rho}(x,s,\lambda,v)=f(x)+\lambda^T(Ax-b)+v^T(Bx+s-h)+\frac{\rho}{2}(\|Ax-b\|^2_2+\|Bx+s-h\|^2_2),而且\lambda\succeq 0,v\succeq0,\rho>0

    更新式子如下所示:

    x_{k+1}=arg min_{x} L_{\rho}(x,s_k,\lambda_{k},v_k);  s_{k+1}=arg min_{s\succeq 0} L_{\rho}(x_{k+1},s,\lambda_{k},v_k);

    \lambda_{k+1}=\lambda_{k}+\rho_{k}(Ax_{k+1}-b);  v_{k+1}=v_{k}+\rho_{k}(Bx_{k+1}+s_{k+1}-h)


    这里有几个问题要注意:

    1、增广拉格朗日乘子法不再需要惩罚因子\rho_k增加至无穷大, 只要更新拉格朗日乘子就可以收敛了。所以前面说的罚函数法的病态条件应该指的是要把惩罚因子增加至无穷大才会收敛。

    2、增广拉格朗日乘子法的乘子比普通的拉格朗日乘子法要收敛得更快,而且不再像标准拉格朗日乘子法要求有局部凸结构,也就是说应用范围更广。另外,标准的拉格朗日乘子法的xL(x,\lambda_k)更新的结果,而增广的是L_{\rho}(x,\lambda_k)更新的结果,差别在于有没有惩罚项。

    三、“交替方向乘子法和增广拉格朗日乘子法的关系”

    交替方向乘子法是为了适应大尺度的等式约束问题,即x\in R^n的维数很高。但是变量可以分成很多个子变量x=(x_1,x_2,...,x_r),同时目标函数可以根据这些子变量做一个分解:f(x)=\sum_{i=1}^{r}f_i(x_i),这时候就变成一个分布式优化的问题。而且既然变量可以分解,那么等式约束就变成Ax=\sum_{i=1}^{r}A_ix_i,所以可以得到如下的增广拉格朗日目标函数:

    L_{\rho}(x,\lambda)=\sum_{i=1}^{r}L_i(x_i,\lambda)=\sum_{i=1}^{r}(f_i(x_i)+\lambda^TA_ix_i)-\lambda^Tb+\frac{\rho}{2}\|\sum_{i=1}^{r}(A_ix_i)-b\|^2_2,然后利用下面的式子做更新:

    x^{k+1}_i=arg min _{x_i}L_i(x_i,\lambda_k),i=1,...,r

    \lambda_{k+1}=\lambda_k+\rho_k(\sum^r_{i=1}A_ix^{k+1}_i-b)

     

    以上是我看完这部分的一个小结,但理解上差了很多,只能有大概一个轮廓,如果读者有更好更容易理解的中文或者英文文献资料,麻烦给我留言,或者一起讨论学习,谢谢!!!

    展开全文
  • * * 基本概念及理论 无约束优化算法的一般框架迭代下降算法 几种经典的算法 1最速下降法 2牛顿算法 3拟牛顿算法 4共轭梯度 4. 算法的几个度量指标 1收敛全局/局部 2收敛速度 3运算量 无约束问题的数值方法一般格式 ...
  • 拉格朗日乘子法 约束优化问题的标准形式为 min f ( x, x Rn s.t g (x ) 0,i 1,2, m i h (x ) 0, j 1,2,l j 其中 f , g , h : Rn R i j 约束优化算法的基本思想是 通过引入效用函数的方法将约束优化问题转换为无约束...
  • 提出一种基于混合策略的双种群约束优化算法. 利用双种群存储机制处理约束条件, 并采用约束支配更新不可行解集, 同时采用混合策略进化种群: 在进化前期利用Deb 准则产生可行解, 并保留一部分非劣不可行解参与进化, ...
  • 传统的非线性约束优化算法的精度较低,为了克服这一问题,提出了一种基于粒子滤波的新型优化算法。该算法用于解决非线性约束优化问题,并结合粒子滤波器的模型和机制。首先,利用粒子滤波算法的基本原理建立这种优化...
  • 自适应混合粒子群约束优化算法及其在软测量模型参数估计中的应用
  • 针对约束优化系统易陷局部优化的问题,提出了基于分解协调的多Agent约束优化算法(DCMACOA)。对可分系统,不同于传统的分解协调算法,DCMACOA选用各子系统间的关联变量为协调变量,借助于多Agent及生物免疫的进化...
  • ABC带约束优化算法

    2019-04-12 19:25:58
    人工蜂群算法是模仿蜜蜂行为提出的一种优化方法,是集群智能思想的一个具体应用,它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工蜂个体的局部寻优行为,最终在群体中使全局最优值...
  • 对于约束优化问题,目前提出的差分进化算法大多采用罚函数法,但此方法对罚参数有很强的依赖性.基于此,把约束优化问题中的约束条件当作一个目标函数,从而把约束优化问题转化为有两个目标函数的多目标优化问题.借鉴多...
  • 约束问题的数值方法一般格式;3;牛顿算法;y(k)= gk+1 gk s(k)=x(k+1)-x(k) Hk+1=Hk+ d(k+1)=Hk+1 gk+1;共轭梯度算法;习题11 给定函数f(x)=(6+x1+x2)2+(2-3x1-3x2-x1x2)2 点x=(-4,6)T 1给出X处的最速下降方向 2给出X...
  • 优化相关算法小结

    这里写图片描述

    优化相关算法小结

    展开全文
  • 结合非固定多段罚函数处理约束条件,提出一种动态分级中心引力优化算法用于求解约束优化问题。该算法利用佳点集初始化个体以保证种群的多样性。在每次迭代过程中将种群分为两个子种群,分别用于全局搜索和局部搜索,...
  • 为了解决无导数的线性无约束优化问题,提出了无约束非线性优化的无导数漏斗方法。 该研究提出了新的基于插值的技术。 本文的主要工作取决于一些矩阵计算技术。 求解线性系统,以在每次迭代时获得所需的二次模型。 ...
  • 如果是有约束优化问题,我们还是假设问题是凸的(非凸难啊)、目标函数可微(不可微可以用次梯度和无梯度),且限定一下优化问题只有一个等式约束(不等式可以用内点法,但是额我还没看(◡‿◡))。即,我们的标准问题为:...

    如果是有约束优化问题,我们还是假设问题是凸的(非凸难啊)、目标函数可微(不可微可以用次梯度和无梯度),且限定一下优化问题只有一个等式约束(不等式可以用内点法,但是额我还没看(◡‿◡))。即,我们的标准问题为:

    计算它的KKT条件:

    【解约束优化问题就不得不用到KKT条件了,解KKT条件(如果可解的话),那么相当于一次性把原问题和对偶问题的最优解都解出来了。目前有一个从KKT条件出发得出的算法,就叫做拉格朗日乘子法】

    1.先计算几个优化问题的KKT条件热身一下

    • KKT条件是线性方程组
      比如:

      其中
      一般是不可逆的(这样
      才会是有一个解集的),否则可逆矩阵的方程组有唯一解就谈不上要优化了。

      计算这个问题的KKT条件为:

      【会发现,这时候KKT条件也是一个线性的方程组,主要原因就是
      是线性的
      ,这个时候就可以用Gauss-Seidel等解线性方程组的方法求解最优值了。这样的情况不需要什么下降算法,本质就是求解线性方程组】
      【当然,你也可以转化为求无约束优化的对偶问题。】
    • KKT条件不是线性的方程组:(比如
      往往不是一个线性函数)

      如果
      不是一个
      的线性函数,自然会想到要找一个办法把它变成线性。比如如果二次可微的话,可以找一个点,然后把梯度在这个点一阶展开,这就需要函数是二阶可微的。

      不过如何函数都是二阶可微的话,可以像牛顿法那样更快的处理。我们选取一个点
      ,把原问题等价为新的优化问题

      这是一个关于
      的新的优化问题。为了让原问题KKT线性,先对新问题目标函数做二阶泰勒展开

      则新问题又被等价为新新问题【严格来说二阶展开的话,应该是被近似为新新问题】

      求解这个新新优化问题的KKT条件为:

      便又回到解线性方程组了。但是这里要注意的是,我们这样近似解出来的是
      ,也就是用上一次的迭代点沿着
      方向展开了得到的
      ,这一个过程我们进行了二阶展开这样的近似操作,并不是求解出了原问题的最优解。

      但是我们可以发现,解出来的
      满足
      ,也就是说
      起码是可行的点,满足

      到这里我们就会思考,可不可以用这个方向去下降呢?答案是最好先别。因为
      只是可行点,不一定相对于
      是下降点。所以我们可以给
      乘上一个步长,对步长做一次线搜索,再来当作下降方向来用。

      由此我们得到带等式约束的牛顿法

      【所以,对于带约束优化问题,KKT条件还是蛮重要的】

    2.拉格朗日乘子法Method of Lagrangian Multiplier/拉格朗日法Lagrangian Method

    ​ 第二个式子乘子的迭代部分,

    肯定是可以换成上一步已经计算好的
    。不过我们先把注意力放在两个式子的迭代方向上。
    • 从鞍点角度理解拉格朗日法
      因为
      ,所以鞍点

      我们知道,如果强对偶性成立,那么鞍点就是最优点。此时

      如果已知某一个分量的最优点,求另一个本质上就是求拉格朗日函数对于单个变量的最优解。接下来分类讨论下:
      • 当已知
        时:

        用梯度下降法迭代求解
        。因为
        ,所以我们的迭代算法为

        但是我们不可能真的已知
        是什么,所以我们用
        近似。这便是拉格朗日法的关于
        的迭代部分:
      • 当已知
        时:

        同理得到

        【要注意到
        是对
        求极大得到的,所以上面的迭代方向就是梯度方向,而不是负梯度方向】

        我们同样不可能真的已知
        是什么,所以我们用
        近似。这便是拉格朗日法的关于
        的迭代部分:

    【所以,拉格朗日法实际上是在求

    的鞍点,来得出原问题的最优解】
    • 从罚函数的角度理解拉格朗日法
      我们把带等式约束的原问题的KKT条件:

      改写成一个罚函数的样子,去当作一个新的优化问题来解:
      特点:这个新的无约束优化问题的解就是满足KKT条件的点。某种意义上说,相当于把原问题转化成了无约束优化问题。
      咱们当然可以去求这个新问题的目标函数的负梯度方向,然后梯度下降求最优解:


      上边这个式子(二次型),当
      不全为
      时,会大于等于
      。即:
      时,
      的一个下降方向(和负梯度方向同向)。

      而上面这个条件是成立的。因为原问题凸,所以Hessian矩阵半正定。而当随着迭代
      的时候,
      ,那么大部分情况下
      都是正定的。另外,只要
      还没有到达最优解,
      就一直满足,当
      时,
      ,此时
      ,算法也就停止更新了。

      【对拉格朗日法进行理论分析很有意义,但是这个算法实际运行起来速度很慢,所以为了提高一下效率,诞生了下一节的增广拉格朗日法。】
    展开全文
  • 简介:最近在看逻辑回归算法,在算法构建模型的过程中需要对参数进行求解,采用的方法有梯度下降法和无约束优化算法。之前对无约束优化算法并不是很了解,于是在学习逻辑回归之前,先对无约束优化算法中经典的...
  • 优化学习 学习笔记 一、牛顿法(Newton’s method\text{Newton's method}Newton’s method) 1.推导 在最速下降法中,我们的方向: dk=arg⁡min⁡v{f(xk+v)∣∥v∥=1} d^k=\arg\min_v\lbrace f(x^k+v)\...
  • 梯度下降法是最经典、最简单的算法,要求目标函数一阶可微无约束,有m,M\textbf{m,M}m,M控制凸性。 学习笔记 一、梯度下降法 形如: dk=−∇f(xk)Repeatdk=arg⁡min⁡f(xk+αdk)αmax⁡≥α≥0xk+1=xk+αkdkUntil&...
  • 优化学习 拉格朗日法用得不多,但需要深入理解,方便学习另一种使用很广的算法。 学习笔记 一、拉格朗日法(lagrangian method\text{lagrangian method}lagrangian method) 前面我们讲到,所有的方法都...
  • 优化学习 学习笔记 一、有约束凸问题分析 首先,介绍一下log barrier\text{log barrier}log barrier方法: min⁡f0(x)s.t.fi(x)≤0i=1⋯mhi(x)=0i=1⋯p⇔min⁡f0(x)−∑i=1muilog⁡(−fi(x))  ...
  • 优化学习 最速下降法实为最陡下降法,收敛性质类似于梯度下降法。 学习笔记 一、最速下降法 定义一个和xkx^kxk同维度的向量vvv,那么有: min⁡xf(x)⇔Repeatmin⁡vf(xk+v) \min_xf(x)\Leftrightarrow\text{Repeat...
  • 优化学习 我们前面说过,拉格朗日法在实际中应用不大。为什么呢?因为α\alphaα的取值很难取,这就导致拉格朗日法鲁棒性很低,收敛很慢,解很不稳定。于是就有了今天的增广拉格朗日法和ADMM。 学习笔记 一、增广...
  • 一维无约束优化算法——进退法

    千次阅读 2011-05-14 20:48:00
      <br />function [minx,maxx]=minJT(f,x0,h0) %进退法求极值区间 %2011/5/14 %目标函数:f %初始点x0 %初始步长h0; format long; x1=x0; k=0;...
  • 针对带有线性等式和不等式约束的无确定函数形式的约束优化问题, 提出一种利用梯度投影法与遗传算法、同时扰动随机逼近... 将上述约束优化算法应用于典型约束优化问题, 其仿真结果表明了所提出算法的可行性和收敛性.</p>
  • 约束优化进化算法

    2021-02-23 13:56:50
    约束优化进化算法
  • 优化算法-无约束优化

    2019-09-30 00:55:20
    约束优化的常见算法 无约束优化问题可以表示为: ...经典的优化算法可以分为直接法和迭代法两大类。 直接法 直接法,就是能够直接给出优化问题的最优解的方法,这种方法能够通过一个解析式直接求出对应的最优...
  • 优化原理与方法 第 8 讲 * 3.5 有约束问题优化算法 一Zoutendijk可行方向法不等式约束问题 利用一个线性规划子问题寻求可行下降方向 即寻找方向d在满足可行的前提下使目标下降 进一步改写为线性规划问题 j称为推开...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,614
精华内容 1,445
关键字:

约束优化算法