2-2优化方法数学基础.ppt

2 优化方法数学基础优化方法数学基础 优化设计优化设计极值极值 多变量、多约束非线性优化多变量、多约束非线性优化 高等数学极值理论是求解基础，但是不能直接高等数学极值理论是求解基础，但是不能直接求出最优解。求出最优解。对多变量约束优化问题的求解方法所涉及的数对多变量约束优化问题的求解方法所涉及的数学概念及有关理论进行补充和扩展。学概念及有关理论进行补充和扩展。介绍二次函数、多元函数的梯度、函数的近似介绍二次函数、多元函数的梯度、函数的近似表示以及极值条件和数值迭代解法等基本概念。表示以及极值条件和数值迭代解法等基本概念。一、正定二次型一、正定二次型二次函数二次函数 XTHX二次型，二次型，H二次型矩阵二次型矩阵 正定和负定矩阵。对于所有非零向量正定和负定矩阵。对于所有非零向量 XTHX 0，矩阵正定矩阵正定 XTHX=0，矩阵半正定矩阵半正定 XTHX 0，矩阵负定矩阵负定 XTHX=0，矩阵半负定矩阵半负定 XTHX=0，矩阵不定矩阵不定写成向量形式写成向量形式一、正定二次型一、正定二次型 线性代数可知，矩阵线性代数可知，矩阵H的正定性除用定义判断外，还可的正定性除用定义判断外，还可以用矩阵的各阶主子式进行判别以用矩阵的各阶主子式进行判别 主子式主子式包含第一个元素在内的左上角各阶子矩阵所包含第一个元素在内的左上角各阶子矩阵所对应的行列式。对应的行列式。奇数阶主子式奇数阶主子式0，矩阵，矩阵H负定。负定。矩阵矩阵H正定正定如果矩阵的各阶主子式均大于零，即如果矩阵的各阶主子式均大于零，即n阶主子式阶主子式 一、正定二次型一、正定二次型 二次型矩阵二次型矩阵H正定正定正定二次函数。正定二次函数。正定二次函数正定二次函数性质：性质：正定二次函数的等值线或等值面是一族同心椭圆正定二次函数的等值线或等值面是一族同心椭圆(或同心椭球或同心椭球)。椭圆族椭圆族或椭球族的中心是极小点。或椭球族的中心是极小点。函数椭圆族等值线与一组平行线切点的连线通过函数椭圆族等值线与一组平行线切点的连线通过椭圆中心；椭圆中心；反之，过椭圆中心的直线与各椭圆的交点所反之，过椭圆中心的直线与各椭圆的交点所作椭圆的切线是一组平行线。作椭圆的切线是一组平行线。非正定二次函数非正定二次函数在极小点附近的等值线或等值面近似在极小点附近的等值线或等值面近似于椭圆或椭球。于椭圆或椭球。求极值时，近似按二次函数处理，即用二次函数的极求极值时，近似按二次函数处理，即用二次函数的极小点近似函数的极小点，反复进行，逐渐逼近函数的极小点近似函数的极小点，反复进行，逐渐逼近函数的极小点。小点。一、正定二次型一、正定二次型二、方向导数和梯度二、方向导数和梯度 1方向导数方向导数 导数是描述函数变化率的数学量。导数是描述函数变化率的数学量。微分理论微分理论知，一元函数在点知，一元函数在点xk的一阶导数表示函数在的一阶导数表示函数在该点的变化率。该点的变化率。二元函数在某点沿坐标方向二元函数在某点沿坐标方向xi的变化率用函数对该坐标的变化率用函数对该坐标变量的一阶偏导数表示。变量的一阶偏导数表示。二、方向导数和梯度二、方向导数和梯度 函数沿任一方向的变化率，用方向导数描述。函数沿任一方向的变化率，用方向导数描述。二元函数在二元函数在X（k）处沿与坐标轴夹角为处沿与坐标轴夹角为 i的的 S方向的变化方向的变化率，即方向导数率，即方向导数二、方向导数和梯度二、方向导数和梯度二、方向导数和梯度二、方向导数和梯度 多元函数在多元函数在X（k）处方向导数处方向导数 梯度梯度；方向；方向S上的单位向量；上的单位向量；S的方向角；的方向角；S的方的方向余弦向余弦2梯度梯度 函数在点函数在点X（k）的梯度是由函数在该点的一阶偏导数组的梯度是由函数在该点的一阶偏导数组成的向量成的向量。根据矢量代数根据矢量代数2梯度梯度 函数在某点沿方向函数在某点沿方向S的的方向导数方向导数等于等于 该点的梯该点的梯度在方向度在方向S上的投影。上的投影。函数梯度性质函数梯度性质 (1)梯度方向是函数等值线梯度方向是函数等值线(或等值面或等值面)的法线方向的法线方向 当当S方向与该点的梯度相方向与该点的梯度相垂直垂直时，函数在该点沿时，函数在该点沿S的方向的方向导数等于零。导数等于零。说明方向位于该点等值线说明方向位于该点等值线的切线上的切线上(或等值面的切平或等值面的切平面内面内)函数在该点的梯度函数在该点的梯度方向必定是该点等值线或等方向必定是该点等值线或等值面的法线方向。值面的法线方向。函数梯度性质函数梯度性质 (2)(负负)梯度方向是函数值梯度方向是函数值(下降下降)增长最快的方向增长最快的方向 当当S方向与梯度夹角为零时，方向导数达到最大值方向与梯度夹角为零时，方向导数达到最大值 函数在一点的梯度方向是该点方向导数最大的方向函数在一点的梯度方向是该点方向导数最大的方向(函函数值增长最快的方向数值增长最快的方向)；与梯度相反的方向称为与梯度相反的方向称为负梯度方向负梯度方向 。函数在一点的负。函数在一点的负梯度方向是该点函数值下降最快的方向。梯度方向是该点函数值下降最快的方向。与梯度成锐角的方向是函数值上升的方向，与梯度成钝与梯度成锐角的方向是函数值上升的方向，与梯度成钝角的方向是函数值下降的方向。角的方向是函数值下降的方向。函数梯度性质函数梯度性质(3)各点函数梯度不同。各点函数梯度不同。梯度大小就是梯度的模长。梯度大小就是梯度的模长。(4)梯度是函数在一点邻域内局部性态的描述。梯度是函数在一点邻域内局部性态的描述。(5)极值点处梯度为零极值点处梯度为零 梯度为零不一定是极值点。梯度为零不一定是极值点。x2x1.函数梯度函数梯度例例 求函数求函数f(X)=(x1-2)2+(x2-1)2在点在点X(1)=3,2T和和X(2)=2,2T处的梯度并作图表示。处的梯度并作图表示。解解 梯度梯度三、多元函数的近似表示三、多元函数的近似表示 一元函数在点一元函数在点xk的邻域内的邻域内n阶可导，可在该点的邻域内阶可导，可在该点的邻域内泰勒展开泰勒展开 多元函数若在点多元函数若在点X（k）作泰勒展开，展开式一般取三项，作泰勒展开，展开式一般取三项，形式与一元函数展开式的前三项相似，即形式与一元函数展开式的前三项相似，即三、多元函数的近似表示三、多元函数的近似表示二阶导数矩阵二阶导数矩阵海赛海赛(Hessian)矩阵，矩阵，n阶对称矩阵阶对称矩阵 取泰勒展开式的前两项，得到泰勒线性近似式取泰勒展开式的前两项，得到泰勒线性近似式 例例 用泰勒展开函数用泰勒展开函数f(X)=x13-x23+3x12+3x22-9x1，在在点点X(1)=1,1T简化成线性函数和二次函数。简化成线性函数和二次函数。三、多元函数的近似表示三、多元函数的近似表示解解 函数在点函数在点X(1)的函数值、梯度和二阶导数矩阵的函数值、梯度和二阶导数矩阵三、多元函数的近似表示三、多元函数的近似表示简化线性函数简化线性函数简化二次函数简化二次函数 将将X(1)代入简化所得的线性函数和二次函数中，其函数代入简化所得的线性函数和二次函数中，其函数值等于值等于-3，与原函数在点，与原函数在点X(1)的值相等，说明简化正确。的值相等，说明简化正确。四、函数的极值四、函数的极值 无约束优化问题的极值只取决于目标函数本身性态，无约束优化问题的极值只取决于目标函数本身性态，约束优化问题的极值不仅与目标函数的性态有关，且与约束优化问题的极值不仅与目标函数的性态有关，且与约束函数的构成相关。约束函数的构成相关。(一一)无约束问题极值条件无约束问题极值条件 高等数学高等数学知，一元函数在点知，一元函数在点xk 取得极值：取得极值：必要条件是函数在该点的一阶导数等于零，充分条件必要条件是函数在该点的一阶导数等于零，充分条件是二阶导数不等于零。是二阶导数不等于零。四、函数的极值四、函数的极值 多元函数在点多元函数在点X(k)取得极值的取得极值的必要条件：必要条件：函数在该点的所有方向导数等于零函数在该点的所有方向导数等于零函数在该点的函数在该点的梯度等于零。梯度等于零。多元函数在点多元函数在点X(k)取得取得极小值条件：极小值条件：函数在该点的梯度为零，二阶导数矩阵为正定函数在该点的梯度为零，二阶导数矩阵为正定展开成泰勒二次近似式展开成泰勒二次近似式四、函数的极值四、函数的极值例例 求函数求函数f(X)=x12+x1x2+x22-6x1-3x2的极值的极值。解解 联立求解得驻点联立求解得驻点X*=3，0T海赛矩阵正定，严格极小点。海赛矩阵正定，严格极小点。(二二)约束问题极值条件约束问题极值条件(后述后述)五、数值迭代算法五、数值迭代算法 最优化方法最优化方法基本思想基本思想 消去法和爬山法消去法和爬山法 消去法消去法处理单变量函数极值问题时有效处理单变量函数极值问题时有效 对于多维函数，消去的不是线段，而是平面对于多维函数，消去的不是线段，而是平面(两变量两变量函数函数)、立体、立体(三变量函数三变量函数)或多维空间的一部分，使求或多维空间的一部分，使求解问题变得复杂解问题变得复杂 爬山法爬山法上山或下山上山或下山 极大值极大值上升算法；极小值上升算法；极小值下将算法下将算法 每前进一步，函数值有所改善，同时为下一步移每前进一步，函数值有所改善，同时为下一步移动方向提供有用信息动方向提供有用信息数值迭代算法基本思想。数值迭代算法基本思想。五、数值迭代算法五、数值迭代算法 按照某一迭代格式，从一个初始点按照某一迭代格式，从一个初始点X(0)出发逐步产生出发逐步产生一个点列一个点列 X(0)，X(1)，X(k)，X(k+1)，点列所对应的目标函数值呈下降趋势，构成此点列的点列所对应的目标函数值呈下降趋势，构成此点列的方法就是下降迭代算法。方法就是下降迭代算法。点列的极限就是点列的极限就是目标函数的极小点目标函数的极小点x2x11下降迭代算法基本格式下降迭代算法基本格式迭代点列递推方法迭代点列递推方法 为使每一次迭代都能让目标函数获得最大的下降量，新为使每一次迭代都能让目标函数获得最大的下降量，新的迭代点的迭代点X(k+1)通常取作方向通常取作方向S(k)上的一维极小点，对应的上的一维极小点，对应的步长记作步长记作 k，称最优步长因子。称最优步长因子。下降迭代算法基本格式：下降迭代算法基本格式：给定初始点给定初始点X(k)和收敛精度和收敛精度；选取搜索方向选取搜索方向S(k)；确定步长因子确定步长因子 k，得到迭代点得到迭代点X(k+1)；收敛判断：若满足收敛精度，以收敛判断：若满足收敛精度，以X(k+1)作为最优点，作为最优点，终止计算；否则，以终止计算；否则，以X(k+1)作为新起点，转作为新起点，转进行下一轮进行下一轮迭代。迭代。1下降迭代算法基本格式下降迭代算法基本格式 下降迭代算法的构成需要解决下降迭代算法的构成需要解决基本问题：基本问题：选择搜索方向选择搜索方向 不同的搜索方向，构成不同的搜索方向，构成不同的下降迭代算法；不同的下降迭代算法；确定步长因子确定步长因子 一般通过一维搜索法取一般通过一维搜索法取得最优步长因子；得最优步长因子；给定收敛准则给定收敛准则 用以判断迭代点是否能用以判断迭代点是否能够作为近似的最优点。够作为近似的最优点。2收敛准则收敛准则 判断迭代点与精确解近似程度的方法判断迭代点与精确解近似程度的方法收敛准则。收敛准则。(1)点距准则点距准则(坐标准则坐标准则)一般来说，迭代点向极小点的逼近速度是逐近变慢的，一般来说，迭代点向极小点的逼近速度是逐近变慢的，越接近极小点，相邻迭代点间的距离越短。当相邻两迭代越接近极小点，相邻迭代点间的距离越短。当相邻两迭代点间的距离充分小，即有点间的距离充分小，即有 (2)函数值准则函数值准则 迭代点接近极小点，迭代点距离接近，函数值也越接近。迭代点接近极小点，迭代点距离接近，函数值也越接近。将相邻的函数值之差作为判断极小点的准则将相邻的函数值之差作为判断极小点的准则函数值准函数值准则。则。2收敛准则收敛准则 (2)函数值准则函数值准则 2收敛准则收敛准则 (3)梯度准则梯度准则 梯度等于零的点是极小点，梯度近似于零的点则必定是梯度等于零的点是极小点，梯度近似于零的点则必定是近似极小点。当近似极小点。当准则选用：准则选用：优化方法、函数性态。优化方法、函数性态。3算法的收敛性算法的收敛性点列向极小点逼近的速度点列向极小点逼近的速度算法的收敛速度算法的收敛速度算法的收敛性和收敛速度定义算法的收敛性和收敛速度定义 p点列点列 的收敛阶，正实数；的收敛阶，正实数；q 收敛比收敛比 对于与迭代次数对于与迭代次数k无关的常数无关的常数 q(0,1)，如果存在如果存在一个大于零的数一个大于零的数p使公式成立，则使公式成立，则 p=1，线性收敛性，线性收敛性(线性收敛速度线性收敛速度)；p=2，二次收敛性；，二次收敛性；1p 2，超线性收敛性，超线性收敛性。3算法的收敛性算法的收敛性 算法的收敛性也可以根据算法对二次函数的求解能算法的收敛性也可以根据算法对二次函数的求解能力加以判断。力加以判断。对于正定二次函数，如果算法能在有限次迭代中得对于正定二次函数，如果算法能在有限次迭代中得到极小点，称此算法具有二阶收敛性。到极小点，称此算法具有二阶收敛性。解题所需迭代计算过程的长短，主要取决于：解题所需迭代计算过程的长短，主要取决于：问题的性态；问题的性态；所用的优化方法；所用的优化方法；终止准则和收敛精度。终止准则和收敛精度。从工程实际出发，采用适当终止准则和收敛精度从工程实际出发，采用适当终止准则和收敛精度