最优化问题数学基础.doc

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