资源描述
第,*,页,本资料仅供参考，不能作为科学依据。谢谢,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运 筹 学,非线性规划,Non-linear Programming,第1页,第六章 非线性规划,基本概念,凸函数和凸规划,一维搜索方法,无约束最优化方法,约束最优化方法,第2页,第一节 基本概念,非线性规划问题,非线性规划方法概述,第3页,一、非线性规划问题引例,例1,曲线最优拟合问题,第4页,例2 构件容积问题,设计一个右图所表示由圆锥和圆柱面围成构件，要求构件表面积为S，圆锥部分高h和圆柱部分高,x,2,之比为,a,。确定构件尺寸，使其容积大。,h,第5页,二、数 学 模 型,约束集,或,可行域,其中,x,=(,x,1,x,2,.,x,n,),T,R,n,，,D,中点称为,可行解,或,可行点,第6页,三、分 类,（1）线性规划：目标函数和约束条件皆为,x,线性函数。,（2）非线性规划：目标函数和约束条件中最少有一个是,x,非线性函数。,本章讨论非线性规划。,（1）当,p=,0,q=,0,即可行域,D=R,n,时，(P)可 写成,称为无约束非线性规划或无约束最优化问题。,（2）若可行域,D,R,n,，,(P)称为约束非线性规划或约束最优化问题。,第7页,定义 1,对于非线性规划(P)，若 而且存在,x*,一个领域,则,x*,称为,局部最优解,或,局部极小点,，,称,f(x*),为,局部最优值,或,局部极小值,。,则称,x*,为,严格局部最优解,或,严格局部极小点,称,f,(,x*,)为,严格局部最优值,或,严格局部极小值,。,若使得,使得,四、最优解和最优值,第8页,四、最优解和最优值,第9页,全局最优解为,x,*=(1/2,1/2),T,全局最优值为,f,(,x,*)=1/2。,1,x,1,x,2,1,x,*,若目标函数改为：,其最优解和最优值怎样？,第10页,五、非线性规划方法概述,迭代法:,按某种方法给出目标函数极小点一个初始预计，称为初始点。然后按某种特定迭代规则产生一点列,x,k,，使得,x,k,为有穷点列时，其最终一个点是最优解；当,x,k,是无穷点列时，其极限点是最优解(此时称该方法是收敛)。,第11页,定义3,则称向量,p,是函数,f,(,x,)在点 处下降方向。,定义4,则称向量,p,是函数,f,(,x,)在点 处可行方向。,图例说明。,第12页,基本迭代格式,第1步,选取初始点 ,k:=,0;,第2步,结构搜索方向,第3步,依据,，确定步长,第4步,若,x,k,+1,已满足某种终止条件，停顿迭代，输出,近似解.,不然令,k:=k+,1，转回第2步。,第13页,随机性方法,是按照某种规则随机产生迭代点,迭代点列依概率收敛到最优解，包含遗传算法,模拟退火算法,神经网络算法等,这类方法含有对函数性质要求低、轻易实现等优点,但效率低、可靠性差、不能确保产生优化问题最优解.,全局优化算法概述,全局优化方法可分为随机性方法和确定性方法.,第14页,全局优化算法概述,确定性方法,充分利用了问题解析性质,如函数凸性、单调性、稠密性等,产生一个确定性有限或无限点序列,使得该点序列收敛于全局最优解.包含分枝定界算法、区间算法、填充函数法、割平面法、顶点枚举法等,这类算法在理论上有较强可行性,但对较为复杂大型优化问题却难于应用.,全局优化方法可分为随机性方法和确定性方法.,第15页,第二节 凸函数和凸规划,凸函数及其性质,凸规划及其性质,第16页,一、凸函数及其性质,定义 5,设,是非空凸集,，,假如对任意,有,则称,f,是,S,上,凸函数,，或,f,在,S,上是,凸,。,有,则称,f,是,S,上,严格凸函数，,或,f,在,S,上是,严格凸。,假如对于任意,若,f,是,S,上（严格）凸函数，则称,f,是,S,上,（严格）凹函数,或,f,在,S,上是,（严格）凹,第17页,例1 线性函数,在,R,n,上既是凸函数又是凹函数。,例2 函数,证,证,第18页,证:(1),定理 1,(1)若,f,(,x,)是,S,上凸函数，,都是,S,上凸函数,是,S,上凸函数。,是非空凸集。,(2),则,也是,S,上凸函数。,凸函数性质,第19页,定理 1,(1)若,f,(,x,)是,S,上凸函数，,是,S,上凸函数。,是非空凸集。,凸函数性质,都是,S,上凸函数,(2),则,也是,S,上凸函数。,证:(2),第20页,定理 2,设,是非空凸集，,是凸函数，,，则集合,是凸集。,证：,水平集,又因,f,是,S,上凸函数，所以,凸函数性质,第21页,定理 3,设,是非空开凸集，,，,是函数,f,在点,处梯度,（1）,f,是,S,上凸函数充要条件是,（2）,f,是,S,上严格凸函数充要条件是,可微,，,则,凸函数判定,第22页,证,(1)必要性.设,f,是,S,上凸函数，则对,代入得,由泰勒公式得,第23页,证,（1）,（2）,对,和,充分性.设,第24页,定理 4,设,是非空开凸集，,则,f,是,S,上凸函数充要条件是,f,Hesse矩阵,在,S,上是半正定.,注意,：,该逆命题不成立。,f,在,S,上二阶连续可导,在,S,上正定时，,f,是S上严格凸函数.,凸函数判定,第25页,二 次 型,二次型函数,其中,x,R,n,A,是一个,n,阶对称矩阵，,所以当且仅当,A,为半正定矩阵时，,f(x),是凸函数。,A,为正定矩阵时，,f(x),是严格凸函数。,例,第26页,二、凸规划及其性质,约束集,假如(P)约束集,D,是凸集，目标函数,f,是,D,上凸函数，则(P)叫做,非线性凸规划,，或简称为,凸规划,。,非线性规划,第27页,定理 5,对于非线性规划(P)，若,而且,f,是,D,上凸函数，则(P)是凸规划。,皆为,R,n,上凸函数，,皆为线性函数,证：,又因,f,是,D,上凸函数，,(P)是凸规划,第28页,定理 6,凸规划任一局部最优解都是它全局最优解。,证：,又因,f,是凸函数，所以,矛盾,第29页,例：验证以下规划为凸规划,第30页,第三节 一维搜索方法,非准确一维搜索方法,Goldstein法,Armijo法,准确一维搜索方法,0.618法,Newton法,第31页,目标函数为单变量非线性规划问题称为一维搜索问题,数学模型,由定义知，,t,*是 在,a,b,上唯一极小点。,一、基本原理,定义1,假如存在一个 ，使得 在 区间 上严格递减，且在区间 上严格递增，则称,函数 在区间,a,b,上是,单谷，,区间,a,b,称为,单谷区间,。,第32页,使得,，称,a,b,为搜索区间。,不停缩短搜索区间长度，当区间足够小时,得到所求问题近似最优解。,在区间,a,b,上任取两点,t,1,t,2,，设,t,1,t,2,，,然后，,图,第33页,让下一次迭代中区间缩短相同百分比,，而且已经有一个计算过点在缩短后区间内。,二、0.618法（近似黄金分割法）,a,b,t,1,t,2,第34页,设新探索区间为,a,t,2,其上两个探索点为,0.618法（近似黄金分割法）,第35页,由以上分析得迭代公式：,0.618法（近似黄金分割法）,第36页,算法步骤：,第37页,例1：试用黄金分割法求解,解 (1),第38页,(2),(3),(4),得最优解：,第39页,三、斐波那契（Fibonacci）法,定义2,设数列,F,n,满足：,数列,F,k,称为斐波那契（Fibonacci）数列,。,k,0 1 2 3 4 5 6 7 8,F,k,1 1 2 3 5 8 13 21 34,第40页,一、斐波那契（Fibonacci）法,计算,n,次函数值所得最大缩短率为1/,F,n,要把区间缩短为原区间,(,0，有,第54页,定理2,若,x*,是(UP),定理3,则,x*,是(UP)严格局部最优解。,局部最优解，则,一、无约束问题最优性条件,第55页,定理4,则,x*,是(UP)全局最优解。,x*,是(UP)全局最优解。,一、无约束问题最优性条件,第56页,例1,解,目标函数Hesse矩阵为,一、无约束问题最优性条件,第57页,一、无约束问题最优性条件,第58页,二、最速下降法,基本思想：,从当前点,x,k,出发，取函数,f,(,x,)在点,x,k,处下降最快方向为搜索方向,p,k,，即负梯度方向。,设目标函数,f(x),一阶连续可微.,第59页,二、最速下降法,算法步骤：,第1步,选取初始点,x,0,给定终止误差,0,令,k:=,0；,第2步,计算,第4步,进行一维搜索，求,t,k,使得,第3步,用最速下降法求得最优解是目标函数一个驻点。,第60页,例2 用最速下降法求解,解：,经10轮迭代得最优解。,第61页,三、共轭方向法,定义,设,A,是,n,阶是对称矩阵，若,则称,p,和,q,是相互,A,共轭。,对于非零向量组,则称,p,0,p,1,.,p,n-1,是,A,共轭方向组，或称一组,A,共轭方向。,共轭概念是正交概念推广。,第62页,证,线性无关,第63页,共轭方向组中最多含n个向量，且线性无关,反之，n维空间一组基能够结构一组A共轭方向,共轭方向组结构,由定理知：,第64页,二次严格凸函数无约束最优化问题,定理 6,对于问题(QP)，若,组A共轭方向，则由任意初始点,出发，依次沿,则最多经n次迭代可,得(QP)整体最优解。,为任意一,进行准确一维搜索，,由任意初始点出发，依此沿某共轭方向组进行一维搜索求解无优化约束方法叫,共轭方向法。,利用迭代点处负梯度向量为基础产生一组共轭方向，这种方法叫,共轭梯度法。,第65页,共轭梯度法,首先，取定初始点,x,0,，,从,x,0,点沿方向,p,0,进行，准确一维搜索求得,t,0,，则,不然，取,（1）,依此进行下去，,（2）,第66页,共轭梯度法,不然，取,和沿这些方向迭代点，,（4）,（3）,从而有,第67页,共轭梯度法,（5）,（3）能够写成,公式（5）是由Fletcher和Reeves于1964年提出，称为F-R公式，用公式（5）求解无约束最优化问题最优解方法简称为F-R法。,第68页,第1步,选取初始点,x,0,给定终止误差,0,；,第2步,计算,第4步,进行一维搜索，求,t,k,使得,第3步,F-R法步骤,第69页,第5步,计算,第6步,第7步,用F-R公式取,第70页,例2 用F-R法求解,解：,利用F-R公式得：,第71页,若用某种方法求解(QP)问题，经有限轮迭代能够到达最优解，称此方法含有二次终止性。,F-R法含有二次终止性。,第72页,第五节 约束最优化方法,约束最优化问题,最 优 化条件,简 约 梯 度 法,惩 罚 函 数 法,第73页,第74页,一、约束最优化问题最优化条件,定理 1,处可微，,在点,x,*处连续，,在点,x,*,划(P)局部最优解，则存在两组实数,若,x,*是非线性规,称约束规范条件,Kuhn-Tucker条件，简称K-T条件,第75页,特殊地，对于只有不等式约束非线性规划问题,若,x,*是局部最优解，则存在实数,对于只有等式约束非线性规划问题,一、约束最优化问题最优化条件,第76页,现引进Lagrange函数以下：,一、约束最优化问题最优化条件,第77页,定理 2,对于问题(P)，若,在点,x*,处连续可微，若可行点,x,*满足(P)K-T条件，且,是凸函数,是线性函数，则,x,*,是(P)全局最优解。,一、约束最优化问题最优化条件,第78页,二、简约梯度法,假设（1）每个可行点最少有m个大于0分量,（2）A任意m列线性无关,简约梯度法基本思想是Wolfe于1962年提出,第79页,二、简约梯度法,基本思想：,类似于单纯性法，将当前点,x,k,m,个最大正分量定为基变量，其余,m-n,个分量作为非基变量，那么目标函数作为非基变量函数求负梯度方向，并依据这一方向结构从,x,k,到,x,k+1,可行下降方向。,第80页,二、简约梯度法,称,r,N,为,f,在点,x,处对应于基矩阵,B,简约梯度,。,首先，求,f,对非基变量梯度,第81页,二、简约梯度法,其次，在迭代点,x,k,处依据简约梯度结构可行下降方向,第82页,二、简约梯度法,这是因为，,第83页,二、简约梯度法,总而言之，利用简约梯度,（*）,第84页,定理 3 设,f,是可微函数，,，,二、简约梯度法,第85页,二、简约梯度法,最终，考查怎样从点,x,k,D,l,沿上面结构可行下降方向,p,k,进行有效一维搜索。,因而取,t,上界为,为使,第86页,Wolfe法步骤,第87页,Wolfe法步骤,第88页,例 用Wolfe法求解极小化问题,解 上面问题可化为以下问题,第89页,三、处罚函数法,罚函数法,障碍函数法,基本思想,：利用问题中约束函数做出适当带有参数处罚函数，然后在原来目标函数上加上处罚函数，结构出带参数增广目标函数，把问题求解转换为求解一系列无约束非线性规划问题。,第90页,罚函数法,考虑问题：,设法适当地加大不可行点处对应目标函数值，使不可行点不能成为对应无约束极小化问题最优解。,可行域为,D,结构罚函数：,c称为罚参数或罚因子,第91页,实际应用中，选取一个递增且趋于无穷正罚函数参数列,c,k,于是,第92页,罚函数法计算步骤,第93页,例 用罚函数法求解,解 罚函数为,增广目标函数为,第94页,原问题转化为求解一系列无约束最优化问题：,用解析法求解上述问题：,所以，罚函数法也称为,外点法,O,x,1,x,2,1,x,1,第95页,障碍函数法,基本思想：,在可行区域边界上筑起一道“墙”，当迭代点靠近边界时，所结构增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。,仅考虑带不等式约束问题,当点,x,从可行域内部趋于可行域边界时，最少有一个,g,i,(,x,)趋于0。所以以下函数会无限增大,第96页,结构障碍函数：,取一个递减且趋于0正罚函数参数列,d,k,(,k,=1,2,.),第97页,障碍函数法步骤,第98页,例 用障碍函数法求解极小化问题,解 取,增广目标函数为：,用解析法求,得无约束优化问题,最优解为：,所以，罚函数法也称为,内点法,第99页,罚函数法适合用于普通规划问题，障碍函数法仅适合用于带等式约束规划问题。,罚函数法优点是方法结构简单，对初始点选取没有要求，障碍函数法优点也是方法结构简单，但初始点必须是内点。,缺点：收敛速度慢；工作量大；方法本身造成数值困难。,两种方法优缺点比较：,第100页,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
