约束优化的数学基础.ppt

约束优化的数学基础,本章内容,优化问题分单变量和多变量，有约束和无约束，线性和非线性问题。 无约束优化就是数学上的无条件极值，约束优化就是数学上的条件极值。 我们常见的是非线性规划问题。 本章是回顾相关的数学基础，讨论约束最优化的条件等问题,多元函数的极小值充分必要条件,正定,约束优化的模型：,第一节 等式约束优化的极值条件,求解等式约束优化问题：,需要导出极值存在的条件，这是求解等式约束优化问题的理论基础。对这一问题在数学上有两种处理方法：消元法（降维法）和拉格朗日乘子法（升维法），现分别予以介绍。,为了便于理解，先讨论二元函数只有一个等式约束的简单情况，即 从约束条件得 带入目标函数可消去一个变量,消元法（降维法）,消元法（降维法）,对于n维情况,由 个约束方程将n个变量中的前 个变量用其余 个变量表示，即有： 带入目标函数可以 消去 个设计变量,拉格朗日乘子法,拉格朗日乘子法通过增加变量将等式约束优化问题变成无约束优化问题，所以又称升维法。,可以通过其中的前l个方程,但 应是任意的量，则应有,综合起来即为： 再加上等式约束 就是无约束优化问题 F 的极值条件：,设 ，目标函数是 ，约束条件是 的 个等式约束方程。为了求出 的可能的极值点 ，引入非零拉格朗日乘子 ，并构成一个新的目标函数,第二节 不等式约束优化 的极值条件,工程上大多数问题都是不等式约束优化问题. 一元函数在一定区间的优化问题:,引入松弛变量,得到拉格朗日方程 -,分析 可知，此时不是 ，就是 。当 时， ，约束起作用，即为 的情况。当 时， ，约束不起作用，即为 的情况。这个分析结果可表示为,这说明对于 和 ，二者至少必有一个需要取零值，因此可将 的条件写成 。,可将 的条件写成 。,分析极值点 在区间 中所处的位置，将会出现三种可能的情况：,1）当 时，因为此时 ，则极值条件为,2）当 时，因为此时 ，则极值条件为 ，即 。,3）当 时，因为此时 ，则极值条件为 ，即 。,这和如下图所示的从几何概念分析的结果完全一致。,三个极值条件的几何表示,第六节 库恩塔克条件,将上述一元函数推广到多元函数，可以得到著名的库恩塔克条件,可以得到拉格朗日函数,（其中设计变量 为n维向量，它受到有m个不等式约束的限制）,拉格朗日函数的极值条件,从一元函数类推可以得到库恩塔克条件,即： 库恩-塔克条件的几何意义是：在约束极小点处函数的负梯度一定能够表示成所有起作用的约束在该点梯度的非负线性组合。,令J表示起作用的约束下标集合，则库恩塔克条件为：,图2-12 两个起作用的约束,图2-13 库恩塔克条件的几何意义,a）负梯度位于锥角区之内 b）负梯度位于锥角区之外,K-T条件关于仅含不等式约束的二维问题的几何解释,作业： 1、 min f(x,y)=4x*x+5y*y s.t. h(x,y)=2x+3y-6=0 使用消元法求解 2、使用拉格朗日乘子法求解上面问题 3、用K-T条件求证 min f(x,y)=(x-7)*(x-7)+(y-3)*(y-3) s.t. g1(x,y)=x*x+y*y-10=0 g2(x,y)=x+y-4=0 g3(x,y)=-y=0 在点(3,1)处是否为极值点,作业： 4、 max f(x,y)=8x+12y-x*x-y*y s.t. g1