优化方法的数学基础ppt课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 优化方法的数学基础,2.1,方向导数与梯度,1,、方向导数,二元函数,(,定义可微,),在点,x,0,处沿某一方向,S,的方向导数,第2章 优化方法的数学基础2.1 方向导数与梯度,第,2,章 优化方法的数学基础,2.1,方向导数与梯度,第2章 优化方法的数学基础2.1 方向导数与梯度,第,2,章 优化方法的数学基础,2.1,方向导数与梯度,三元函数,:,第2章 优化方法的数学基础2.1 方向导数与梯度,n,元函数在点,x,0,处沿,S,方向的方向导数,上式表明了方向导数与偏导数之间的数量关系,方向导数是偏导数概念的推广,方向导数表明了函数,f(X),在点,X,(0),沿,S,方向的,变化率,，它是一个,标量,+,函数,f(X),在,X,(0),点处沿,S,方向是,增加,的,-,函数,f(X),在,X,(0),点处沿,S,方向是,减小,的,优化方法的数学基础ppt课件,2,、梯度,二元函数的梯度,为函数,f,(,x,1,，,x,2,),在,x,0,点处的,梯度,2、梯度二元函数的梯度 为函数f(x1，x2)在x0点处的梯,梯度的模：,设,梯度方向和,S,方向重合时，方向导数值最大。,梯度的模：设梯度方向和S 方向重合时，方向导数值最大。,梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值,。,梯度方向与等值线的关系,设：,则有,为单位方向向量。,梯度方向是函数值变化最快的方向，而梯度的模就是函数,多元函数的梯度,多元函数的梯度,梯度 模：,函数的梯度方向与函数等值面相垂直，也就是和等值面上过,x,0,的一切曲线相垂直。,由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。,优化方法的数学基础ppt课件,例题,2-1,求函数 在点,3,2,T,、,2,0,T,的梯度,解,在点,x,(1),=,3,2,T,处的梯度为：,例题2-1求函数,在点,x,(1),=,3,2,T,处的梯度为：,在点,x,(2),=,2,0,T,处的梯度为：,若函数在某点取得极值，,则该点的所有一阶偏导数,必定为零，即梯度为零,在点x(1)=3,2T处的梯度为：,例题,2-2,一般,n,元二次函数的矩阵式为,其中,C,为常数，求梯度,f,(X),。,解：,将二元二次函数矩阵式展开,例题2-2一般n元二次函数的矩阵式为,若,推广到,n,元二次函数，则一般,n,元二次函数梯度,的矩阵表达式为,若推广到n元二次函数，则一般n元二次函数梯度,2.2,多元函数的泰勒展开及海森矩阵,复杂函数,的极值问题，常用,泰勒展开式,得到,目标函数在所讨论点的近似表达式,，最常用的是,线性近似和二次近似,n,元函数在某点,(,至少二阶可导,),展开到二次项,写成矩阵形式,2.2 多元函数的泰勒展开及海森矩阵 复杂函数的极值,f,(X),的二阶导数矩阵，称为,f,(X),的海森,(Hessian),矩,阵，海森矩阵是一个,nXn,的对称矩阵，常用,H(X),表示,例题,用泰勒展开将函数,在点,简化成线性函数与二次函数。,解：函数在点 的函数值、梯度和二阶导数矩阵：,例题 用泰勒展开将函数,简化的线性函数,简化的二次函数,简化的线性函数简化的二次函数,2.3,无约束优化问题的极值条件,1.,在 处取得极值，其必要条件是,:,即在极值点处函数的梯度为,n,维零向量。,为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。,根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。,2.3 无约束优化问题的极值条件 1.在 处,2,.,处取得极值充分条件,大于,0,+,大于,0,2.处取得极值充分条件大于0+大于0,2,.,处取得极值充分条件,即要求 各阶主子式均大于零。,2.处取得极值充分条件即要求,2,4,凸集、凸函数与凸规划,全局最优与局部最优,?,1,、凸集,几何特征是：,其任意两点连线上的一切点都位于这个集合内,24 凸集、凸函数与凸规划 全局最优与局部最优?,2,、凸函数,对凸集,D,内，任两点,X,(1),、,X,(2),及,0,1,f,(X),为,凸函数,几何意义为：,这两个点的连线完全处在,f,(X),曲线,(,曲面,),的,上方，或在,f,(X),曲线,(,曲面,),上,2、凸函数 对凸集D内，任两点X(1)、X(2)及0 0,凸规划,-,对非线性规划,f,(X),与,g(X),均为凸函数,凸规划,凸规划的局部极小点一定是全局极小点,判定一个函数的凸性，可利用以下性质：f(X)为一阶连续导数,2.5,不等式约束优化问题的极值条件,不等式约束的多元函数极值的必要条件是著名的库恩,-,塔克（,Kuhn-Tucker,）条件，它是非线性优化问题的重要理论,（,1,）库恩,塔克条件,(K-T,条件）,对于多元函数不等式的约束优化问题：,2.5 不等式约束优化问题的极值条件 不等式约束,库恩,塔克条件表明：如点 是函数 的极值点，要么 （此时 ）,要么目标函数的负剃度等于起作用约束梯度的非负线性组合（此时,）,K-T,条件,库恩塔克条件表明：如点 是函数 的极值,O,x,1,x,2,极值点处于等值线的中心,极值点处于两个约束曲线的交点上,x,g,1,(,x,),0,g,2,(,x,),0,g,3,(,x,),0,O,x,1,x,2,x,g,1,(,x,),0,g,2,(,x,),0,起作用约束：,Ox1x2极值点处于等值线的中心极值点处于两个约束曲线的交点,库恩,塔克条件的几何意义是,:,在约束极小值点 处，函数 的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。,x,1,x,2,O,g,2,(,x,)=0,g,1,(,x,)=0,f,(,x,)=,C,g,2,(,x,k,),g,1,(,x,k,),f,(,x,k,),x,k,可行域,点,x,k,处的切平面,x,1,x,2,O,g,2,(,x,)=0,g,1,(,x,)=0,f,(,x,)=,C,g,2,(,x,k,),g,1,(,x,k,),f,(,x,k,),x,k,可行域,点,x,k,处的切平面,(a),(b),库恩塔克条件的几何意义是:在约束极小值点 处，函数,同时具有等式和不等式约束的优化问题,:,K-T,条件：,同时具有等式和不等式约束的优化问题:K-T条件：,K-T,条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,例,1-6,库恩,塔克（,K-T,）条件应用举例,s.t,判断,1 0,T,是否为约束最优点。,K-T条件是多元函数取得约束极值的必要条件,以用来作,(1),当前点 为可行点，因满足约束条件,（,2,）在 起作用约束为,g,1,和,g,2,因,(3),各函数的梯度：,(1)当前点 为可行点，因满,（,4,）求拉格朗日乘子,由于拉格朗日乘子均为非负，说明,是一个局部最优点，因为它满足,K-T,条件。,（4）求拉格朗日乘子由于拉格朗日乘子均为非负，说明,s.t,s.t,