最优化第一章(2)

,*,开始,最优化方法,（最优化课件研制组）,退出,主讲：张 京,最优化方法,1.7,极小点的判定条件,函数,在局部极小点满足什么条件？反之，满足,什么条件的点是,的局部极小点？,定理,1.15,设,具有一阶连续偏导数，,是,的内点。若,是,的局部极小点，则,（,1.40,）,注意，条件式（,1.40,）不是充分的，仅仅是必要的。,例如，,在点,处的梯度是,但是点,是这个双曲抛物面的鞍点，而,不是极小点。,根据定理,1.15,与推论,1.13,，,容易得到凸规划问题全局极小,点的一个一阶充分且必要条件。,推论,1.16,设,是可微凸函数，,是非空开凸集，,。则,是（,1.36,）的全局极小点的,充要条件是,.,定义,1.17,设,可微，,若,，则,称为,的驻点。,驻点包括极大值点、极小值点和鞍点。,定理,1.17,设,具有二阶连续偏导数，,，且,。若,正定，则,是,的严格局部极小点。,一般来说，这个定理仅具有理论意义。因为对于复杂,的目标函数，,Hesse,矩阵不易求得，其正定性也很难判定。,定理,1.18,设,具有二阶连续偏导数，,且,。,若存在,的,邻域,，使得,对于,，,都半正定，则,必是,的局部极小点。,利用上节和本节的定理不难说明下面的两个论断。,i,）对于正定二次函数,，,是它的唯一极小点。,ii,）若多元函数在极小点处的,Hesse,矩阵是正定的,则,在这个极小点附近其等值面近似地呈现为同心椭球面族。,推证如下：,i,）首先求出二次函数的驻点。令,因为,是正定矩阵，所以解出唯一驻点为,（,1.41,）,因此根据推论,1.13,可以断定，,是唯一的极小点。,ii,）设,是多元函数的极小点，,并设,是充分,的一个等值面，,靠近极小点,即,充分小。,把,在点,处按,Taylor,公式展开，得到,上式右端第二项因为,是极小点而消失，再略去,第四项，那么二次曲面,（,1.42,）,就是等值面,的近似曲面。,按假设，,是正定的，因此，,为中心的椭球面,（,1.42,）是以,方程。这正是我们所要说明的。,1.,下降迭代算法,1.8,算法及有关概念,在集合,上的迭代算法是指：开始，选定一个初始点,，置,。然后按某种规则,，把第,次迭代点,映射为新的一点,，记为,，并置,这称为完成了第,次迭代。,这个过程无限地进行下去，,。因此，规则,称为算法。,就会产生一个点列,若点列,收敛于,，则称算法,在,上是收敛的；,否则，称算法,在,上是发散的。特别地,，当,问题（,1.6,）的容许集时，若除满足计算终止准则的迭代点,是最优化,外，对于每个,，都有,，则称,为下降迭代,许多最优化方法都采用将多维问题转化为一维问题的,处理方式。下面以,无约束问题,为例，说明采用这种方式时,的下降算法的基本迭代格式。,设第,次迭代点,已求得。若它不满足终止准则，,。对于可微目标函数，即,那么在该点必存在下降方向,是满足,的,。按某种规则选取一个,，例如,，再沿这个方向适当地前进一步，即在直线,上确定一个新点,，使得,这就完成了第,迭代。上式中的,称为搜索方向，,称为步长因子。,不过，计算机只能进行有限次迭代。因此，一般说来，,数值计算不能求到精确解，而只能得到近似解。当迭代点,满足事先给定的精度要求时，就终止计算，并把这个迭代,点当作问题的最优解。,在上数述迭代过程中，有两个规则需要确定：一个是,的选取规则；一个是步长因子,的选取规则。,下降方向,不同的规则对应着不同的最优化方法。,综上所述，无约束问题下降算法的基本迭代格式如下：,选定初始点,，置,。,按某种规则确定下降方向,。,按某种规则确定,，使得,置,。,判定,是否满足终止准则。若满足，,则打印,和,；否则，置,转,。,算法流程图见,P34,图,1-18,。,2.,直线搜索及其性质,在搜索方向,已经确定的前提下，选取步长因子的,方法有多种。例如，取步长因子为某个常数。但在实际计算中，最常用的方法是直线搜索（又称一维搜索），,即选取,，使得,（,1.43,）,按这种方法确定的步长因子称为最优步长因子。这种选取方法是很自然的。既然下降方向已经确定，就应该沿这个方向找到使目标函数取极小值的点。,2.,直线搜索及其性质,在搜索方向,已经确定的前提下，选取步长因子的,方法有多种。例如，取步长因子为某个常数。但在实际计算中，最常用的方法是直线搜索（又称一维搜索），,即选取,，使得,（,1.43,）,按这种方法确定的步长因子称为最优步长因子。这种选取方法是很自然的。既然下降方向已经确定，就应该沿这个方向找到使目标函数取极小值的点。,同时这又是容易办到的，因为,是以,为变量的一元函数。,求一元函数极小点的迭代法称为直线搜索或一维搜索。许多最优化方法都采用将多维问题转化为一维问题的处理技术。因此可以说，一维搜索是最优化方法的一个重要支柱。这种方法的优点是，它使目标函数值在搜索方向上下降得最多；缺点是，计算量较大。在第,3,章的,3.1,节中将全面介绍直线搜索。,为简便起见，今后用记号,（,1.44,）,表示从点,出发沿,方向对目标函数,作直线,。在目标函数,确定的条件下，,搜索得到极小点,（,1.44,）等价于,（,1.45,）,直线搜索的一个重要性质。,定理,1.19,设目标函数,具有一阶连续偏导数。若,，则,证 使用反证法。假设,，则,或,（,1.47,）,（,1.48,）,（,1.47,）表明,是点,处的下降方向，（,1.48,）表明,是点,处的下降方向，,这都与,相矛盾。,。,故必有,（,1.46,）的几何意义是明显的。,若,是从点,出发沿,方向对目标函数,搜索得到的极小点，则（,1.46,）指出，梯度,搜索方向向量,正交。,作直线,必与,又因为,与目标函数过点,的等值面（等直线）,正交，所以搜索方向向量,与这个等值面（等直线）在点,处相切。,3.,计算终止准则,设某个算法产生的点列,收敛于（,1.6,）的最优解,。,现在的问题是：在计算机上计算时，计算到哪一个,迭代点才有把握地说它就是所求问题的（近似）最解？,显然，当,小于预先给定的误差限时就可以,就是所求的最优解。,认为,但事实上,是未知的，因而,无法计算,。不过，由极限理论知道，当,与,都很小时，,也必然很小。于是，在,数值计算中，可以用,（,1.51,）,作为计算终止的一个判定条件，其中,是预先给定的计算,终止的界限，今后称为终止限。,但是，用（,1.51,）作为终止准则是不可靠的，因为,很小并不能保证,很小。,下面图,1,中画出了一条一元目标函数的曲线及其有关的点。,从图中可以看到，相邻两个迭代点,和,已经很,靠近了，,但它们距极小点,却都很远，而且这两点的,目标函数值,和,还由极限理论知道，当,相差很大。,很小时，,也必然很小。因此，如果加上,（,1.52,）,这个条件，那么可靠性就会加强。上图,2,指出了只采用（,1.52,）也是不可靠的。虽然,与,相差很小，可,是相应的两个迭代点,和,却相距很远，它们距,极,也很远。,小点,需要注意的是，实际应用中，由于,和,所取的量,纲有时太大，这时如果仍然以（,1.51,）和（,1.52,）作为终止准则就太严格了。结果要么是用更多的计算才能使得（,1.51,）和（,1.52,）得到满足，而这是不划算的；要么是永远不能满足。解决这个问题的办法是，,先对,和,作无量纲处理，然后再结合（,1.51,）和（,1.52,），给出,（,1.53,）,和,（,1.54,）,作为终止准则。,此外，有一类无约束最优化方法在求解过程中利用了梯度。由于,为极小点的必要条件是,。因此，,当,满足,（,1.55,）,时，一般可以认为,就是所要求的最优解。由于条件不是,充分的，所以单独以（,1.55,）作为终止准则也是不可靠的。,最后的结论是：对于使用导数的最优化方法，可按书上图所示的判别过程作为终止准则；对于不使用导数的最优化方法，则只需把图中涉及,的部分去掉。今后,统称为,Himmelblau,计算终止准则，简称,H,终止准则。,