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

1、第四章非线性规划,凌翔龙建成交通运输工程学院,1,凸函数定义：,设为定义在n维欧氏空间E中某个凸集R上的函数，若对任何实数以及R中的任意两点和，恒有：,则称为定义在R上的凸函数。,则称为定义在R上的严格凸函数。,2,凸函数性质：,性质1：设为定义在凸集R上的凸函数，则对任意实数,函数也是定义在R上的凸函数。,性质2：设和为定义在凸集R上的凸函数，则其和,任是定义在R上的凸函数。,3,凸函数性质：,性质3：设为定义在凸集R上的凸函数，则对任意实数,集合：,是凸集。,称为水平集。,4,凸函数性质：,推论：有限个凸函数的非负线性组合：,仍为凸函数。,5,函数凸性的判别：,一阶条件:设R为n维欧氏空间

2、En上的开凸集，在R上具有一阶连续偏导数，则为R上的凸函数的充要条件是，对任意两个不同点和，恒有：,6,函数凸性的判别：,二阶条件:设R为n维欧氏空间En上的开凸集，在R上具有二阶连续偏导数，则为R上的凸函数的充要条件是：的海赛矩阵在R上处处半正定。,7,凸函数的极值：,定理：设为定义在凸集R上的凸函数，则它的任一极小值就是它在R上的最小点（全局极小点），而且它的极小点形成一个凸集。,定理：设为定义在凸集R上的可微凸函数，若存在点，使得对于所有的有：,则是的R上的最小点（全局极小点）,8,凸规划：,定义：若为凸集，是R上的凸函数，则称规划：,为凸规划,定义：若规划问题：,其中为凸函数，为凹函数

3、（或为凸函数），则该规划问题为凸规划。,9,练习,判断下述非线性规划是否是凸规划,s.t.,10,下降迭代算法：,迭代法的基本思想：为了求函数的最优解，首先给定一个初始估计，然后按照某种算法找出比更好的解；1.对于极小化问题：2.对于极大化问题：如此可以得到一个解的序列。若这个解序列有极限，即：,则称它收敛于,11,下降迭代算法：,下降迭代算法的步骤：选定某一初始点，令k：=0；确定搜索方向；从出发，沿方向求步长，以产生下一个迭代点；,检查得到的新点x是否为极小值点或近似极小值点。若是，停止迭代。否则，令k：=k+1，回2步继续迭代。,12,确定最优步长,求以为变量的一元函数的极小值点（一维搜

4、索）,一维搜索重要性质：在搜索方向上所得最优点处的梯度和该搜索方向正交。,13,14,迭代终止准则绝对误差：相对误差：目标函数梯度：,为事先给定的足够小的正数。,15,一维搜索,一维搜索是所有非线性规划迭代算法都要遇到的共同问题，而且相对于构造搜索方向问题比较简单。因此我们在这一部分先介绍求解一维搜索问题的方法。主要有斐波那契法、0.618法、插值法、求根法（二分法）等。一维搜索主要针对单峰函数。什么是单峰函数？,16,单峰函数及其性质,定义:设函数：，闭区间，若存在点，使在上严格递减，在上严格递增，则称函数为上的单峰函数，为的单峰区间，如下图,17,单峰区间和单峰函数具有如下性质：若是单峰区

5、间上的单峰函数，极小点为，在中任取两点，且，则（1）当时，；（2）当时，。这个性质说明了，经过函数值的比较后，我们可以把单峰函数的单峰区间进行缩小，或者或者，而仍在区间内。,18,二分法步骤如下：第一步：选取初始数据，确定初始搜索区间，给出最后区间精度。第二步：计算初始试点：，计算，并令k:=0。第三步：如果，则令ak+1=tk,bk+1=bk,tk+1=(ak+1+bk+1)/2；否则，ak+1=ak,bk+1=tk,tk+1=(ak+1+bk+1)/2。第四步：计算精度，若(bk+1-ak+1)/(b0-a0)0.5,25,3、第三轮：a=0,t1=0.438,t2=0.708,b=1.1

6、46,b-t1=1.146-0.4380.5,1.416,t2,t1,t20=1.1460.5,t2,t1,2、第二轮：a=0,t1=0.708,t2=1.146,b=1.854,26,4、第四轮：a=0.438,t1=0.708,t2=0.876,b=1.146,b-t1=1.146-0.7080.5,输出：t*=t2=0.876为最优解，最优值为-0.0798,0,1.416,t,t1,t2,27,采用黄金分割法求解下列问题：,初始区间-1,1,精度0.15,练习,28,无约束优化问题的求解算法,此类无约束最优化问题的求解已被各国学者广泛地研究并取得了丰富的研究成果，至今已有许多有效算法被

7、提出。一般说来，求解此类问题的算法被分成两大类，一类要求导数的信息，而另一类则不要求导数的信息。第一类方法包括最速下降法、广义牛顿法、共轭方向法以及变尺度方法等；第二类方法通常指搜索法，包括Hooke-Jeeves直接搜索法和随机搜索法等。,考虑如下无约束优化问题,29,梯度法（最速下降法）,1.梯度法的基本原理：,目标函数有一阶连续偏导数，具有极小值点,以表示极小值点的第k次近似，为了求其第k+1次近似点，我们在点沿方向做射线：,将在点处展成泰勒级数：,30,将在点处展成泰勒级数：,对于充分小的，只要：,即可保证：,这时若取：,就能使目标函数值得到改善。,即：,31,2.梯度法的方向确定（负

8、梯度方向）,使上式成立的有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使取最小值的。由线性代数得：,为向量与的夹角。,当向量与取反向时,取最小值,32,3.梯度法的步长确定（一维搜索）,若具有二阶连续偏导数，在作的泰勒展开,对求导并令其等于零，则得到近似最佳步长：,33,梯度法（最速下降法）,考虑如下无约束优化问题：,其中函数f(x)具有一阶连续偏导数。,(1)最速下降法采用目标函数的负梯度方向为下降方向：,(2)一维搜索确定步长,(3)收敛准则,34,例题,例：试用最速下降法求下例优化问题的极小点,解：取初始近似点,35,36,37,38,39,40,41,采用最速下降法求解：,选

9、初始点X(0)=(2,-2,1)T。要求做三次迭代。,42,Newton型算法(牛顿法),43,44,牛顿方向!,45,46,例,考虑如下无约束优化问题：,选取初始点x1=(0,0)T，目标函数在x1处的梯度和Hessian矩阵分别为：,牛顿方向：,令：,则,x*=(0.7732,-1.1546)T,47,第五章约束极值问题,最优性条件,1.起作用约束:设为非线性规划的一个可行解，满足所有条件。,不起作用约束（无效约束）,起作用约束（有效约束）,显而易见，等式约束对所有可行点来说都是起作用约束。,48,最优性条件,2.可行下降方向:设是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数

10、，使对任意均有：,就称方向D为点的一个可行方向。,49,设是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数，使对任意均有：,就称方向D为点的一个可行方向。,只要：,那么：,设是非线性规划的一个可行点，对该点的任一方向D，若存在实数，使对任意均有：,那么就称方向D为点的一个下降方向。,50,泰勒展开,只要：,即可保证：,即可保证D必为点的下降方向。,如果方向D为点的可行方向，又是这个点的下降方向，就称它是该点的可行下降方向。,51,定理：设是非线性规划的一个局部极小点，目标函数在处可微，而且：,在处可微，当,在处连续，当,则在点不存在可行下降方向，从而不存在向量D同时满足：,52,库

11、恩-塔克条件（kuhn-Tucker,K-T条件）,设是上式非线性规划的一个极小点。,1.若该点位于可行域的内部，该线性规划问题为无约束问题。,2.若点位于可行域的边界上,假设点位于某个约束条件的边界上：,如果点是极小点，则：,与,必须在一条直线上，且方向相反，否则在该点就一定存在可行下降方向。,53,如果点有两个起作用约束，如：,若点为极小值点，那么必处于和的夹角之内。否则在点一定存在可行下降方向。,有一个起作用约束条件：,有两个起作用约束条件：,54,有多个起作用约束条件：,将不起作用约束条件包括进上式：,增加条件：,库恩-塔克条件(K-T条件):,注：K-T条件是确定某点为最优点的必要条

12、件。对于凸规划，K-T条件是确定某点为最优点的充要条件,55,为可行方向。,为下降方向。,为的可行下降方向。,56,K-T条件定义：,设是非线性规划问题的极小值点，而且点的所有起作用约束的梯度线性无关，则存在向量：,使下述条件成立：,广义拉格朗日（Lagrange）乘子。,K-T条件,57,先将该非线性规划问题写成以下形式：,写出其目标函数和约束函数的梯度：,引入拉格朗日乘子,引入拉格朗日乘子,58,K-T条件,59,约束非线性优化问题的求解方法,Zoutendijk可行方向法Frank-Wolfe算法MSA算法惩罚函数法(SUMT外点法)障碍函数法(SUMT内点法),60,Zoutendij

13、k可行方向法,可行方向法定义设为非线性规划：,的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，应在点的可行下降方向中选取某一方向，并确定步长，使：,若满足精度要求，迭代停止，就是所要的点。否则，从出发继续进行迭代，直到满足要求为止。,61,Zoutendijk可行方向法：,设点的起作用约束集非空，为求点的可行下降方向，可由下述不等式组来确定向量：,这等价于由下面的不等式组求向量和实数：,62,现在使和（对所有）的最大值极小化，即可将上述选取搜索方向的工作，转换为求解下述线性规划问题：,为向量的分量,若最优解为，如果求出的，则点不存在可行下降方向。,如果求出的，则得到可行下降方向

14、。,63,Zoutendijk可行方向法步骤：,1.确定允许误差和，选初始近似点，并令。,2.确定起作用约束指标集：,（1）.若，而且，停止迭代，得点。,（2）.若，而且，则取搜索方向，然后转向5步。,（3）.若，转下一步。,3.求解线性规划：,64,4.检查是否停止：,若满足则停止迭代，得到点；否则，以为搜索方向，并转下一步。,5.解下述一维极值问题：,此处：,6.令：,转回2步。,65,解下述非线性规划问题：,解：,取初始可行点：,由于,所以不是极小点。,66,现取搜索方向：,从而,分别代入约束条件和目标函数：,从而,67,求解下述线性规划问题：,由此：,68,点为可行点,所以,继续迭代下

15、去,最优解：,69,Frank-Wolfe算法,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,MSA算法,86,假定在任意点，通过求解下面的线性规划问题可以得到从点出发的最优可行下降方向：,设最优解为，构造下降方向。若，停止迭代输出，否则，确定可行下降方向：,下一个迭代点为：,87,MSA算法步长的确定：,88,与Frank-Wolfe算法相比较，这种方法的优点是：在每次迭代过程中，不需要通过求解线性搜索问题得到迭代步长，迭代步长是预先确定的。因而MSA算法计算简单，具有明显的实用价值。该方法的不足之处在于：收敛速度比较慢，由于MSA算法没有考虑迭代过程中当时情况。,89,惩罚函数法(SUMT外点法),考虑非线性规划问题：,为求其最优解，构造一个函数,现把视为t，显然：,再构造无约束问题：,90,现求解无约束问题：,若该问题有解，假定其解为，当则由上式应该有。所以也为原问题的最优解。这样一