优化的数学基础市公开课金奖市赛课一等奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第二章 优化设计数学基础,第1页,第1页,本章内容,优化问题分单变量和多变量，有约束和无约束，线性和非线性问题。,无约束优化就是数学上无条件极值，约束优化就是数学上条件极值。,我们常见是非线性规划问题。,本章是回顾相关数学基础，讨论约束最优化条件等问题,第2页,第2页,第一节 多元导数方向导数与梯度,方向导数 一个二元函数在 处偏导数,第3页,第3页,图,2-1,二维空间中方向,第4页,第4页,一个二元函数在 处沿方向d导数,第5页,第5页,同理，三元函数方向导数,多元函数方向导数,第6页,第6页,图,2-2,三维空间中方向,第7页,第7页,二元函数梯度,二元函数梯度,称函数在 处梯度。,第8页,第8页,方向导数几种形式：,第9页,第9页,图,2-3,梯度方向与等值线关系,第10页,第10页,当在 平面内画出 等值 线,能够看出，在等值线切线方向d是函数改变率为零方向，即有,因此,第11页,第11页,作业：求二元函数,在 处函数改变率最大方向和数值。,第12页,第12页,多元函数梯度,第13页,第13页,d,方向上方向导数,第14页,第14页,为梯度 模。,为梯度方向单位向量，它与函数等值面 相垂直。,第15页,第15页,图,2-5,梯度方向与等值面关系,第16页,第16页,多元函数泰勒展开,一元函数 在 点处泰勒展开式为,其中,二元函数 在 点处泰勒展开式为,其中,第17页,第17页,第18页,第18页,其二阶偏导数矩阵,：,又称hession矩阵,第19页,第19页,作业 求二元函数,在 点处二阶泰勒展开式。,第20页,第20页,将二元函数泰勒展开式推广到多元函时，则 在 点处泰勒展开式矩阵形式为,其中,为函数 在 点处梯度,第21页,第21页,若将函数泰勒展开式只取到线性项，即取,则 是过 点和函数 所代表超曲面相切切平面。,第22页,第22页,第二节 无约束优化极值条件,对于二元函数 ，若在 点处取得极值，其必要条件是,为了判断从上述必要条件求得 是否是,第23页,第23页,极值点，需要建立极值充足条件。依据二元函数 在 点处泰勒展开式，考虑上述极值必要条件，有,设,则,第24页,第24页,即要求:,或表示为,第25页,第25页,该条件反应了函数在 处各阶主子式不小于0,第26页,第26页,多元函数极值充足条件,正定,第27页,第27页,函数极小点和最小点,第三节 凸集、凸函数与凸规划,图,2-7,下凸一元函数,第28页,第28页,凸集,一个点集（或区域），假如连结其中任意两点 和 线段所有包括在该集合内，就成该点集为凸集，不然称非凸集,。凸集概念能够用数学语言简练地表示为：假如对一切 ，及一切满足 实数 ，点 ，则称集合 为凸集。凸集既能够是有界，也能够是无界。n维空间中 维子空间也是凸集（比如三维空间中平面）。,第29页,第29页,图,2-8,凸集与非凸集,第30页,第30页,凸集含有下列性质：,（,1,）若,A是一个凸集，是一个实数，是凸集A中动点，即 ，则集合,还是凸集,（,2,）若,A和B是凸集，,、分别是凸集,A,、,B中动点，即 ，则集合,还是凸集。,（,3,）任何一组凸集交集还是凸集。,第31页,第31页,这三个性质如图,所表示,凸集性质,第32页,第32页,凸函数,函数 假如在连接其凸集定义域内任意两点 、线段上，函数值总小于或等于用 及 作线性内插所得值，那么称 为凸函数。用数学语言表示为,第33页,第33页,凸函数定义,第34页,第34页,下面给出凸函数一些简朴性质：,设 为定义在凸集 上一个凸函数，对任意实数 ，则函数 也是定义在 上凸函数。,设 和 为定义在凸集 上两个凸函数，则其和 也是 上凸函数。,对任意两个整数 和 ，函数 也是在 上凸函数。,第35页,第35页,凸性函数,设 为定义在凸集 上，且含有连续一阶导数函数，则 在 上为凸函数充分必要条件是对凸集 内任意不同两点 、，不等式,这是依据函数一阶导数信息函数梯度 来判断函数凸性。也能够用二阶导数信息函数海塞矩阵 来判断函数凸性。,设 为定义在凸集 上且含有连续二阶导数函数，则 在 上为凸函数充足必要条件是海塞矩阵 在 上处处半正定。（证实从略）,恒成立。,第36页,第36页,凸规划,对于约束优化问题,若,都为凸函数，则称此问题,为凸规划。,凸规划有下列性质：,1）,若给定一点 ，则集合 为凸集。此性质表明，当 为二元函数时期等值线成大圈套小圈形式。,2）,可行域 为凸集。,3）,凸规划任何局部最优解就是全局最优解。,第37页,第37页,第四节 等式约束优化极值条件,求解等式约束优化问题：,需要导出极值存在条件，这是求解等式约束优化问题理论基础。对这一问题在数学上有两种处理办法：消元法（降维法）和拉格朗日乘子法（升维法），现分别予以简介。,第38页,第38页,消元法,为了便于理解，先讨论二元函数只有一个等式约束简朴情况，即,对于,n,维情况,由 个约束方程将,n,个变量中前 个变量用其余 个变量表示，即有,第39页,第39页,拉格朗日乘子法,拉格朗日乘子法是求解等式约束优化问题另一个典型办法，它是通过增长变量将等式约束优化问题变成无约束优化问题。因此又称升维法。,对于含有 个等式约束,N维优化问题,在极值点 处有,第40页,第40页,把 个等式约束给出 个 分别乘以,待定系数 再和 相加，得,（2-10）,能够通过其中 个方程,（2-11）,来求解 个 ，使得 个变量微分 系数所有为零。这样式,（2-10）等号左边就只剩余,个变量微分 项，即它变为,（2-12）,第41页,第41页,但 应是任意量，则应有,（2-13）,式（,2-11,）和式（,2-13,）及等式约束 就是点 达到约束极值必要条件。,第42页,第42页,设 ，目的函数是 ，约束条件是 个等式约束方程。为了求出 也许极值点 ，引入拉格朗日乘子 ，并构成一个新目的函数,第43页,第43页,第五节 不等式约束优化极值条件,工程上大多数问题都是不等式约束优化问题.,一元函数在一定区间优化问题:,引入松弛变量,第44页,第44页,得到拉格朗日方程,第45页,第45页,分析 可知，此时不是 ，就是 。当 时，约束起作用，即为 情况。当 时，约束不起作用，即为 情况。这个分析结果可表示为,这阐明对于 和 ，两者至少必有一个需要取零值，因此可将 条件写成 。,可将 条件写成 。,第46页,第46页,分析极值点 在区间 中所处位置，将会出现三种也许情况：,1）,当 时，由于此时 ，则极值条件为,2）,当 时，由于此时 ，则极值条件为 ，即 。,3）,当 时，由于此时 ，则极值条件为 ，即 。,第47页,第47页,这和以下图所表示从几何概念分析结果完全一致。,三个极值条件几何表示,第48页,第48页,第六节 库恩塔克条件,将上述一元函数推广到多元函数，能够得到著名库恩塔克条件,能够得到拉格朗日函数,（其中设计变量 为,n,维向量，它受到有,m,个不等式约束限制）,第49页,第49页,拉格朗日函数极值条件,从一元函数类推能够得到库恩塔克条件,第50页,第50页,库恩-塔克条件几何意义是：在约束极小点处函数负梯度一定能够表示成所有起作用约束在该点梯度非负线性组合。,第51页,第51页,图,2-12,两个起作用约束,第52页,第52页,图,2-13,库恩塔克条件几何意义,a）,负梯度位于锥角区之内,b）,负梯度位于锥角区之外,第53页,第53页,K-T,条件关于仅含不等式约束二维问题几何解释,第54页,第54页,