数学软件MATLAB课件第六章 非线性规划.ppt

运筹学,Non-linearProgramming,第六章非线性规划,基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法,第一节基本概念,非线性规划问题非线性规划方法概述,一、非线性规划问题引例,例1曲线的最优拟合问题,例2构件容积问题,设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积为S，圆锥部分的高h和圆柱部分的高x2之比为a。确定构件尺寸，使其容积大。,h,二、数学模型,其中x=(x1,x2,.,xn)TRn，,D中的点称为可行解或可行点,三、分类,（1）线性规划：目标函数和约束条件皆为x的线性函数。,（2）非线性规划：目标函数和约束条件中至少有一个是x的非线性函数。,本章讨论非线性规划。,（1）当p=0,q=0,即可行域D=Rn时，(P)可写成,称为无约束非线性规划或无约束最优化问题。,（2）若可行域DRn，(P)称为约束非线性规划或约束最优化问题。,定义1对于非线性规划(P)，若并且存在x*的一个领域,则x*称为局部最优解或局部极小点，称f(x*)为局部最优值或局部极小值。,则称x*为严格局部最优解或严格局部极小点,称f(x*)为严格局部最优值或严格局部极小值。,若使得,使得,四、最优解和最优值,四、最优解和最优值,全局最优解为x*=(1/2,1/2)T,全局最优值为f(x*)=1/2。,1x1,x2,1,x*,若目标函数改为：,其最优解和最优值如何？,五、非线性规划方法概述,迭代法:,按某种方法给出目标函数极小点的一个初始估计，称为初始点。然后按某种特定的迭代规则产生一点列xk，使得xk为有穷点列时，其最后一个点是最优解；当xk是无穷点列时，其极限点是最优解(此时称该方法是收敛的)。,定义3,则称向量p是函数f(x)在点处的下降方向。,定义4,则称向量p是函数f(x)在点处的可行方向。,图例说明。,基本迭代格式,第1步选取初始点,k:=0;,第2步构造搜索方向,第3步根据,，确定步长,第4步,若xk+1已满足某种终止条件，停止迭代，输出近似解.,否则令k:=k+1，转回第2步。,随机性方法是按照某种规则随机产生迭代点,迭代点列依概率收敛到最优解，包括遗传算法,模拟退火算法,神经网络算法等,这类方法具有对函数性质要求低、容易实现等优点,但效率低、可靠性差、不能保证产生优化问题的最优解.,全局优化算法概述,全局优化方法可分为随机性方法和确定性方法.,全局优化算法概述,确定性方法充分利用了问题的解析性质,如函数的凸性、单调性、稠密性等,产生一个确定性的有限或无限点序列,使得该点序列收敛于全局最优解.包括分枝定界算法、区间算法、填充函数法、割平面法、顶点枚举法等,这类算法在理论上有较强的可行性,但对较为复杂的大型优化问题却难于应用.,全局优化方法可分为随机性方法和确定性方法.,第二节凸函数和凸规划,凸函数及其性质凸规划及其性质,一、凸函数及其性质,定义5设,是非空凸集，,如果对任意的,有,则称f是S上的凸函数，或f在S上是凸的。,有,则称f是S上的严格凸函数，或f在S上是严格凸的。,如果对于任意的,若f是S上的（严格）凸函数，则称f是S上的（严格）凹函数或f在S上是（严格）凹的,例1线性函数,在Rn上既是凸函数又是凹函数。,例2函数,证,证,证:(1),定理1,(1)若f(x)是S上的凸函数，,都是S上的凸函数,是S上的凸函数。,是非空凸集。,(2),则,也是S上的凸函数。,凸函数的性质,定理1,(1)若f(x)是S上的凸函数，,是S上的凸函数。,是非空凸集。,凸函数的性质,都是S上的凸函数,(2),则,也是S上的凸函数。,证:(2),定理2设,是非空凸集，,是凸函数，,，则集合,是凸集。,证：,水平集,又因f是S上的凸函数，所以,凸函数的性质,定理3设,是非空开凸集，,，,是函数f在点,处的梯度,（1）f是S上的凸函数的充要条件是,（2）f是S上的严格凸函数的充要条件是,可微，则,凸函数的判定,证(1)必要性.设f是S上的凸函数，则对,代入得,由泰勒公式得,证,（1）,（2）,对,和,充分性.设,定理4设,是非空开凸集，,则f是S上的凸函数的充要条件是f的Hesse矩阵,在S上是半正定的.,注意：该逆命题不成立。,f在S上二阶连续可导,在S上正定时，f是S上的严格凸函数.,凸函数的判定,二次型,二次型函数,其中xRn,A是一个n阶对称矩阵，,所以当且仅当A为半正定矩阵时，f(x)是凸函数。,A为正定矩阵时，f(x)是严格凸函数。,例,二、凸规划及其性质,约束集,如果(P)的约束集D是凸集，目标函数f是D上的凸函数，则(P)叫做非线性凸规划，或简称为凸规划。,非线性规划,定理5对于非线性规划(P)，若,并且f是D上的凸函数，则(P)是凸规划。,皆为Rn上的凸函数，,皆为线性函数,证：,又因f是D上的凸函数，,(P)是凸规划,定理6凸规划的任一局部最优解都是它的全局最优解。,证：,又因f是凸函数，所以,矛盾,例：验证下列规划为凸规划,第三节一维搜索方法,非精确一维搜索方法Goldstein法Armijo法,精确一维搜索方法0.618法Newton法,目标函数为单变量的非线性规划问题称为一维搜索问题,数学模型,由定义知，t*是在a,b上的唯一极小点。,一、基本原理,定义1如果存在一个，使得在区间上严格递减，且在区间上严格递增，则称函数在区间a,b上是单谷的，区间a,b称为的单谷区间。,使得,，称a,b为搜索区间。,不断缩短搜索区间的长度，当区间足够小时,得到所求问题的近似最优解。,在区间a,b上任取两点t1,t2，设t10,令k:=0；,第2步计算,第4步进行一维搜索，求tk使得,第3步,用最速下降法求得最优解是目标函数的一个驻点。,例2用最速下降法求解,解：,经10轮迭代得最优解。,三、共轭方向法,定义设A是n阶是对称矩阵，若,则称p和q是相互A共轭的。,对于非零向量组,则称p0,p1,.,pn-1是A共轭方向组，或称一组A共轭方向。,共轭概念是正交概念的推广。,证,线性无关,共轭方向组中最多含n个向量，且线性无关,反之，n维空间的一组基可以构造一组A共轭方向,共轭方向组的构造,由定理知：,二次严格凸函数的无约束最优化问题,定理6对于问题(QP)，若,组A共轭方向，则由任意初始点,出发，依次沿,则最多经n次迭代可得(QP)的整体最优解。,为任意一,进行精确一维搜索，,由任意初始点出发，依此沿某共轭方向组进行一维搜索求解无优化约束的方法叫共轭方向法。,利用迭代点处的负梯度向量为基础产生一组共轭方向，这种方法叫共轭梯度法。,共轭梯度法,首先，取定初始点x0，,从x0点沿方向p0进行，精确一维搜索求得t0，则,否则，取,（1）,依此进行下去，,（2）,共轭梯度法,否则，取,和沿这些方向的迭代点，,（4）,（3）,从而有,共轭梯度法,（5）,（3）可以写成,公式（5）是由Fletcher和Reeves于1964年提出的，称为F-R公式，用公式（5）求解无约束最优化问题最优解的方法简称为F-R法。,第1步选取初始点x0,给定终止误差0；,第2步计算,第4步进行一维搜索，求tk使得,第3步,F-R法步骤,第5步计算,第6步,第7步用F-R公式取,例2用F-R法求解,解：,利用F-R公式得：,若用某种方法求解(QP)问题，经有限轮迭代可以达到最优解，称此方法具有二次终止性。,F-R法具有二次终止性。,第五节约束最优化方法,约束最优化问题的最优化条件简约梯度法惩罚函数法,一、约束最优化问题的最优化条件,定理1,处可微，,在点x*处连续，,在点x*,划(P)的局部最优解，则存在两组实数,若x*是非线性规,称约束规范条件,Kuhn-Tucker条件，简称K-T条件,特殊地，对于只有不等式约束的非线性规划问题,若x*是局部最优解，则存在实数,对于只有等式约束的非线性规划问题,一、约束最优化问题的最优化条件,现引进Lagrange函数如下：,一、约束最优化问题的最优化条件,定理2对于问题(P)，若,在点,x*处连续可微，若可行点x*满足(P)的K-T条件，且,是凸函数,是线性函数，则x*,是(P)的全局最优解。,一、约束最优化问题的最优化条件,二、简约梯度法,假设（1）每个可行点至少有m个大于0的分量（2）A的任意m列线性无关,简约梯度法的基本思想是Wolfe于1962年提出,二、简约梯度法,基本思想：类似于单纯性法，将当前点xk的m个最大正分量定为基变量，其余的m-n个分量作为非基变量，那么目标函数作为非基变量的函数求负梯度方向，并依据这一方向构造从xk到xk+1的可行下降方向。,二、简约梯度法,称rN为f在点x处对应于基矩阵B的简约梯度。,首先，求f对非基变量的梯度,二、简约梯度法,其次，在迭代点xk处依据简约梯度构造可行下降方向,二、简约梯度法,这是因为，,二、简约梯度法,综上所述，利用简约梯度,（*）,定理3设f是可微函数，,，,二、简约梯度法,二、简约梯度法,最后，考察如何从点xkDl沿上面构造的可行下降方向pk进行有效一维搜索。,因而取t的上界为,为使,Wolfe法步骤,Wolfe法步骤,例用Wolfe法求解极小化问题,解上面问题可化为下列问题,三、惩罚函数法,罚函数法障碍函数法,基本思想：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数，构造出带参数的增广目标函数，把问题的求解转换为求解一系列无约束非线性规划问题。,罚函数法,考虑问题：,设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。,可行域为D,构造罚函数：,c称为罚参数或罚因子,实际应用中，选取一个递增且趋于无穷的正罚函数参数列ck,于是,罚函数法计算步骤,例用罚函数法求解,解罚函数为,增广目标函数为,原问题转化为求解一系列无约束最优化问题：,用解析法求解上述问题：,因此，罚函数法也称为外点法,障碍函数法,基本思想：在可行区域的边界上筑起一道“墙”，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。,仅考虑带不等式约束的问题,当点x从可行域内部趋于可行域边界时，至少有一个gi(x)趋于0。因此下列函数会无限增大,构造障碍函数：,取一个递减