最优化问题数学基础.pptx

《最优化问题数学基础.pptx》由会员分享，可在线阅读，更多相关《最优化问题数学基础.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共63页用矩阵表示为其中，矩阵A的元素正是二次型的项的系数的一半，是二次型的项的系数因此，二次型和它的矩阵A是相互唯一决定的，且第2页/共63页二、正定矩阵定义2.1 如果二次型对于任何一组不全为零的数恒有则称正定，且二次型矩阵A也称为正定简言之，一个对称矩阵A如果是正定的，则二次型 对于所有非零向量X其值总为正类似可以给出定义，若二次型则A为半正定矩阵；若，则A为半负定矩阵；若二次型既不是半正定又不是半负定，就称矩阵A为不定的第3页/共63页矩阵A为正定的充要条件是它的行列式的顺序主子式全部大于零，即由此可见，正定矩阵必然是非奇异的例2.1 判断矩阵 是否正定解 ，A是正定的第4页/

2、共63页一、方向导数所谓方向导数的概念是作为偏导数的一个推广而引入，它主要研究函数沿任一给定方向的变化率 定义2.2 设 在点 处可微，P是固定不变的非零向量，是方向P上的单位向量，则称极限 (2.1)为函数 在点 处沿P方向的方向导数，式中 是它的记号2.2 方向导数与梯度第5页/共63页定义2.3 设 是连续函数，且 ，若存在 ，当 时都有，则称P为在点处的下降方向若 ，则称P为在点处的上升方向由以上两个定义可立刻得到如下的结论：若 ，则 从 出发在 附近沿P方向是下降；若 ，则从出发在附近沿P方向是上升第6页/共63页二、梯度定义2.4 以 的n个偏导数为分量的向量称为 在X处的梯度，记

3、为 梯度也可以称为函数 关于向量 的一阶导数以下几个特殊类型函数的梯度公式是常用的：（1）若 （常数），则 ，即 ；（2）证 设 ，则于是 的第 个分量是所以（3）（4）若Q是对称矩阵，则第7页/共63页三、梯度与方向导数之间的关系定理2.1 设 在点 处可微，则 ，其中 是 方向上的单位向量.由这个定理容易得到下列结论：(1)若 ，则P的方向是函数在点 处的下降方向；(2)若 ，则 的方向是函数在点 处的上升方向方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定绝对值越大，升降的速度就越快，即 第8页/共63页 =1 上式中的等号，当且仅当的方向与的方向相同时才成立由此可得

4、如下重要结论(如图2.1所示）：(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值最速下降方向 1 第9页/共63页对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向总是希望它等于或者是靠近于目标函数的负梯度-图2.1的方向，这样才能使函数值下降的最快第10页/共63页例2.2 试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长后新点的目标函数值解 因为所以最速下降方向是 =这个方向上的单位向量是故新点是 对应目标函数值为

5、第11页/共63页2.3 海色矩阵及泰勒展式一、海色（Hesse）矩阵前面说过，梯度 是 关于 的一阶导数，现在要问 关于 的二阶导数是什么？定义 2.5 设：:，如果在点 处对于自变量的各分量的二阶偏导数都存在，则称函数在点处二阶可导，并且称矩阵第12页/共63页是 在点 处的Hesse矩阵在数学分析中已经知道，当 在点 处的所有二阶偏导数为连续时有因此，在这种情况下Hesse矩阵是对称的 第13页/共63页例2.3 求目标函数 的梯度和Hesse矩阵解 因为 所以第14页/共63页又因为所以 第15页/共63页例2.4 设 ，求线性函数在任意点X处的梯度和Hesse矩阵解:设 ,则 （2.

6、2）由式（2.2）进而知 （阶零矩阵）第16页/共63页例2.5 设 是对称矩阵，求二次函数 在任意点处的梯度和Hesse矩阵解 设 则将它对各变量 求偏导数，得 第17页/共63页在上式中显然再对它们求偏导数得 以上例子说明，元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵 最后介绍在今后的计算中要用到的向量函数的导数第18页/共63页定义2.6 设 ，记 如果 在点 处于自变量 的各分量的偏导数 都存在，则称向量函数 在点 处是一阶可导的，并且称矩阵第19页/共63页是在点处的一阶导数或Jac

7、obi矩阵，简记为 由于n元函数 的梯度是向量函数所以 的一阶导数或Jacobi矩阵为第20页/共63页 得到第21页/共63页据此，从上式得知，函数梯度的Jacobi矩阵即为此函数的Hesse矩阵下面给出今后要用到的几个公式：（1），其中 是分量全为常数的 维向量，是 阶零矩阵（2），其中 是维向量，是 阶单位矩阵（3），其中 是 阶矩阵（4）设 ，其中 ，则第22页/共63页二、泰勒展开式多元函数的泰勒展开在最优化方法中十分重要，许多方法及其收敛性的证明是从它出发，这里给出泰勒展开定理及其证明 定理2.2 设 具有二阶连续偏导数，则 （2.3）其中 ，而 证 设 ，于是对 按一元函数在 点

8、展开，得到其中 令 ，于是 (2.4)第23页/共63页又因为代入式（2.4）中，所以 式（2.3）还可以写成 第24页/共63页2.4 极小点的判定条件函数在局部极小点应满足什么条件？反之，满足什么条件的是局部极小点？这是我们关心的基本问题下面针对多元函数的情形给出各类极小点的定义定义2.7 对于任意给定的实数 ，满足不等式 集合称为点的邻域，记为定义2.8 设 ，若存在点 和数 ，都有 ，则称 为 局部极小点（非严格）第25页/共63页定义2.9 设 ，若存在点 和数 ，但 ，都有 ，则称 为 的严格局部极小点定义2.10 设 ，若存在点 和数 ，都有 ，则称 为 在D上的全局极小点（非严

9、格）定义2.11 设 ，若存在点 ，但 ，都有 ，则称 为 在D上的严格全局极小点第26页/共63页由以上定义看到，是局部极小点，是指在以为中心的一个邻域中在点处取得最小的值；而是全局极小点，是指在定义域D中在点处取得最小的值全局极小点可能在某个局部极小点处取得，也可能在D的边界上取得实际问题通常是求全局极小点，但是直到目前为止，最优化中绝大多数方法都是求局部极小点的，解决这一矛盾的一种方法是先求出所有的局部极小点，再求全局极小点第27页/共63页定理2.3 设 具有连续的一阶偏导数若 是 的局部极小点并且是D的内点，则 （2.5）证 设 是任意单位向量，因为 是 的局部极小点，所以存在 ，当

10、 或 时总有 （2.6）引入辅助一元函数 ，此时，由式（2.6）得 又因 第28页/共63页是D的内点，所以与它对应的 是 的局部极小点又根据一元函数极小点的必要条件，得到 ，即 再由单位向量 的任意性得 这里条件（2.5）仅仅是必要的，而不是充分的例如 在点 处的梯度是 ，但 是双曲面的鞍点，而不是极小点（如图2.2所示）第29页/共63页定义2.12 设 是D的内 点若 ，则称 为 的驻点定理2.4 设 具有连续二阶偏导数，是D的一个内点若 ，并且 是正定的，则 是 的严格局部极小点第30页/共63页证 因为 是正定矩阵，则必存在 ，使得对于所有的 都有 （参看高等代数二次型理论）现在将

11、在点 处按泰勒公式展开，并注意到 ，于是可得第31页/共63页当 充分接近 （但 ）时，上式左端的符号取决于右端第一项，因此 一般说来，这个定理仅具有理论意义因为对于复杂的目标函数，Hesse矩阵不易求得，它的正定性就更难判定了 第32页/共63页定理2.5 若多元函数在其极小点处的Hesse矩阵是正定的，则它在这个极小点附近的等值面近似地呈现为同心椭球面族证 设 是多元函数的极小点，并设 是充分靠近极小点 的一个等值面，即 充分小把 在点 展成泰勒表达式，即右端第二项因 是极小点有 而消失如果略去第4项,那么又因为 ，所以 （2.7）按假设 正定，由二次型理论知式（2.7）是以 为中心的椭球

12、面方程第33页/共63页2.5 锥、凸集、凸锥在本节中，给出维Euclid空间 中的锥、凸集和凸锥的定义，以及与其相关的一些概念和性质一、定义与简单性质定义2.13 集合 若 ，及任意的数 ，均有 ，则称C为锥定义2.14 设 是 中的 个已知点若对于某点 存在常数 且 使得 ，则称 是 的凸组合若 且 ，则称 是 的严格凸组合第34页/共63页定义2.15 集合 若 和 ，以及任意的数 ，均有 则称C为凸集定义2.16 设 且 ，则集合 称为 中的半空间特别地，规定：空集是凸集容易验证，空间 、半空间、超平面、直线、点、球都是凸集第35页/共63页定理2.6 任意一组凸集的交仍然是凸集证 设

13、 ，其中I是 的下标集，都是凸集任取，则对于任意都是任取 且 ，因 是凸集,有于是 ，即C是凸集若集合C为锥，C又为凸集，则称C为凸锥若C为凸集，也为闭集，则称C为闭凸集若C为凸锥，也为闭集，则称C为闭凸锥第36页/共63页由数学归纳法不难证明如下的定理2.7和2.8定理2.7 集合C为凸集的充分必要条件是 ，及任意数 （），有定理2.8 集合C为凸锥的充分必要条件是 ，及任意数 ,()，均有定义 2.17 有限个半空间的交 称为多面集,其中 为 矩阵，为 向量第37页/共63页例2.6 集合为多面集，其几何表示如图2.3画斜线部分图2.3在多面集的表达式中，若 ，则多面集 也是凸锥，称为多面

14、锥在有关凸集的理论及应用中，极点和极方向的概念有着重要作用第38页/共63页定义 2.18 设C为非空凸集，,若 不能表示成 C 中两个不同点的凸组合；换言之，若设 ,必推得 ，则称 是凸集 C的极点按此定义，图2.4(a)中多边形的顶 点 ，和 是极点，而 和 不是极点图2.4(b)中圆周上的点均为极点由图2.4可以看出，在给定的两个凸集中，任何一点都能表示成极点的凸组合第39页/共63页定义 2.19 设C为 中的闭凸集，P为非零向量，如果对C中的每一个 ，都有射线 ，则称向量P为C的方向又设 和 是的两个方向，若对任何正数 ，有 ，则称 和 是两个不同的方向若C的方向P不能表示成该集合的

15、两个不同方向的正的线性组合，则称p为c的极方向第40页/共63页概括起来，有下列定理：定理2.9（Representation Theorem）设 为非空多面集，则有（1）极点集非空，且存在有限个极点（2）极方向集合为空集的充要条件是C有界若无界，则存在有限个极方向（3）的充要条件是其中第41页/共63页二、凸集分离定理凸集分离定理是凸分析中最重要的定理之一，它在最优化理论和模型当中具有重要的应用所谓集合的分离是指对于两个集合C1和C2存在一个超平面H，使得C1在H的一边，而C2在H的另一边如果超平面方程为 ，那么对位于H某一边的点必有 ，而对位于H另一边的必有 定义2.20 设C1和C2是

16、中的两个非空集合，是超平面，若对于每一个 都有 ，对于每一个 都有 （或情况恰好相反），则称超平面H分离集合C1和C2第42页/共63页定理2.10 若C为闭凸集，则存在 以及数 ，对 ，有 并且存在 ，使得 定理2.11 设C为凸集，则存在 使得 ，有定理2.12 设C为闭凸集，则C可表为所有包含C的半空间的交，即其中第43页/共63页2.6 凸函数一、各类凸函数定义及性质设函数 定义在凸集R上，其中 定义2.21 若存在常数 ，使得 以及 ，有则称 为一致凸函数；有则称为严格凸函数；有则称为凸函数第44页/共63页定义2.22 设 为可微函数若 满足都有则称 为伪凸函数定义2.23 对 ，

17、且 ，以及 ，若则称为严格拟凸函数；定义2.24 对 ，以及 ，若则称为拟凸函数；定义2.25 对 则称为强拟凸函数第45页/共63页定理2.13 若 为一致凸函数，则为严格凸函数证：设 为一致凸函数，则 ，及 ，有即为严格凸函数第46页/共63页定理2.14 若为严格凸函数，则为凸函数定理2.15 设为可微函数若为凸函数，则为伪凸函数定理2.16 设为伪凸函数，则为严格拟凸函数定理2.17 设为下半连续的严格拟凸函数，则为拟凸函数定理2.18 若为严格凸函数，则为强拟凸函数定理2.19 设为强拟凸函数，则为严格拟凸函数第47页/共63页凸函数与凸集之间有如下关系：定理2.20 设 ，其中C为

18、非空凸集若f是凸函数，则对于任意实数 ，水平集 是凸集证 若 是空集，则 是凸集以下设 非空，任取 ，则 设 且 ，由f是凸函数知即 ，所以 是凸集判定一个函数是否为凸函数，一般说来是比较困难，但当函数可微时，有如下几个定理可供使用第48页/共63页定理2.21 设 是可微函数，其中C为凸集则（1）为凸函数的充要条件是，都有 （2.11）（2）为严格凸函数的充要条件是，且 都有证 （1）必要性 已知f是C上的凸函数，要证式 （2.11）由凸函数定义知，对满足 的任意数 都有令 ，则 代入上式中，经移项可得第49页/共63页 （2.12）令 ，由f的可微性，利用一阶泰勒展式、方向导数定义及式（2

19、.12），可得这就证明了式（2.11）充分性 任取一对数 且 考虑点 ，根据充分性假设，应有第50页/共63页两式分别乘以 和 后相加，得到由凸函数定义知,f是C上的凸函数（2）充分性可依照（1）的充分性证得必要性 因为严格凸函数本身是凸函数，所以 且 ,都有以下证明式中只能取“”号假设存在 ，且 ，使得 （2.12）第51页/共63页取 ，由的严格凸性，有 （2.13）把式（2.12）代入式（2.13）中，经整理得根据本定理（1）部分结论得知，此式与是凸函数相矛盾定理2.22 设 是二次可微函数，C为非空开凸集，则f为c上凸函数的充要条件是，Hesse矩阵 在C上到处半正定证明略第52页/共

20、63页定理2.23 设 是二次可微函数，C为非空凸集若Hesse矩阵在C上到处正定，则f在C上为严格凸函数证明略，需要注意，该定理的逆命题不真例如 为严格凸函数，但是它的Hesse矩阵在点x=0处是半正定的二、凸规划定义2.26 设 ，其中C是非空凸集，f是凸函数，则形式为 的问题称为凸规划问题第53页/共63页更进一步，设若 都是 上的凸函数，都是 上的线性函数，则容易验证C是凸集事实上，因为 都是凸函数，根据定理2.20集合 也都是凸集此外，超平面 ，也都是凸集显然，C是 的交集，根据定理2.6，C是凸集于是，在这种情况下凸规划问题又可表示成如下形式：第54页/共63页定理2.24 设 是

21、凸规划问题的局部极小点，（1）若f是凸函数，则 是凸规划问题全局极小点；（2）若f是严格凸函数，则 是凸规划问题的唯一全局极小点证（1）使用反证法假设 不是全局极小点，则必存在 使得 对于Z与的任意凸组合 ，其中 且 ，根据的凸性，有由此看到，当 充分小时，充分接近 ,注意到此时也有 ,而这与 是局部极小点相矛盾因此 必是全局极小点第55页/共63页（2）假设 不是唯一全局极小点必存在 但 使得 考虑中点 由f的严格凸性，有 此式与 为全局极小点相矛盾这就证明了唯一性定义2.27 形式为 （2.14）的函数称为n元二次函数，其中第56页/共63页这里的Q是对称矩阵，即若Q为正定，则称（2.14

22、）为正定二次函数注意到 ，由定理2.23知，正定二次函数是严格凸函数，在最优化算法构造中它起着特殊的作用定义2.28 形式为 （2.15）的问题称为二次规划问题，其中是矩阵，是矩阵若Q为半正定或正定，则称（2.15）为二次凸规划问题本书不作专门讨论 第57页/共63页 2.7约束问题的最优性条件所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的最优性必要条件是指，在最优点处满足哪些条件；充分条件是指满足哪些条件的点是最优点本节仅讲述最基本的结论一、约束最优解对约束优化问题的求解，其目的是在由约束条件所规定的可行

23、域内，寻求一个目标函数值最小的点及其函数值这样的解称为约束最优解约束最优点除了可能落在可行域内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同第58页/共63页（一）约束优化问题的类型约束优化问题根据约束条件类型的不同分为三种，其数学模型如下：（1）不等式约束优化问题（IP型）（2.16）（2）等式约束优化问题（EP型）（3）一般约束优化问题（GP型）第59页/共63页（二）约束优化问题的局部解与全局解按一般约束优化问题，其可行域为若对某可行点 存在 ，当 与它邻域的点 之距离 时，总有 则称 为该约束优化问题的一个局部最优解下面以一个简单例子说明设有第60页/共63页该问题的几何图形如图2.8所示从图上的目标函数等值线和不等式约束与等式约束的函数曲线可写出它的两个局部最优解 ，这是因为在 点邻域的任一满足约束的点 ，都有 同理，亦然第61页/共63页对某些约束优化问题，局部解可能有多个在所有的局部最优解中，目标函数值最小的那个解称为全局最优解在上例中，由于，所以全局最优解为由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解这与无约束优化问题是相同的第62页/共63页感谢您的观看！第63页/共63页