非线性优化问题课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,.,*,第三专题 非线性优化问题,1,、非线性优化模型的建立,2,、非线性优化模型的寻优,.,第三专题 非线性优化问题1、非线性优化模型的建立.,1,非线性优化模型的建立,确定决策变量,确定目标（决策准则）,确定约束条件,.,非线性优化模型的建立确定决策变量.,2,实例分析,（,1,）投资决策问题（,P88),（,2,）曲线拟合问题,在实验数据处理或统计资料分析中，常常遇到这样的问题：如何利用有关变量的实验数据（资料）去确定这些变量间的函数关系。例如，已知某物体的温度 与时间 之间有如下形式的经验函数关系：,其中 是待定参数。通过测试获得,n,组温度与时间之间的实验数据 ，试确定参数 使理论曲线尽可能地与,n,个测试点拟合。,.,实例分析（1）投资决策问题（P88).,3,非线性规划问题的共同特征,都是求一个目标函数在一组约束条件下,的极值问题。,在目标函数或约束条件中，至少有一个是变量的非线性函数。,.,非线性规划问题的共同特征 都是求一个目标函数在一组约束条件下,4,非线性规划问题,一般形式：,向量形式：,.,非线性规划问题一般形式：.,5,非线性优化问题的寻优,相关概念及理论,一维最优化方法,多维无约束最优化方法,多维有约束最优化方法,.,非线性优化问题的寻优相关概念及理论.,6,非线性规划的相关概念及理论,一阶导数、二阶导数和,n,元函数的,Taylor,公式,.,非线性规划的相关概念及理论一阶导数、二阶导数和n元函数的Ta,7,.,.,8,.,.,9,定义,4,设函数,定义在凸集,上，,若对任意的,及任意的,都有：,则称函数,为凸集,上的凸函数,定义,5,严格凸函数,注：,将上述定义中的不等式反向，可以得到,凹函数的定义,凸函数,.,定义4设函数定义在凸集上，若对任意的及任意的都有：则称函数为,10,例,1,：,设,试证明,在,上是严格凸函数,证明,:,设,且,都有：,因此,在,上是严格凸函数,.,例1：设试证明在上是严格凸函数证明:设且都有：因此在上是严,11,例,2,：,试证线性函数是,证明,:,设,上的凸函数,则,所以,是凸函数,类似可以证明,是凹函数,.,例2：试证线性函数是证明:设上的凸函数则所以是凸函数类似,12,凸函数的几何性质,对一元函数,在几何上,表示连接,的线段,表示在点,处的,函数值,所以一元凸函数表示连接函数图形上任意两点,的线段总是位于曲线弧的上方,.,凸函数的几何性质对一元函数在几何上表示连接的线段表示在点处,13,.,.,14,凸函数的性质,（）,设,（）,设,函数，,是凸集,上的凸函数，,实数,则,也是,上的凸函数,是凸集,上的凸,实数,则,也是,上的凸函数,（）,设,是凸集,上的凸函数，,是实数，,则水平集,是凸集,.,凸函数的性质（）设（）设函数，是凸集上的凸函数，实数则也,15,下面的图形给出了凸函数,的等值线的图形，可以看出水平集是凸集,.,下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集.,16,凸函数的判定,定理,1,设,上，,令,则,:,(1),是定义在凸集,是凸集,上的凸函数的充要条件是对,任意的,一元函数,为,上的凸函数,.,(2),设,若,在,上为严格,凸函数，,则,在,上为严格凸函数,.,凸函数的判定定理1设上，令则:(1)是定义在凸集是凸集上的凸,17,该定理的几何意义是：凸函数上任意两点之,间的部分是一段向下凸的弧,.,该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的,18,一阶条件,定理,2.1,设在凸集,上,可微，,则：,在,上为凸函数的充要条件是对任意的,都有：,定理,2.2,严格凸函数,(,充要条件,),.,一阶条件定理2.1设在凸集上可微，则：在上为凸函数的充要条件,19,二阶条件,定理,3,设在开凸集,内,二阶可微，则,(1),是,内的凸函数的充要条件为，,在,内任一点,处，,的海色矩阵,半正定,其中：,.,二阶条件定理3设在开凸集内二阶可微，则(1)是内的凸函数的充,20,二阶条件,定理,3,设在开凸集,内,(2),若在,内,正定,则,在,内,二阶可微，则,是严格凸函数,注,:,反之不成立,例：,显然是严格凸的，,但在点,处,不是正定的,.,二阶条件定理3设在开凸集内(2)若在内正定,则在内二阶可微，,21,凸规划,定义,6,设,为凸集，,为,上的凸函数，,则称规划问题,为凸规划问题,定理,4,(1),凸规划问题的任一局部极小点,是,整体极小点，全体极小点组成凸集,(2),若,是凸集,上的严格凸函数，,且凸规划问题,整体极小点存在，,则整体极小点是唯一的,.,凸规划定义6设为凸集，为上的凸函数，则称规划问题为凸规划问题,22,非线性规划的最优性条件,最优性条件：是指非线性规划模型的最优解所要满足的必要和充分条件。,无约束最优性条件,约束最优性条件,.,非线性规划的最优性条件 最优性条件：是指非线性规,23,无约束最优性条件,.,无约束最优性条件.,24,一（单）元函数的最优性条件,（）,若,（）,为,的局部极小点，,则,若,则,为,的严格局部极小点；,若,（）,为,的局部极小点，,则：,.,一（单）元函数的最优性条件（）若（）为的局部极小点，则若,25,多元函数的一阶必要条件（,P106-107),定理,1:,若,为,的局部极小点，,且在,内,一阶连续可导，,则,注,:,(1),仅仅是必要条件，而非充分条件,(2),满足,的点称为驻点,驻点分为：极小点，极大点，鞍点,.,多元函数的一阶必要条件（P106-107)定理1:若为的局部,26,多元函数的二阶充分条件,定理,2:,若在,内,二阶连续可导，,且,正定,则,为严格局部,极小点,注,:,如果,负定,则,为严格局部极大点,.,多元函数的二阶充分条件定理2:若在 内 二阶连续可导，,27,二阶必要条件和充要条件,定理,3:,若,为,的局部极小点，,且在,内,二阶连续可导，,则,半正定,定理,4:,设,在,上是凸函数且有一阶连续,偏导数，,则,为,的整体极小点的充要,条件是,.,二阶必要条件和充要条件定理3:若为的局部极小点，且在内二阶连,28,例,1,：,利用极值条件解下列问题：,解：,令,即：,得到驻点：,.,例1：利用极值条件解下列问题：解：令即：得到驻点：.,29,函数,的海色阵：,由此，,在点,处的海色阵依次为：,.,函数的海色阵：由此，在点处的海色阵依次为：.,30,由于矩阵,不定，,则,不是极小点,负定，,则,不是极小点，,实际上它是极大点,正定，,则,是局部极小点,.,由于矩阵不定，则不是极小点负定，则不是极小点，实际上它是极,31,约束最优性条件,(p133-p136),.,约束最优性条件(p133-p136).,32,定义,1:,有效约束：,若,(*),中的一个可行点,使得,某个不等式约束,变成等式，,即,则,称为关于,的有效,(,积极）约束,非有效约束：,若对,则,称为,关于,的非有效,(,无效,）约束,有效集：,定义,2:,锥：,的子集，,如果它关于正的数乘运算,是封闭的,如果锥也是凸集，则称为,凸锥,凸锥,关于加法和正的数乘运算是封闭的,.,定义1:有效约束：若(*)中的一个可行点使得某个不等式约束变,33,一阶必要条件,定理,3.5:,(Kuhn-Tucker,一阶必要条件,)(1951),设,在,（,K-T,条件）,.,一阶必要条件定理3.5:(Kuhn-Tucker一阶必要条件,34,一阶必要条件,定理,1,:,(Kuhn-Tucker,一阶必要条件,),（互补松弛条件）,.,一阶必要条件定理1:(Kuhn-Tucker一阶必要条件),35,.,.,36,例,2,：,验证 是否满足,Kuhn-Tucker,条件：,试验证最优点,为,KT,点,.,例2：验证 是否满足Kuhn-Tucker条件：试验证最优,37,解：,令,所以,即：,所以：,是,KT,点,.,解：令所以即：所以：是KT点.,38,Lagrange,函数及,K-T,条件,.,Lagrange函数及K-T条件.,39,在一定凸性下的最优性的充分条件,.,在一定凸性下的最优性的充分条件.,40,一维最优化方法（线性搜索方法）,已知,并且求出了,处的可行下降方向,从,出发，,沿方向,求目标函数的最优解，,或者选取,使得：,问题描述,即,.,一维最优化方法（线性搜索方法）已知并且求出了处的可行下降方向,41,设其最优解为,（叫精确步长因子），,所以线性搜索是求解一元函数,的最优化问,题（也叫一维最优化问题）。,我们来求解：,于是得到一个新点：,.,设其最优解为（叫精确步长因子），所以线性搜索是求解一元函数的,42,一般地，线性搜索算法分成两个阶段：,第一阶段确定包含理想的步长因子,（或问题最优解）的搜索区间；,第二阶段采用某种分割技术或插值方法,缩小这个区间。,搜索区间：,.,一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长,43,搜索区间求取方法,进退法：,一种简单的确定初始搜索区间方法,.,基本思想：,是从一点出发，按一定步长，试图确定出函数值呈现,“,高,-,低,-,高,”,的三点，即,这里 。,具体地说，就是给出初始点,，,初始步长,，若 ，则下一步从新点,出发，加大步长，再向前搜索，直到,目标函数上升为止。,.,搜索区间求取方法 进退法：一种简单的确定初始搜索区间方法.,44,若 ，则下一步仍以 为出发点，沿反方向同样搜索，直到目标函数上升就停止。这样便得到一个搜索区间。这种方法叫进退法。,计算步骤：见,P96,计算框图,:,见,P97,.,若,45,.,.,46,黄金分割法（,0.618,法）,基本思想：,它通过对试探点的函数值进行比较，使得包含极小点的区间不断缩短，当区间长度小到精度范围之内时，可以粗略地认为区间上各点的函数值均接近于极小值。,.,黄金分割法（0.618法）基本思想：.,47,设,在,上为下单峰函数，,即有唯一,的极小点,在,左边,严格下降，,在,右边,严格上升。,在,内任取,若,则,若,则,单峰函数：,黄金分割法,.,设在上为下单峰函数，即有唯一的极小点在左边严格下降，在右边严,48,黄金分割法,若第一次选取的试点为,则下一步保留,的区间为,或,两者的机会是均等的,因此我们选取试点时希望,设,则,另外，我们希望如果缩小的区间包含原来的,试点，则该试点在下一步被利用若保留的区,.,黄金分割法若第一次选取的试点为则下一步保留的区间为或两者的机,49,我们希望原来的,间为,前一次的试点,在这个区间内,在缩小的区间内成为,新的,我们根据这条件 来计算,计算,的公式为：,因此我们希望：,即：,.,我们希望原来的间为前一次的试点在这个区间内在缩小的区间内成,50,化简得：,若保留区间为,我们得到的结果是,一致的,该方法称为黄金分割法，实际计算取：,所以黄金分割法又称为,0.618,法,黄金分割法每次缩小区间的比例是一致的，,每次将区间长度缩小到原来的,0.618,倍,.,化简得：若保留区间为我们得到的结果是一致的该方法称为黄金分,51,黄金分割法的算法步骤,Step1,给定,以及,令,Step2,Step3,转,Step,.,令,转,Step,.,若,则,停；,否则,转,Step,.,Step4,若,则,转,Step3.,.,黄金分割法的算法步骤Step1给定以及令Step2Step,52,黄金分割法的算法步骤,Step5,若,则,转,Step3.,若,则,转,Step3.,.,黄金分割法的算法步骤Step5若则转Step3.若则转Ste,53,例,1,（黄金分割法）,用黄金分割法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的,0.08,倍,解：,函数,在区间,上为下单峰函数，,.,例1（黄金分割法）用黄金分割法求函数在区间上的极小点。要求最,54,第一次迭代：,缩短后区间为,第二次迭代：,缩短后区间为,.,第一次迭代：缩短后区间为第二次迭代：缩短后区间为.,55,迭代,次数,0.528,1.472,1.751,2.695,否,-0.056,0.528,2.059,1.751,否,0.528,0.888,1.751,1.901,否,0.305,0.528,1.788,1.751,否,0.528,0.665,1.751,1.777,否,0.443,0.528,1.753,1.751,否,0.528,0.580,1.751,1.757,是,.,迭代0.5281.4721.7512.695否-0.05,56,Fibonacci,法,为了尽快得到结果，希望区间缩小的尽量小。,如果在区间只有一个试点，我们无法将区间缩小。,如果知道两个试点,根据,的大,小关系，,可以得到缩小的区间,或者,它与,0.618,法的主要区别之一在于：搜索区间长,度的缩短率不是采用,0.618,，而是采用,Fibonacci,数。,.,Fibonacci法为了尽快得到结果，希望区间缩小的尽量小。,57,下面我们考虑任给一个,另外一种思维方式为，,的单峰区间,如果给定试点的个数,如何使最后确定,最优值的区间尽量的小。,按什么方式取点，,求,次函数值之后，,可最多将多长的原始区间,长度缩小为,设,为试点个数为,最终区间,长度为,时、,原始区间,的最大可能长度。,的包含,.,下面我们考虑任给一个另外一种思维方式为，的单峰区间如果给定试,58,设最初两个试点为,和,若极小点在,内，,至多还有,个试点，,则,若极小点在,内，,包括,在内可以有,个试点，,则,因此，,如果我们采取合适的技巧，可以使得：,另外，,显然，,.,设最初两个试点为和若极小点在内，至多还有个试点，则若极小点在,59,从而,满足差分方程：,此为,Fibonacci,数列，一般写为：,.,从而满足差分方程：此为Fibonacci数列，一般写为：.,60,若原始区间为,要求最终区间长度,则,由此可确定,区间缩短之后与,之前的比依次为：,确定之后，最初两个试点分别为：,关于,对称,由于,.,若原始区间为要求最终区间长度则由此可确定区间缩短之后与之前的,61,上述过程完成了依次迭代，新区间仍记为,若已经进行了,次迭代，,第,次迭代时，,还有,个试点（包括已经计算过的函数值的一个）,注意,：,（）若在一定的误差范围内，,则认为,在,内。,（）最后的两个试点的选取方式：,.,上述过程完成了依次迭代，新区间仍记为若已经进行了次迭代，第次,62,例,3.1,（,Fibonacci,法）,用,Fibonacci,法求函数,在区间,上的极小点。,要求最终区间长度不大于,原始区间长度的,0.08,倍,解：,函数,在区间,上为下单峰函数，,由,可知,应取,Fibonacci,算法与,0.618,法几乎完全相同 。,.,例3.1（Fibonacci法）用Fibonacci法求函数,63,第一次迭代：,缩短后区间为,.,第一次迭代：缩短后区间为.,64,第二次迭代,：,缩短后区间为,.,第二次迭代：缩短后区间为.,65,第三次迭代：,缩短后区间为,第四次迭代：,缩短后区间为,.,第三次迭代：缩短后区间为第四次迭代：缩短后区间为.,66,第五次迭代：,取最优解,.,第五次迭代：取最优解.,67,Fibonacci,方法评价,Fibonacci,法的优点,（）如果缩小的区间包含原来的试点，则该,试点在下一步被利用；,（）效率最高，有限个试点的情况下，可将,最优点所在的区间缩小到最小,.,Fibonacci方法评价Fibonacci法的优点（）如,68,Fibonacci,法的缺点,（）搜索前先要计算搜索的步数；,（）每次搜索试点计算的公式不一致,1,、黄金分割法（,0.618,法）与,Fibonacci,法,的区别与联系是什么？,2,、请读者自己写出算法和程序,.,Fibonacci法的缺点（）搜索前先要计算搜索的步数；（,69,二分法,若,的导数存在且容易计算，,则线性搜索,的速度可以得到提高,下面的二分法每次将,区间缩小至原来的二分之一,设,为下单峰函数，,若,在,内,具有连续的一阶导数，,且,.,二分法若的导数存在且容易计算，则线性搜索的速度可以得到提高,70,取,若,则,为极小点；,若,则以,代替,若,则以,代替,二分法每次迭代都将区间缩短一半，故二分法的收敛速度也是线性的，收敛比为,1/2,。,。,计算步骤：见,P105,计算框图,:,见,P106,.,取若则为极小点；若则以代替若则以代替 二分法每次迭代,71,多维无约束最优化方法,最速下降法,(,阻尼,),牛顿法,共轭梯度法,.,多维无约束最优化方法最速下降法.,72,最速下降法,.,最速下降法.,73,问题提出,问题：,在点,处，,沿什么方向,下降最快,?,分析：,考查：,显然当,时，,取极小值,因此：,结论：,负梯度方向使,下降最快，,亦即最速,下降方向,.,问题提出问题：在点处，沿什么方向下降最快?分析：考查：显然当,74,最速下降法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,计算下降方向,Step4:,计算步长因子,Step5:,令,转步,.,.,最速下降法算法Step1:给出Step2:计算如果停Ste,75,问题：,设,是正定二次函数,由精确的线搜索确定的,特别当：,.,问题：设是正定二次函数,由精确的线搜索确定的特别当：.,76,例,1,：,用最速下降法求解：,解：,.,例1：用最速下降法求解：解：.,77,分析：,(1),因此：,最速下降法是整体收敛的，,且是线性收敛的,(2),两个相邻的搜索方向是正交的,.,分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的(,78,.,.,79,收敛性分析,定理,1:,设,在,上存在且一致连续，,则最速下降法产生的序列,满足或者对某个,有,或者,证明：,对于最速下降法，,由以上定理立得,.,收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序,80,收敛性分析,定理,2:,设,二次连续可微，,且,其中,是个正常数，,对任何给定的初始点,最速下降算法或有限终止，,或者,或者,证明：,用以上的结论：,.,收敛性分析定理2:设二次连续可微，且其中是个正常数，对任何给,81,最速下降法优点,(1),程序设计简单，计算量小，存储量小，,对初始点没有特别要求,(2),有着很好的整体收敛性，即使对一般的,目标函数，它也整体收敛,.,最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始,82,最速下降法缺点,最速下降法是线性收敛的，并且有时是,很慢的线性收敛,原因：,仅反映,在,处,的局部性质,相继两次迭代中搜索,方向是正交的,.,最速下降法缺点最速下降法是线性收敛的，并且有时是很慢的线性收,83,小结,最速下降法是基本算法之一，而非有效,的实用算法,最速下降法的本质是用线性函数来近似,目标函数，,要想得到快速算法，需要考,虑对目标函数的高阶逼近,.,小结最速下降法是基本算法之一，而非有效的实用算法最速下降法,84,牛顿法,.,牛顿法.,85,基本思想,利用目标函数,在点,处的二阶,Taylor,展开式去近似目标函数，,用二次函数的极小点,去逼近目标函数的极小点,.,基本思想利用目标函数在点处的二阶Taylor展开式去近似目标,86,算法构造,问题：,设,二阶连续可微，,海色阵,正定,如何从,因为,正定，,则,有唯一极小点，,用这个,极小点作为,.,算法构造问题：设二阶连续可微，海色阵正定如何从因为正定，则,87,所以要求：,即：,因此：,这就是,牛顿法迭代公式,注：,这里,.,所以要求：即：因此：这就是牛顿法迭代公式注：这里.,88,牛顿法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,否则计算,Step4:,令,转步,.,并且求解方程,得出,.,牛顿法算法Step1:给出Step2:计算如果停Step3,89,例,1,：,用牛顿法求解：,解：,.,例1：用牛顿法求解：解：.,90,牛顿法收敛定理,定理,1,:,设,二次连续可微，,是,的局,部极小点，,正定,假定,的海色阵,满足,Lipschitz,条件，即存在,使得对于所有,有：,其中,是海色阵,的,元素,则当,充分靠近,时，,对于一切,牛顿迭代有意义，,迭代序列,收敛到,并且具有二阶收敛速度,.,牛顿法收敛定理定理1:设二次连续可微，是的局部极小点，正定,91,牛顿法优点,(1),(2),对正定二次函数，迭代一次就可以得到,极小点,如果,正定且初始点选取合适，,算法,二阶收敛,.,牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小,92,牛顿法缺点,(1),(2),对多数问题算法不是整体收敛的,每次都需要计算,计算量大,(3),每次都需要解,方程组有时奇异或病态的，,无法确定,或,不是下降方向,(4),收敛到鞍点或极大点的可能性并不小,.,牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需,93,阻尼牛顿法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,否则计算,Step4:,沿,并且求解方程,得出,进行线搜索，,得出,Step5:,令,转,Step2.,.,阻尼牛顿法算法Step1:给出Step2:计算如果停Ste,94,阻尼牛顿法收敛定理,定理,2:,设,二阶连续可微，,又设对任意的,存在常数,使得,在,上满足：,则在精确线搜索条件下，,阻尼牛顿法产生的点列,满足：,(1),当,是有限点列时，,其最后一个点为,的唯一极小点,(2),当,是无限点列时，,收敛到,的唯一极小点,.,阻尼牛顿法收敛定理定理2:设二阶连续可微，又设对任意的存在常,95,阻尼牛顿法收敛定理,定理,3,:,设,二阶连续可微，,又设对任意的,存在常数,使得,在,上满足：,则在,Wolfe,不精确线搜索条件下，,阻尼牛顿法,产生的点列,满足：,且,收敛到,的唯一极小点,.,阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的存在常,96,例,2,：,用阻尼牛顿法求解：,解：,显然,不是正定的，,但：,于是，,沿方向,进行线搜索，,得其极小点,从而迭代不能继续下去,.,例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向,97,带保护的牛顿法算法,给出,Step1:,若,为奇异的，转,Step8,，否则，,Step2:,令,Step3:,若,为奇异的，转,Step8,，否则，,则转,Step8,，否则，,Step4:,若,则转,Step9,，否则，,Step5:,沿方向,进行线搜索，,求出,并令,.,带保护的牛顿法算法给出Step1:若为奇异的，转Step8，,98,Step6:,若,停；,Step7:,令,转,Step1,；,Step8:,令,转,Step5,；,Step9:,令,转,Step5.,.,Step6:若停；Step7:令转Step1；Step8:令,99,例,3,：,用带保护的牛顿法求解：,解：,显然,不是正定的，,但：,于是，,因为，,故令，,沿,进行线搜索得：,.,例3：用带保护的牛顿法求解：解：显然不是正定的，但：于是，因,100,第二次迭代：,而：,使,故令,沿,进行线搜索，,得出,于是,:,此时,:,.,第二次迭代：而：使故令沿进行线搜索，得出于是:此时:.,101,共轭梯度法,.,共轭梯度法.,102,问题,1:,如何建立有效的算法？,从二次模型到一般模型,问题,2:,什么样的算法有效呢？,二次终止性,(,经过有限次迭代必达到极小点的性质）,.,问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么,103,算法特点,（）建立在二次模型上，具有二次终止性,（）有效的算法，克服了最速下降法的慢,收敛性，又避免了牛顿法的计算量大和局部收,性的缺点,（）算法简单，易于编程，需存储空间小等,优点，是求解大规模问题的主要方法,.,算法特点（）建立在二次模型上，具有二次终止性（）有效的,104,共轭方向及其性质,定义,1:,设,是,中任一组,非零向量，,如果：,则称,是关于,共轭的,注：,若,则是正交的，因此共轭是,正交的推广,.,共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关,105,定理,1:,设,为,阶正定阵，,非零向量组,关于,共轭，,则必线性无关,推论,1,:,设,为,阶正定阵，,非零向量组,关于,共轭，,则向量构成,的一组基,推论,2:,设,为,阶正定阵，,非零向量组,关于,共轭，,若向量,与,关于,共轭，,则,.,定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关推论,106,求 的极小点的方法,共轭方向法算法,Step1:,给出,计算,和初始下降方向,Step2:,如果,停止迭代,Step3:,计算,使得,Step4:,采用某种共轭方向法计算,使得：,Step5:,令,转,Step2.,.,求 的极小点的方法共轭方向法算,107,共轭方向法基本定理,定义,2:,设,维向量组,线性无关，,向量集合,为,与,生成的,维超平面,.,共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生,108,引理,1:,设,是连续可微的严格凸函数，,维向量组,线性无关，,则：,是,在,上,唯一极小点的充要条件是：,.,引理1:设是连续可微的严格凸函数，维向量组线性无关，则：是在,109,定理,2:,设,为,阶正定阵，,向量组,关于,共轭，,对正定二次函数,由任意,开始，,依次进行,次精确线搜索：,则：,（）,（）,是,在,上的极小点,推论,:,当,时，,为正定二次函数在,上的极小点,.,定理2:设为阶正定阵，向量组关于共轭，对正定二次函数由任意开,110,共轭梯度法,记：,左乘,并使,得：,（,Hestenes-Stiefel,公式）,取：,是一种特殊的共轭方向法,.,共轭梯度法记：左乘并使得：（Hestenes-Stiefel,111,共轭梯度法基本性质,定理,3:,对于正定二次函数，,采用精确线搜索,的共轭梯度法在,步后终止，,且对,成立下列关系式：,（共轭性）,（正交性）,（下降条件）,.,共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的,112,系数的其他形式,（）,FR,公式,（,1964,）,（,2,）,PRP,公式,（,1969,）,.,系数的其他形式（）FR公式（1964）（2）PRP公式（1,113,FR,共轭梯度法算法,Step1:,给出,Step2:,如果,停,Step5:,转,Step2.,计算,Step4:,Step3:,由精确线搜索求,计算,.,FR共轭梯度法算法Step1:给出Step2:如果停Ste,114,例,4,：,用,FR,共轭梯度法求解：,解：,化成,形式,(1),.,例4：用FR共轭梯度法求解：解：化成形式(1).,115,(2),.,(2).,116,.,.,117,例,5,：,用,FR,共轭梯度法求解：,解：,化成,形式,(1),.,例5：用FR共轭梯度法求解：解：化成形式(1).,118,(2),.,(2).,119,注意：,FR,方法中初始搜索方向必须取最速下降方向，才满足二次终止性。,.,注意：FR方法中初始搜索方向必须取最速下降方向，才满足二次终,120,FR,共轭梯度法收敛定理,定理,4,:,假定,在有界水平集,上连续可微，,且有下界，,那么采用精确线搜索下的,FR,共轭梯度法产生的点列,至少有一个聚点,是驻点，即：,(1),当,是有穷点列时，,其最后一个点是,的驻点,(2),当,是无穷点列时，,它必有聚点，,且任一,聚点都是,的驻点,.,FR共轭梯度法收敛定理定理4:假定在有界水平集上连续可微，且,121,再开始,FR,共轭梯度法算法,Step1:,给出,Step2:,计算,如果,停，,Step4:,否则,Step3:,由精确线搜索求,并令：,计算,若,令,转,Step2;,如果,停,.,.,再开始FR共轭梯度法算法Step1:给出Step2:计算如果,122,Step5:,若,令,转,step2.,Step6:,计算,Step7:,如果,令,转,step2,否则,转,step3.,.,Step5:若令转step2.Step6:计算Step7:如,123,作业,用,FR,共轭梯度法求解：,.,作业用FR共轭梯度法求解：.,124,多维约束最优化方法,惩罚函数法,SUMT:,序列无约束极小化方法,(Sequential Unconstrained Minimization Technique),乘子法,外点法（二次罚函数方法）,内点法（内点障碍罚函数法）,.,多维约束最优化方法外点法（二次罚函数方法） 内点法（内点障碍,125,罚函数法,.,罚函数法.,126,基本思想,设法将约束问题求解转化为无约束问题求解,具体说：,根据约束的特点，构造某种惩罚函数，,然后把它加到目标函数中去，将约束问题的,求解化为一系列无约束问题的求解,惩罚策略,：,企图违反约束的迭代点给予很大的,目标函数值,迫使一系列无约束问题的极小点或,者无限地靠近可行域，或者一直保持在可行域,内移动，直到收敛到极小点,.,基本思想设法将约束问题求解转化为无约束问题求解具体说：根据,127,外罚函数法（外点法）,引例：,求解等式约束问题,:,解,:,图解法求出最优解,构造：,但是,性态极坏，,无法用有效的无约束,优化算法求解,.,外罚函数法（外点法）引例：求解等式约束问题:解:图解法求出最,128,设想构造：,其中,是很大的正数,求解此无约束问题得：,当,时，,有：,.,设想构造：其中是很大的正数求解此无约束问题得：当时，有：.,129,等式约束问题,构造：,其中,为参数，称为罚因子,分析：,当,不是可行解时，,越大，,惩罚越重,因此当,充分大时，,应充分小,即,的极小点应充分逼近可行域，,进而,逼近,(1),的最优解,.,等式约束问题构造：其中为参数，称为罚因子分析：当不是可行解,130,不等式约束问题,构造：,分析：,当,不是可行解时，,越大，,惩罚越重,因此当,充分大时，,应充分小,即,的极小点应充分逼近可行域，,进而,逼近,(2),的最优解,.,不等式约束问题构造：分析：当不是可行解时，越大，惩罚越重因,131,一般约束问题,构造：,其中：,.,一般约束问题构造：其中：.,132,例,1,：,用外罚函数法求解：,解：,即：,因此：,.,例1：用外罚函数法求解：解：即：因此：.,133,令：,得：,最优值：,当,时：,.,令：得：最优值：当时：.,134,注：,(1),往往不满足约束条件，,都是,从可行域外部趋向于,的,因此叫外罚函数法,(2),通过求解一系列无约束最优化问题来求,解约束最优化问题的方法，,又称为序列无约束,极小化技术,SUMT.,外罚函数法,又称,SUMT,外点法,.,注：(1)往往不满足约束条件，都是从可行域外部趋向于的因此,135,外罚函数法算法步骤,Step1:,给出,(,可是不可行点,),，,罚因子,放大系数,Step2:,以,为初始点求无约束问题：,得,Step3:,若,则,停；,否则转,step4,Step4:,令,转,step2.,.,外罚函数法算法步骤Step1:给出(可是不可行点)，罚因子放,136,例,2,：,用,SUMT,外点法求解：,取,求解,迭代过程见下表：,.,例2：用SUMT外点法求解：取求解迭代过程见下表：.,137,0.1,(1.4539,0.7608),0.0935,0.1831,1,(1.1687,0.7407),0.5753,0.3908,10,(0.9906,0.8425),0.5203,0.1926,100,(0.9507,0.8875),1.9405,0.0267,.,0.1(1.4539,0.7608)0.09350.183,138,收敛性分析,引理,1,：,对于由,SUMT,外点法产生的点列,则有：,设,.,收敛性分析引理1：对于由SUMT外点法产生的点列则有：设.,139,收敛性分析,定理,1,：,设约束问题,(3),和无约束问题,(4),的整体,最优解为,和,对正数序列,且,则由,SUMT,外点法产生的点列,的,任何聚点,必是,(3),的整体最优解,证：,不妨设,因为,和,分别为,(3),和,(4),的整体最优解，,且,所以有：,.,收敛性分析定理1：设约束问题(3)和无约束问题(4)的整体最,140,为单调有界序列，,设其极限为,亦为单调有界序列，,设其极限为,且,连续；,即,为可行解,为最优解；,连续；,即,为,(3),的整体最优解,.,为单调有界序列，设其极限为亦为单调有界序列，设其极限为且连续,141,外罚函数法评价,(1),如果有了求解无约束问题的好算法，利用,外罚函数法求解约束问题很方便,(2),每个近似解,往往不是可行解，这是某,些实际问题所无法接受的,内罚函数法可以解决,(3),由收敛性定理,取越大越好，,而,越大将,造成增广目标函数,的,Hesse,阵条件数越,大，趋于病态，给无约束问题求解增加很大困,难，甚至无法求解乘子法可解决这个问题,.,外罚函数法评价(1)如果有了求解无约束问题的好算法，利用外罚,142,内罚函数法,惩罚策略：,在可行域的边界上筑起一道很高的,“,围墙,”,，当迭代点靠近边界时，目标函数值,陡然增大，以示惩罚，阻止迭代点穿越边界，,这样就可以把最优解,“,挡,”,在可行域内了,注：,惩罚策略只适合于不等式约束问题，,并且要求可行域的内点集非空,.,内罚函数法惩罚策略：在可行域的边界上筑起一道很高的“围墙”，,143,不等式约束问题,构造：,其中：,或,分析：,为可行域的内点时，,为有限正数，,几乎不受惩罚；,接近边界时，,趋于无穷大，,施以很重的惩罚；,迫使极小点落在可行域内，,最终逼近极小点,.,不等式约束问题构造：其中：或分析：为可行域的内点时，为有限正,144,例,3,：,用内罚函数法求解：,解：,令：,.,例3：用内罚函数法求解：解：令：.,145,所以,当,时，,注：,一般,最优解很难用解析法求出，,需采用序列无约束最优化方法,.,所以当时，注：一般最优解很难用解析法求出，需采用序列无约束最,146,内罚函数法算法,Step1:,给出,(,要求是可行点,),，,罚因子,缩小系数,Step2:,以,为初始点求无约束问题：,得,Step3:,若,则,停；,否则转,step4,Step4:,令,转,step2.,.,内罚函数法算法Step1:给出(要求是可行点)，罚因子缩小系,147,例,4,：,用,SUMT,内点法求解：,取,迭代结果见下表：,.,例4：用SUMT内点法求解：取迭代结果见下表：.,148,10,(2.0402,3.1623),12.5290,12.7755,1,(1.1473,0.3162),3.6165,0.9951,0.1,(1.0488,0.1000),2.9667,0.3049,0.01,(1.0157,0.0316),2.7616,0.0953,0.001,(1.0016,0.0316),2.7046,0.0941,.,10(2.0402,3.1623)12.529012.77,149,收敛性分析,引理,2,：,对于由,SUMT,内点法产生的点列,总有：,定理,2,：,设可行域,的内点集,非空，,在,上存在极小点,对严格单减正数列,且,则由,SUMT,内点法产生的点列,的任何聚点,是约束问题,(2),的最优解,.,收敛性分析引理2：对于由SUMT内点法产生的点列总有：定理2,150,证：,由于,由引理,2,知,单调减少且下有界，,于是它有极限，记作,即：,若能证明：,则可得：,再由,的连续性，可得：,即,是,(2),的最优解,.,证：由于由引理2知单调减少且下有界，于是它有极限，记作即：若,151,再证：,由,的连续性知，,对于任意小的正数,存在,取满足,的,使得：,由,知，,对于同一个,存在,当,时,又因为,.,再证：由的连续性知，对于任意小的正数存在取满足的使得：由知，,152,乘子法,引例：,求解等式约束问题,:,解,:,最优解,分析：,对于任何,关于,的极小点是不存在的,正因为如此，才引进外罚函数法的,.,乘子法引例：求解等式约束问题:解:最优解分析：对于任何关于的,153,问题：,能否找到某个,使,恰好是,的无约束极小呢？回答是否定的,设想：,能否在不改变最优解的前提下，,以某个,在最优解,处梯度为零的函数来取代,呢？,启发：,(,增广,Lagrange,函数,),通过求解增广,Lagrange,函数的序列无约束问题,来获得原约束问题的解,.,问题：能否找到某个使恰好是的无约束极小呢？回答是否定的设想,154,等式约束问题的乘子法,其中,和,二阶连续可微,设,为,Lagrange,乘子向量，,则对应,Lagrange,函数为：,设,是,的极小点，,是相应的乘子向量 ,(1),可等价为：,.,等式约束问题的乘子法其中和二阶连续可微设为Lagrange,155,启发：,采用外罚函数法,构造：,我们将证明：,适当大时，,是,极小点,但,是未知的，,在求,的同时，,采用迭代法求出,这是乘子法的基本思想,.,启发：采用外罚函数法构造：我们将证明：适当大时，是极小点,156,定理：,设,与,满足,为问题,(1),的严格局部,极小点的二阶充分条件，,则存在,使对所有,为,的严格局部极小点；,反之，,若,且,对某个,是无约束问题,(5),的局部极小点，,则,是约束问题,(1),的局部,极小点,.,.,定理：设与满足为问题(1)的严格局部极小点的二阶充分条件，,157,算法构造,采用迭代法求点列,使,设已有,和,则由一阶最优性条件有：,要求,和,且,采用：,或：,.,算法构造采用迭代法求点列使设已有和则由一阶最优性条件有：要求,158,例,5,：,用乘子法求解：,解：,增广,Lagrange,函数为：,令：,得：,.,例5：用乘子法求解：解：增广Lagrange函数为：令：得：,159,所以：,乘子迭代公式为：,即：,取：,所以：,设,对上式取极限有：,得：,得：,也可不取特定值，直接对上式求极限,.,所以：乘子迭代公式为：即：取：所以：设对上式取极限有：得：得,160,等式约束的乘子法,(PH,算法,),Step1:,给出,Step2:,以,为初始点求无约束问题：,得,Step3:,若,则,停；,否则转,step4,Step4:,当,及放大系数,转,step5;,否则,转,step5;,Step5:,令,转,step2.,.,等式约束的乘子法(PH算法)Step1:给出Step2:以为,161,作业,(1),用外罚函数法求解：,(2),用内罚函数法求解：,.,作业(1)用外罚函数法求解：(2)用内罚函数法求解：.,162,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,163,