最优化方法 第一章

1、,或,解法：Lagrange乘子法,1.2 实例 数据拟合问题 原料切割问题 运输问题 营养配餐问题 分配问题,1.3 基本概念 1. 最优化问题的向量表示法 设,则,（1）,以向量为变量的实值函数 定义向量间的序关系(定义1.1)：,等于，小于,，严格小于,。由此,（2）,以向量为变量的实向量值函数最优化问题的一般形式,（3）,2. 最优化问题的分类,试验问题：用于检验、比较最优化方法优劣的一些最优化问题。,3. 术语,目标函数,等式约束,不等式约束,容许解（点）,容许集,求解问题（3）是指：在容许集,中找一点,目标函数,在该点取极小值，即对于容许集中的任,，总有,意一点,最优点（极小点）,

2、最优值,最优解,严格极小点,局部,非严格极小点,严格极小点,非严格极小点,全局,，使得,到目前为止，大多数最优化算法求到的都是局部极小点。为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。,4. 极大值问题与极小值问题的关系,1.4 二维问题图解法,二维极值问题有时可以用图解的方式进行求解，有 明显的几何解释。,例 求解,图解法的步骤：,，显然,；,取,并画出相应的曲线（称之为等值线）.,确定极值点位置，并用以往所学方法求之。,易知本题的极小值点,。,再复杂点的情形见P13上的例1.7。,虽然三维及以上的问题不便于在平面上画图，图解法失效，但仍有相应的等值面

3、的概念，且等值面具有以下性质：,有不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；,等值面不会在区域的内部中断，除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故；,令,等值面稠密的地方，目标函数值变化得比较快；等值 面稀疏的地方，目标函数值变化得比较慢；,在极值点附近，等值面（等值线）一般近似地呈现为同心椭球面族（椭圆线族）。,1.5 梯度和Hesse矩阵,本段讨论都基于对函数,以下及今后的讨论中还经常要用到以下一些向量的知识。,可微的假定。,与,。,记作,。,向量也常用希腊字母,等表示。,向量内积的性质：,),（对称性）；,),（线性性）；,),当且仅当,时，,（正定性

4、）；,向量的内积 设,则,称为向量,的内积，,其实，,向量的长,单位向量,向量的夹角 ，,向量的正交,（正交性）,1.可微,定义1.7 设,.如果存在,维向量,对于可任意小的,维非零向量,，总有,在点,那么称函数,处可微。,若令,便得到（1.9）的等价形式,. （1.10）,2.梯度,定理1.1 若,在点,处可微，则,在该点关于各个变量的一阶偏导数存在，并且,定义1.8 以函数,的,个偏导数为分量的向量,称为,在点,处的梯度，记为,。,。,梯度也称为函数,关于变量,于是，（1.10）可写为,这个公式与一元函数展开到两项的Taylor公式是相对的。,梯度的性质：,当梯度,连续时，,第一，若,，则

5、,必垂直于,过点,处的等值面；,的一阶偏导数。,第二，梯度方向是函数具有最大变化率的方向。,下面以,为例来解释这个性质。,上图是该函数的等值线图。,今考虑一点,，不妨取坐标为,。设想有,出发沿某个方向移动到了点,，其坐标,，那么目标函数值将产生如下变化量,一动点从,设为,假定,。试问：动点沿哪个方向移动会使,目标函数值有最多的下降或上升？,从图上看，这相当于问：在以点,为圆心、以1为半径,的圆周上，哪一个点具有最大的或最小的目标函数值。,为了一般地描述函数,在点,处沿,情况及变化速度，须引入上升方向和下降方向及方向导数 的概念。,方向的变化,函数,在点,处沿,方向的变化反映的是函数,在一条直线

6、上的变化，空间中由一点,和一方向,所确定的直线方程为,上升方向和下降方向 设,是连续函数。,若存在,，对于,都有,，则称,方向是,在点,处的上升方向；若存在,对于,都有,，则称,方向是,在点,处的下降方向。,定义1.9 设,在点,处可微，,是非,方向上的单位向量。如果极限,零向量,存在，则称其为函数,在点,处沿,方向的方向导数，,。,记作,思考：,与,的异同。,若,，则,方向是,在点,处的上升方向；,根据极限理论，易见,若,，则,方向是,在点,处的下降方向。,因此，方向导数的正负决定了函数值的升降。,定理1.2 设,在点,处可微，则,，,其中,是非零向量,方向上的单位向量。,定理1.2又表明：

7、只要,，则,方向是,在点,处的上升方向；只要,，则,方向是,在点,处的下降方向。,函数值升降的快慢则是由方向导数绝对值的大小决 定的。绝对值越大，升或降的速度就越快；绝对值越小， 升或降的速度就越慢。这是因为,据此有,) 等号成立当且仅当,与,同方向或与,同方向。且当,与,同方向时，,取到最大值,。,当,与,同方向时，,取到最小值,) 若,是锐角，则,;,若,是钝角，则,。,因此，方向导数又可以称为函数,在点,处沿,方向的变化率。,使函数值下降最快的方向称为最速下降方向。,最速下降方向为,例1.8 P19,几个常用函数的梯度公式,（1）若,，则,，即,（2）,（3）,；,（4）,.,；,；,2

8、. Hesse矩阵,问：函数,关于变量,的二阶导数又是什么？,先来看什么是向量值函数的可微。,定义1.11 设,。,若,的所有分量,在点,都可微，则称向量值函数,在点,处可微。,定义表明，,在点,处可微，则,成立，,其用向量形式可简单地表示为,其中,称为向量值函数,在点,处的导数，,而,称为向量值函数,在点,处的Jacobi矩阵。,设,具有二阶连续偏导数，且,则矩阵,称为函数,关于变量,的二阶导数，简记为,。,也称为多元实值函数,的Hesse矩阵。,例1.9 P21,几个特殊的向量值函数的导数公式：,（1）,；,（2）,；,（3）,；,（4）设,，其中,。则,利用（4），可得多元函数展开到三项

9、的Taylor公式,（1.29）,或,（1.31）,这个公式与一元函数展开到三项的Taylor公式是相对应的。,多元函数的Taylor展开式在最优化方法中十分重要， 许多方法及其收敛性的证明都是从它出发的。,1. 凸集,1.6 凸函数与凸规划,直观上，凸集就是空间中内部无“洞”，边界又不向 内凹的一些点的集合，其基本特征是该集合中任意两点 间的线段仍然属于这个集合。,非凸集,凸集,空间中两点间的线段是由点的凸组合定义的。,定义1.12 设,是,中的,个已知点。,点,，若存在满足,的非负实数,对于,使得,，则称,是,的一个凸组合。,又若,是满足,的正实数，则称,是,的一个严格凸组合。,两点,的凸

10、组合,恰是连接两点的,的线段。,线段，而严格凸组合是不含端点,定义1.13 设集合,。如果,中任意两点的,，那么集合,称为凸集。,任意凸组合仍然属于,规定：空集是凸集。,思考：空间中三个不同点的凸组合的集合，空间中 四个不同点的凸组合的集合.,常见的凸集有超平面，直线，球.,定理1.5 凸集的交集是凸集。,2. 凸函数,定义1.16 设,，其中,为凸集。若对于,中的任意互异两点,和任意一对满足,的非负实数,，,总有,则称,是定义在凸集,上的凸函数。又若对于任意,的正实数,，总有,一对满足,则称,是定义在凸集,上的严格凸函数。,若,是凸集,上的（严格）凸函数，则称,是凸集,上的（严格）凹函数。,

11、凸函数有以下重要性质。,定理1.6,（1）若,是定义在凸集,上的凸函数，,是,也是,上的凸函数。,任意的非负实数，则,（2）若,是定义在凸集,上的凸函数，则,也是,上的凸函数。,由定理1.6易见，定义在凸集上的任意有限个凸函数 的任意非负组合仍然是凸函数。,例1.10,定理1.7 设,，其中,为非空凸集，若,是凸函数，则对于任意实数,，,水平集,是凸集。,证 若,是空集，则是凸集。以下设,非空。任取,，则,。又设,但,，根据,的凸性，必有,即,。因此，,是凸集。,判断一个函数是否为凸函数，一般说来，是比较困 难的。但当函数可微时，有以下几个判定定理。,定理1.7 设,定理1.8 设,是可微函数

12、，其中,为,凸集。则,),为凸函数的充要条件是对于,中的任意两点,，都有,),为严格凸函数的充要条件是对于,中的任意,都有,两个互异点,定理1.8有明显直观的几何解释。 可微函数为凸函数的充要条件是在其 定义域凸集中任一点处的切平面（切 线）都不在曲面（曲线）的上方。右 图画出了一维的情形。,定理1.9 设,是二次可微函数，,为非,空开凸集。,则,为,上凸函数的充要条件是Hesse矩阵,在,上处处半正定。,定理1.10 设,是二次可微函数，,为非,空凸集，,若,的Hesse矩阵,在,上处处正定，则,是,上的严格凸函数。,这个命题的逆命题不真。,例如，,在,上为严格凸函数，,在,处是半正定的。,

13、但是它的Hesse矩阵,3. 凸规划,设,是定义在非空凸集,上的凸函数，,则形式为,（1.36）,的最优化问题称为凸规划问题，简称凸规划。换言之， 定义在凸集上的凸函数的极小化问题是凸规划问题。,若,都是,上的凹函数，,都是,上的线性函数，容易验证集合,是凸集。在这种情况下，凸规划（1.36）可以表示成如下形式,（1.37）,下面的定理指出了凸规划的一些重要性质。,定理1.11 设,是凸规划（1.36）的局部极小点。则,i）,是（1.36）的全局极小点；,ii）当,是严格凸函数时，,是（1.36）的唯一极小点；,iii）（1.36）的全部极小点的集合是凸集。,定理1.12 设,是可微凸函数，,是非空,。,凸集，,则,是凸规划（1.36）的极小点的充要,中任意一点,，总有,。,条件是，对于,定理1.12表明，凸规划（1.36）在最优点处的任何 容许方向