优化的数学基础市公开课一等奖百校联赛特等奖课件.pptx

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