第二章 最优化问题数学基础

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 最优化问题数学基础,为了便于学习最优化方法，本章将对与,优化方法密切有关的数学知识作一简要介绍,而有些数学知识将在讲解各种算法时，随之,介绍,1.1,二次型与正定矩阵,一、二次型与实对称矩阵,二次型理论在最优化设计中应用十分广泛应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题,二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题推广到,n,维空间中，二次超曲面的一般方程为,用矩阵表示为,其中，矩阵,A,的元素正是二次型的,项的系数的一半，是二次型的项,的系数因此，二次型和它的矩阵,A,是相互,唯一决定的，且,二、正定矩阵,定义,2.1,如果二次型,对于任何一组不全为零的数恒有,则称正定，且二次型矩阵,A,也称为正定,简言之，一个对称矩阵,A,如果是正定的，则二次型,对于所有非零向量,X,其值总为正类似可以给出定义，若二次型,则,A,为半正定矩阵；若，则,A,为半负定矩阵；若二次型既不是半正定又不是半负定，就称矩阵,A,为不定的,矩阵,A,为正定的充要条件是它的行列式的顺序主子式全部大于零，即,由此可见，正定矩阵必然是非奇异的,例,2.1,判断矩阵 是否正定,解 ，,A,是正定的,一、方向导数,所谓方向导数的概念是作为偏导数的一个推广而引入，它主要研究函数沿任一给定方向的变化率,定义,2.2,设 在点 处可微，,P,是固定不变的非零向量， 是方向,P,上的单位向量，则称极限,(2.1),为函数 在点 处沿,P,方向的方向导数，式中,是它的记号,2.2,方向导数与梯度,定义,2.3,设 是连续函数， ，且 ，若存在 ，当 时都有，,则称,P,为在点处的下降方,向若 ，则称,P,为在点处的上升方向,由以上两个定义可立刻得到如下的结论：,若 ，则 从 出发在 附近沿,P,方向是下降；若 ，则从出发在附近沿,P,方向是上升,二、梯度,定义,2.4,以 的,n,个偏导数为分量的向量称为 在,X,处的梯度，记为,梯度也可以称为函数 关于向量 的一阶导数,以下几个特殊类型函数的梯度公式是常用的：,（,1,）若 （常数），则 ，即 ；,（,2,）,证 设 ，则,于是 的第 个分量是,所以,（,3,） ,（,4,）若,Q,是对称矩阵，则,三、梯度与方向导数之间的关系,定理,2.1,设 在点 处可微，则,，,其中 是 方向上的单位向量,.,由这个定理容易得到下列结论：,(1),若 ，则,P,的方向是函数在点 处的下降方向；,(2),若 ，则 的方向是函数在点 处的上升方向,方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定绝对值越大，升降的速度就越快，即,=,1,上式中的等号，当且仅当的方向与的方向相同时才成立,由此可得如下重要结论,(,如图,2.1,所示）：,(1),梯度方向是函数值的最速上升方向；,(2),函数在与其梯度正交的方向上变化率为零；,(3),函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；,(4),梯度反方向是函数值最速下降方向,1,对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向总是希望它等于或者是靠近于目标函数的负梯度,-,图,2.1,的方向，这样才能使函数值下降的最快,例,2.2,试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长后新点的目标函数值,解,因为,所以最速下降方向是,= =,这个方向上的单位向量是,故新点是,对应目标函数值为,2.3,海色矩阵及泰勒展式,一、海色（,Hesse,）矩阵,前面说过，梯度 是 关于 的一阶导数，现在要问 关于 的二阶导数是什么？,定义,2.5,设：,:,， ，如果在点,处对于自变量的各分量的二阶偏导数,都存在，则称函数在点处二阶可导，并且称矩阵,是 在点 处的,Hesse,矩阵,在数学分析中已经知道，当 在点 处的所有二阶偏导数为连续时有,因此，在这种情况下,Hesse,矩阵是对称的,例,2.3,求目标函数 的梯度和,Hesse,矩阵,解 因为,所以,又因为,所以,例,2.4,设 ，求线性函数,在任意点,X,处的梯度和,Hesse,矩阵,解,:,设,则,（,2.2,）,由式（,2.2,）进而知, （阶零矩阵）,例,2.5,设 是对称矩阵， ，求二次函数,在任意点处的梯度和,Hesse,矩阵,解 设 则,将它对各变量 求偏导数，得,在上式中显然,再对它们求偏导数得,以上例子说明，元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵,最后介绍在今后的计算中要用到的向量函数的导数,定义,2.6,设 ，记,如果 在点 处于自变量 的各分量的偏导数 都存在，则称向量函数,在点 处是一阶可导的，并且称矩阵,是在点处的一阶导数或,Jacobi,矩阵，简记为,由于,n,元函数 的梯度是向量函数,所以 的一阶导数或,Jacobi,矩阵为,得到,据此，从上式得知，函数梯度的,Jacobi,矩阵即为此函数的,Hesse,矩阵,下面给出今后要用到的几个公式：,（,1,） ，其中 是分量全为常数的 维向量，是,阶零矩阵,（,2,） ，其中 是维向量，是 阶单位矩阵,（,3,） ，其中 是 阶矩阵,（,4,）设 ，其中 ，则,二、泰勒展开式,多元函数的泰勒展开在最优化方法中十分重要，许多方法及其收敛性的证明是从它出发，这里给出泰勒展开定理及其证明,定理,2.2,设 具有二阶连续偏导数，则,（,2.3,）,其中 ，而 ,证 设 ，于是,对 按一元函数在 点展开，得到,其中 令 ，于是,(2.4),又因为,代入式（,2.4,）中，所以,式（,2.3,）还可以写成,2.4,极小点的判定条件,函数在局部极小点应满足什么条件？反之，满足什么条件的是局部极小点？这是我们关心的基本问题,下面针对多元函数的情形给出各类极小点的定义,定义,2.7,对于任意给定的实数 ，满足不等式,集合称为点的邻域，记为,定义,2.8,设 ，若存在点 和数 ，,都有 ，则称 为 局部极小点（非严格）,定义,2.9,设 ，若存在点 和数 ， 但 ，都有 ，则称 为 的严格局部极小点,定义,2.10,设 ，若存在点 和数 ， 都有 ，则称 为 在,D,上的全局极小点（非严格）,定义,2.11,设 ，若存在点 ，,但 ，都有 ，则称 为,在,D,上的严格全局极小点,由以上定义看到，是局部极小点，是指在以为中心的一个邻域中在点处取得最小的值；而是全局极小点，是指在定义域,D,中在点处取得最小的值全局极小点可能在某个局部极小点处取得，也可能在,D,的边界上取得实际问题通常是求全局极小点，但是直到目前为止，最优化中绝大多数方法都是求局部极小点的，解决这一矛盾的一种方法是先求出所有的局部极小点，再求全局极小点,定理,2.3,设 具有连续的一阶偏导数若 是 的局部极小点并且是,D,的内点，则,（,2.5,）,证 设 是任意单位向量，因为 是 的局部极小点，所以存在 ，当 或,时总有, （,2.6,）,引入辅助一元函数 ，此时，由式（,2.6,）得 又因,是,D,的内点，所以与它对应的 是 的局部极小点又根据一元函数极小点的必要条件，得到 ，即 再由单位向量 的任意性得 ,这里条件（,2.5,）仅仅是必要的，而不是充分的例如 在点 处的梯度是 ，但 是双曲面的鞍点，而不是极小点（如图,2.2,所示）,定义,2.12,设 是,D,的内,点若 ，则称 为 的驻点,定理,2.4,设 具有连续二阶偏导数， 是,D,的一个内点若 ，并且 是正定的，则 是 的严格局部极小点,证 因为 是正定矩阵，则必存在 ，使得对于所有的 都有,（参看高等代数二次型理论）现在将,在点 处按泰勒公式展开，并注意到 ，于是可得,当 充分接近 （但 ）时，上式左端的符号取决于右端第一项，因此,一般说来，这个定理仅具有理论意义因为对于复杂的目标函数，,Hesse,矩阵不易求得，它的正定性就更难判定了,定理,2.5,若多元函数在其极小点处的,Hesse,矩阵是正定的，则它在这个极小点附近的等值面近似地呈现为同心椭球面族,证 设 是多元函数的极小点，并设 是充分靠近极小点 的一个等值面，即 充分小把 在点 展成泰勒表达式，即,右端第二项因 是极小点有 而消失如果略去第,4,项,那么,又因为 ，所以,（,2.7,）,按假设 正定，由二次型理论知式（,2.7,）是以 为中心的椭球面方程,2.5,锥、凸集、凸锥,在本节中，给出维,Euclid,空间 中的锥、凸集和凸锥的定义，以及与其相关的一些概念和性质,一、定义与简单性质,定义,2.13,集合 若 ，及任意的数 ，均有 ，则称,C,为锥,定义,2.14,设 是 中的 个已知点若对于某点 存在常数 且 使得 ，则称 是 的凸组合若,且 ，则称 是 的严格凸组合,定义,2.15,集合 若 和 ，以及任,意的数 ，均有,则称,C,为凸集,定义,2.16,设 且 ， ，则集合,称为 中的半空间,特别地，规定：空集是凸集容易验证，空间 、半空间、超平面、直线、点、球都是凸集,定理,2.6,任意一组凸集的交仍然是凸集,证 设 ，其中,I,是 的下标集， 都是凸集任取，则对于任意都是任取,且 ，因 是凸集,有,于是 ，即,C,是凸集,若集合,C,为锥，,C,又为凸集，则称,C,为凸锥若,C,为凸集，也为闭集，则称,C,为闭凸集若,C,为凸锥，也为闭集，则称,C,为闭凸锥,由数学归纳法不难证明如下的定理,2.7,和,2.8,定理,2.7,集合,C,为凸集的充分必要条件是 ，及任意数 （ ）,，有,定理,2.8,集合,C,为凸锥的充分必要条件是 ，及任意数,( ),，均有,定义,2.17,有限个半空间的交 称为多面集,其中 为 矩阵，为 向量,例,2.6,集合,为多面集，其几何表示如图,2.3,画斜线部分,图,2.3,在多面集的表达式中，若 ，则多面集 也是凸锥，称为多面锥,在有关凸集的理论及应用中，极点和极方向的概念有着重要作用,定义,2.18,设,C,为非空凸集，,若 不能表示成,C,中两个不同点的凸组合；换言之，若设,必推得 ，则称 是凸集,C,的极点,按此定义，图,2.4(a),中多边形的顶,点 ， ， ， 和 是极点，而 和 不是极点图,2.4(b),中圆周上的点均为极点,由图,2.4,可以看出，在给定的两个凸集中，任何一点都能表示成极点的凸组合,定义,2.19,设,C,为 中的闭凸集，,P,为非零向量，如果对,C,中的每一个 ，都有射线 ，则称向量,P,为,C,的方向又设 和 是的两个方向，若对任何正数 ，有 ，则称 和 是两个不同的方向若,C,的方向,P,不能表示成该集合的两个不同方向的正的线性组合，则称,p,为,c,的极方向,概括起来，有下列定理：,定理,2.9,（,Representation Theorem,）,设 为非空多面集，则有,（,1,）极点集非空，且存在有限个极点,（,2,）极方向集合为空集的充要条件是,C,有界若无界，则存在有限个极方向,（,3,） 的充要条件是,其中,二、凸集分离定理,凸集分离定理是凸分析中最重要的定理之一，它在最优化理论和模型当中具有重要的应用,所谓集合的分离是指对于两个集合,C,1,和,C,2,存在一个超平面,H,，使得,C,1,在,H,的一边，而,C,2,在,H,的另一边如果超平面方程为 ，那么对位于,H,某一边的点必有 ，而对位于,H,另一边的必有 ,定义,2.20,设,C,1,和,C,2,是 中的两个非空集合，,是超平面，若对于每一个 都有 ，对于每一个 都有 （或情况恰好相反），则称超平面,H,分离集合,C,1,和,C,2,定理,2.10,若,C,为闭凸集， ，则存在,以及数 ，对 ，有,并且存在 ，使得 ,定理,2.11,设,C,为凸集， ，则存在,使得 ，有,定理,2.12,设,C,为闭凸集，则,C,可表为所有包含,C,的半空间的交，即,其中,2.6,凸函数,一、各类凸函数定义及性质,设函数 定义在凸集,R,上，其中,定义,2.21,若存在常数 ，使得,以及 ，有,则称 为一致凸函数；有,则称为严格凸函数；有,则称为凸函数,定义,2.22,设 为可微函数若,满足,都有,则称 为伪凸函数,定义,2.23,对 ，且 ，以及 ，若,则称为严格拟凸函数；,定义,2.24,对 ，以及 ，若,则称为拟凸函数；,定义,2.25,对,则称为强拟凸函数,定理,2.13,若 为一致凸函数，则为严格凸函数,证：设 为一致凸函数，则 ， ， ，及 ，有,即为严格凸函数,定理,2.14,若为严格凸函数，则为凸函数,定理,2.15,设为可微函数若为凸函数，则为伪凸函数,定理,2.16,设为伪凸函数，则为严格拟凸函数,定理,2.17,设为下半连续的严格拟凸函数，则为拟凸函数,定理,2.18,若为严格凸函数，则为强拟凸函数,定理,2.19,设为强拟凸函数，则为严格拟凸函数,凸函数与凸集之间有如下关系：,定理,2.20,设 ， 其中,C,为非空凸集若,f,是凸函数，则对于任意实数 ，水平集 是凸集,证 若 是空集，则 是凸集以下设 非空，任取 ，则 设 且,，由,f,是凸函数知,即 ，所以 是凸集,判定一个函数是否为凸函数，一般说来是比较困难，但当函数可微时，有如下几个定理可供使用,定理,2.21,设 是可微函数，其中,C,为凸集则,（,1,）为凸函数的充要条件是， ，都有,（,2.11,）,（,2,）为严格凸函数的充要条件是， 且,都有,证 （,1,）必要性 已知,f,是,C,上的凸函数，要证式,（,2.11,）由凸函数定义知，对满足 的任意数,都有,令 ，则 代入上式中，经移项可得,（,2.12,）,令 ，由,f,的可微性，利用一阶泰勒展式、方向导数定义及式（,2.12,），可得,这就证明了式（,2.11,）,充分性 任取一对数 且 考虑点 ，根据充分性假设，应有,两式分别乘以 和 后相加，得到,由凸函数定义知,f,是,C,上的凸函数,（,2,）充分性可依照（,1,）的充分性证得,必要性 因为严格凸函数本身是凸函数，所以 且,都有,以下证明式中只能取“,”,号假设存在 ，且 ，使得,（,2.12,）,取 ，由的严格凸性，有,（,2.13,）,把式（,2.12,）代入式（,2.13,）中，经整理得,根据本定理（,1,）部分结论得知，此式与是凸函数相矛盾,定理,2.22,设 是二次可微函数，,C,为非空开凸集，则,f,为,c,上凸函数的充要条件是，,Hesse,矩阵 在,C,上到处半正定,证明略,定理,2.23,设 是二次可微函数，,C,为非空凸集若,Hesse,矩阵在,C,上到处正定，则,f,在,C,上为严格凸函数,证明略，需要注意，该定理的逆命题不真,例如 为严格凸函数，但是它的,Hesse,矩阵在点,x=0,处是半正定的,二、凸规划,定义,2.26,设 ，其中,C,是非空凸集，,f,是凸函数，则形式为 的问题称为凸规划问题,更进一步，设,若 都是 上的凸函数， 都是,上的线性函数，则容易验证,C,是凸集事实上，因为 都是凸函数，根据定理,2.20,集合,也都是凸集此外，超平面 ，也都是凸集显然，,C,是 的交集，根据定理,2.6,，,C,是凸集于是，在这种情况下凸规划问题又可表示成如下形式：,定理,2.24,设 是凸规划问题的局部极小点，,（,1,）若,f,是凸函数，则 是凸规划问题全局极小点；,（,2,）若,f,是严格凸函数，则 是凸规划问题的唯一全局极小点,证（,1,）使用反证法假设 不是全局极小点，则必存在 使得 对于,Z,与,的任意凸组合 ，其中 且 ，根据的凸性，有,由此看到，当 充分小时，充分接近,注意到此时也有,而这与 是局部极小点相矛盾因此 必是全局极小点,（,2,）假设 不是唯一全局极小点必存在 但 使得 考虑中点 由,f,的严格凸性，有 此式与,为全局极小点相矛盾这就证明了唯一性,定义,2.27,形式为,（,2.14,）,的函数称为,n,元二次函数，其中,这里的,Q,是对称矩阵，即,若,Q,为正定，则称（,2.14,）为正定二次函数注意到,，由定理,2.23,知，正定二次函数是严格凸函数，在最优化算法构造中它起着特殊的作用,定义,2.28,形式为,（,2.15,）,的问题称为二次规划问题，其中是矩阵，是矩阵,若,Q,为半正定或正定，则称（,2.15,）为二次凸规划问题本书不作专门讨论,2.7,约束问题的最优性条件,所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的最优性必要条件是指，在最优点处满足哪些条件；充分条件是指满足哪些条件的点是最优点本节仅讲述最基本的结论,一、约束最优解,对约束优化问题的求解，其目的是在由约束条件所规定的可行域内，寻求一个目标函数值最小的点及其函数值这样的解称为约束最优解约束最优点除了可能落在可行域内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同,（一）约束优化问题的类型,约束优化问题根据约束条件类型的不同分为三种，其数学模型如下：,（,1,）不等式约束优化问题（,IP,型）,（,2.16,）,（,2,）等式约束优化问题（,EP,型）,（,3,）一般约束优化问题（,GP,型）,（二）约束优化问题的局部解与全局解,按一般约束优化问题，其可行域为,若对某可行点 存在 ，当 与它邻域的点 之距离 时，总有 则称 为该约束优化问题的一个局部最优解,下面以一个简单例子说明设有,该问题的几何图形如图,2.8,所示从图上的目标函数等值线和不等式约束与等式约束的函数曲线可写出它的两个局部最优解 ， 这是因为在 点邻域的任一满足约束的点 ，都有,同理，亦然,对某些约束优化问题，局部解可能有多个在所有的局部最优解中，目标函数值最小的那个解称为全局最优解,在上例中，由于，所以全局最优解为,由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解这与无约束优化问题是相同的,二、约束优化问题局部解的一阶必要条件,对于约束，我们现在进一步阐明起作用约束与不起作用约束的概念一般的约束优化问题，其约束包含不等式约束 和等式约束 ，在可行点 处，如写有,则该约束 称可行点 不起作用约束对于等式约束，显然在一可行点的等式约束 都是起作用约束,在某个可行点 处，起作用约束在 的邻域内起到限制可行域范围的作用，而不起作用约束在 处的邻域内就不产生影响因此，应把注意力集中在起作用约束上,（一）,IP,型约束问题的一阶必要条件图,2.9,所示具有三个不等式约束的二维最优化问题,图,2.9,（,a,）是最优化在可行域内部的一种情况在此种情形下，点的全部约束函数值 均大于零，所以这组约束条件对其最优点都不起作用换句话说，如果除掉全部约束，其最优点也仍是同一个点因此这种约束优化问题与无约束优化问题是等价的图,2.9,（,b,）所示的约束最优点在 的边界曲线与目标函数等值线的切点处此时 所以 是起作用约束，而其余的两个是不起作用约束,