运筹学 — 无约束非线性规划,约束非线性优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章非线性规划,凌翔 龙建成,交通运输工程学院,凸函数定义：,设,为定义在,n,维欧氏空间,E,中某个凸集,R,上的函数，若对任何实数,以及,R,中的任意两点,和,，恒有：,则称,为定义在,R,上的凸函数。,则称,为定义在,R,上的严格凸函数。,凸函数性质：,性质,1,：,设,为定义在凸集,R,上的凸函数，则对任意实数,函数 也是定义在,R,上的,凸函数,。,性质,2,：,设,和 为定义在凸集,R,上的凸函数，则其和,任是定义在,R,上的凸函数。,凸函数性质：,性质,3,：,设,为定义在凸集,R,上的凸函数，则对任意实数,集合：,是,凸集,。,称为水平集。,凸函数性质：,推论：,有限个凸函数的非负线性组合：,仍为凸函数。,函数凸性的判别：,一阶条件,:,设,R,为,n,维欧氏空间,E,n,上的开凸集，,在,R,上具有一阶连续偏导数，则,为,R,上的凸函数的,充要条件,是，对任意两个不同点,和,，恒有：,函数凸性的判别：,二阶条件,:,设,R,为,n,维欧氏空间,E,n,上的开凸集，,在,R,上具有二阶连续偏导数，则,为,R,上的凸函数的,充要条件,是： 的海赛矩阵 在,R,上处处半正定。,凸函数的极值：,定理：,设,为定义在凸集,R,上的凸函数，则它的任一极小值就是它在,R,上的,最小点,（,全局极小点,），,而且它的极小点形成一个凸集。,定理：,设,为定义在凸集,R,上的可微凸函数，若存在点,，使得对于所有的,有：,则,是,的,R,上的最小点（全局极小点）,凸规划：,定义：,若,为凸集，,是,R,上的凸函数，,则称规划：,为凸规划,定义：,若规划问题：,其中 为凸函数， 为凹函数（或 为凸函数）,，则该规划问题为,凸规划,。,练习,判断下述非线性规划是否是凸规划,s.t,.,下降迭代算法：,迭代法的基本思想：为了求函数,的最优解，首先给定一个初始估计,，然后按照某种算法找出比,更好的解,；,1.,对于极小化问题：,2.,对于极大化问题：,如此可以得到一个解的序列,。若这个解序列有极限,，即：,则称它收敛于,下降迭代算法：,下降迭代算法的步骤：,选定某一初始点,，令,k,：,=0,；,确定搜索方向,；,从,出发，沿方向,求步长,，以产生下一个迭代点,；,检查得到的新点,x,是否为极小值点或近似极小值点。若是，停止迭代。否则，令,k,：,=k+1,，回,2,步继续迭代。,确定最优步长,求以,为变量的一元函数,的极小值点,（一维搜索）,一维搜索重要性质：在搜索方向上所得最优点处的梯度和该搜索方向正交。,迭代终止准则,绝对误差：,相对误差：,目标函数梯度：,为事先给定的足够小的正数。,一维搜索,一维搜索,是所有非线性规划,迭代算法,都要遇到的,共同问题,，而且相对于构造搜索方向问题比较简单。因此我们在这一部分先介绍求解一维搜索问题的方法。,主要有斐波那契法、,0.618,法,、插值法、,求根法（二分法）,等。,一维搜索主要针对,单峰函数,。什么是单峰函数？,单峰函数及其性质,定义,:,设函数 ： ，闭区间 ，若存在点 ，使 在 上严格递减，在 上严格递增，则称函数 为 上的单峰函数， 为 的单峰区间，如下图,单峰区间,和,单峰函数,具有如下性质：,若 是单峰区间 上的单峰函数，极小点为 ，在 中任取两点 ， ，且 ，则（,1,）当 时， ；（,2,）当 时， 。,这个性质说明了，经过函数值的比较后，我们可以把单峰函数,的单峰区间 进行缩小，或者 或者 ，而 仍在区间内。,二分法步骤如下：,第一步：选取初始数据，确定初始搜索区间 ，给出最后区间精度 。,第二步：计算初始试点： ，计算 ，并令,k,:=0,。,第三步：如果， 则令,a,k,+1,=,t,k,b,k,+1,=,b,k,t,k,+1,=(,a,k,+1,+,b,k,+1,)/2,；,否则，,a,k,+1,=,a,k,b,k,+1,=,t,k,t,k,+1,=(,a,k,+1,+,b,k,+1,)/2,。,第四步：计算精度，若,(,b,k,+1,-,a,k,+1,)/(,b,0,-,a,0,) 0.5,3,、第三轮：,a = 0, t,1,=0.438, t,2,=0.708, b=,1.146,b-t,1,=1.146-0.4380.5,1.416,0,t,t,2,t,1,t,2,0=1.1460.5,1.854,0,t,t,2,t,1,2,、第二轮：,a= 0, t,1,=0.708, t,2,=1.146, b=,1.854,4,、第四轮：,a =,0.438,t,1,=0.708, t,2,=0.876,b=1.146,b-t,1,=1.146-0.7080.5,输出：,t,*,=t,2,=0.876,为最优解，最优值为,-0.0798,0,1.416,t,t,1,t,2,k,a,b,t1,t2,f(t1),f(t2),精度,1,-1,1,-0.236,0.236,-0.653,-1.125,2,2,-0.236,1,0.236,0.528,-1.125,-0.97,1.236,3,-0.236,0.528,0.056,0.236,-1.05,-1.125,0.764,4,0.056,0.528,0.236,0.348,-1.125,-1.106,0.472,5,0.056,0.348,0.168,0.236,-1.112,-1.125,0.292,6,0.168,0.348,0.236,0.279,-1.125,-1.123,0.18,7,0.168,0.279,0.111,采用黄金分割法求解下列问题：,初始区间,-1, 1,精度,0.15,练习,无约束优化问题的求解算法,此类无约束最优化问题的求解已被各国学者广泛地研究并取得了丰富的研究成果，至今已有许多有效算法被提出。一般说来，求解此类问题的算法被分成两大类，一类要求导数的信息，而另一类则不要求导数的信息。第一类方法包括最速下降法、广义牛顿法、共轭方向法以及变尺度方法等；第二类方法通常指搜索法，包括,Hooke-,Jeeves,直接搜索法和随机搜索法等。,考虑如下无约束优化问题,梯度法（最速下降法）,1.,梯度法的基本原理：,目标函数,有一阶连续偏导数，具有极小值点,以 表示极小值点的第,k,次近似，为了求其第,k+1,次近似点,，我们在,点沿方向,做,射线,：,将,在,点处展成泰勒级数：,将,在,点处展成泰勒级数：,对于充分小的 ，只要：,即可保证：,这时若取：,就能使目标函数值得到改善。,即：,2.,梯度法的方向确定（负梯度方向）,使上式成立的,有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使,取最小值的,。由线性代数得：,为向量 与 的夹角。,当向量 与 取反向时,取最小值,3.,梯度法的步长确定（一维搜索）,若,具有二阶连续偏导数，在,作,的泰勒展开,对 求导并令其等于零，则得到近似最佳步长：,梯度法（最速下降法）,考虑如下无约束优化问题：,其中函数,f,(x,),具有一阶连续偏导数。,(1),最速下降法采用目标函数的,负梯度,方向为下降方向：,(2),一维搜索确定步长,(3),收敛准则,例题,例：试用最速下降法求下例优化问题的极小点,解：取初始近似点,采用最速下降法求解：,选初始点,X,(0),=(2,-2,1),T,。要求做三次迭代。,Newton,型算法,(,牛顿法,),牛顿方向,!,例,考虑如下无约束优化问题：,选取初始点,x,1,=(0,0),T,，目标函数在,x,1,处的梯度和,Hessian,矩阵分别为：,牛顿方向：,令：,则,x,*,=(0.7732, -,1.1546,),T,第五章 约束极值问题,最优性条件,1.,起作用约束,:,设,为非线性规划的一个可行解，满足所有条件。,不起作用约束（无效约束）,起作用约束（有效约束）,显而易见，等式约束对所有可行点来说都是起作用约束。,最优性条件,2.,可行下降方向,:,设 是非线性规划的一个可行点，现考虑此点的某一方向,D,，若存在实数 ，使对任意 均有：,就称方向,D,为 点的一个,可行方向,。,设 是非线性规划的一个可行点，现考虑此点的某一方向,D,，若存在实数 ，使对任意 均有：,就称方向,D,为 点的一个,可行方向,。,只要：,那么：,设 是非线性规划的一个可行点，对该点的任一方向,D,，若存在实数 ，使对任意 均有：,那么就称方向,D,为 点的一个,下降方向,。,泰勒展开,只要：,即可保证：,即可保证,D,必为,点的下降方向。,如果方向,D,为,点的,可行方向,，又是这个点的,下降方向,，就称它是该点的,可行下降方向,。,定理：,设,是非线性规划的一个,局部极小点,，目标函数,在,处可微，而且：,在,处可微，当,在,处连续，当,则在 点不存在可行下降方向，从而不存在向量,D,同时满足：,库恩,-,塔克条件（,kuhn-Tucker,K-T,条件）,设,是上式非线性规划的一个,极小点,。,1.,若该点位于可行域的内部，该线性规划问题为,无约束问题,。,2.,若 点位于可行域的边界上,假设 点位于某个约束条件的边界上：,如果 点是极小点，则：,与,必须在一条直线上，且方向相反，否则在该点就一定存在可行下降方向。,如果 点有两个起作用约束，如：,若 点为极小值点，那么 必处于 和 的夹角之内。否则在 点一定存在可行下降方向。,有一个起作用约束条件：,有两个起作用约束条件：,有多个起作用约束条件：,将不起作用约束条件包括进上式：,增加条件：,库恩,-,塔克条件,(K-T,条件,):,注：,K-T,条件是确定某点为最优点的必要条件。对于凸规划，,K-T,条件是确定某点为最优点的充要条件,为可行方向。,为下降方向。,为 的可行下降方向。,K-T,条件定义：,设,是非线性规划问题的极小值点，而且,点的所有起作用,约束的梯度 线性无关，则存在,向量：,使下述条件成立：,广义拉格朗日（,Lagrange,）乘子。,K-T,条件,先将该非线性规划问题写成以下形式：,写出其目标函数和约束函数的梯度：,引入拉格朗日乘子,引入拉格朗日乘子,K-T,条件,约束非线性优化问题的求解方法,Zoutendijk,可行方向法,Frank-Wolfe,算法,MSA,算法,惩罚函数法,(SUMT,外点法,),障碍函数法,(SUMT,内点法,),Zoutendijk,可行方向法,可行方向法定义,设,为非线性规划：,的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，应在 点的可行下降方向中选取某一方向,，并确定步长,，使：,若满足精度要求，迭代停止，,就是所要的点。否则，从,出发继续进行迭代，直到满足要求为止。,Zoutendijk,可行方向法：,设,点的起作用约束集非空，为求,点的可行下降方向，可由,下述不等式组来确定向量,：,这等价于由下面的不等式组求向量,和实数,：,现在使 和 （对所有 ）的最大值极,小化，即可将上述选取搜索方向的工作，转换为求解下述线性,规划问题：,为向量,的分量,若最优解为 ，如果求出的 ，则,点不存在可行下降方向。,如果求出的 ，则得到可行下降方向 。,Zoutendijk,可行方向法步骤：,1.,确定允许误差 和 ，选初始近似点 ，并令 。,2.,确定起作用约束指标集：,（,1,）,.,若 ，而且 ，停止迭代，得点 。,（,2,）,.,若 ，而且 ，则取搜索方向,， 然后转向,5,步。,（,3,）,.,若 ，转下一步。,3.,求解线性规划：,4.,检查是否停止：,若满足则停止迭代，得到点,；否则，以,为搜索方向，,并转下一步。,5.,解下述一维极值问题：,此处：,6.,令：,转回,2,步。,解下述非线性规划问题：,解：,取初始可行点：,由于,所以,不是极小点。,现取搜索方向：,从而,分别代入约束条件和目标函数：,从而,求解下述线性规划问题：,由此：,点为可行点,所以,继续迭代下去,最优解：,Frank-Wolfe,算法,Frank,和,Wolfe,于,1956,年提出求解线性约束问题的一种算法，通常简称,F-W,算法。,考虑最优化问题,其中 是 矩阵，秩为 ， 是 维列向量， 是连续可微函数。可行域记为：,(1),MSA,算法通常称为相继平均法（,Method of Successive Averages,）,。,考虑下面的最优化问题,可行域记为 。可以用,MSA,算法进行迭代求解。,MSA,算法,假定在任意点 ，通过求解下面的线性规划问题可以得到,从点 出发的最优可行下降方向：,设最优解为,，构造下降方向。若 ，停止,迭代输出,，否则，确定可行下降方向：,下一个迭代点为：,MSA,算法步长的确定：,与,Frank-Wolfe,算法相比较，这种方法的,优点,是：,在每次迭代过程中，不需要通过求解线性搜索问题得到迭代步长，,迭代步长是预先确定,的。因而,MSA,算法计算简单，具有明显的实用价值。,该方法的,不足,之处在于：,收敛速度比较慢,，由于,MSA,算法没有考虑迭代过程中当时情况。,惩罚函数法,(SUMT,外点法,),考虑非线性规划问题：,为求其最优解，构造一个函数,现把,视为,t,，显然：,再构造无约束问题：,现求解无约束问题：,若该问题有解，假定其解为,，当,则由上式应该有,。所以,也为原问题的最优解。这样一来，就,把有约束问题的求解化成了求解无约束问题。,为了使函数 在 处连续，可导，将函数修改为：,定义惩罚函数,或：,那么，优化问题：,的极小解就为原问题的极小解。,惩罚函数,惩罚项,惩罚因子,M,为充分大的正数。,例题：求解非线性规划,解：构造惩罚函数,极小解：,例题：求解非线性规划,解：构造惩罚函数,例题：,P189,：,7.21,例题：,P189,：,7.22,障碍函数法,(SUMT,内点法,),例题,