资源描述
运运 筹筹 学学运运 筹筹 学学第五章第五章 非线性规划的基本概念非线性规划的基本概念 和基本原理和基本原理一一.数学模型数学模型1.基本概念基本概念非线性规划定义：非线性规划定义：如果如果目标函数目标函数或或约束条件约束条件中包含有非线性函数，就称中包含有非线性函数，就称这种规划问题为非线性规划问题。这种规划问题为非线性规划问题。非线性规划的数学模型举例：非线性规划的数学模型举例：Max f（X）=x1 S.t.(x2-2)+(x1-1)30 (x1-1)3-(x2-2)0Min f(X)=2x12-4x1x2+4x22-6x1-3x2 S.t.x1+x23 4x1+x20其中其中,x=(x1,x2,xn)T是是n维欧氏空间维欧氏空间En中的向量（点），中的向量（点），f(X)为目标为目标函数，函数，gi(X)0和和hj(x)=0为约束条件。为约束条件。非线性规划一般模型：非线性规划一般模型：其他情况：其他情况：由于由于max f(X)=-min-f(X)，当需使目标函数极大化时，只需使其负值极小，当需使目标函数极大化时，只需使其负值极小 化即可。因而仅考虑极小化无损一般性。化即可。因而仅考虑极小化无损一般性。若某约束条件是若某约束条件是“”的形式。的形式。1）局部极值和全局极值）局部极值和全局极值2）梯度）梯度3）梯度性质）梯度性质 梯度方向是函数值增加最快的方向，而负梯度梯度方向是函数值增加最快的方向，而负梯度方向则是函数值减少最快的方向。方向则是函数值减少最快的方向。4）海赛（）海赛（Hesse)矩阵矩阵例1 对于数学规划（对于数学规划（MP），若），若 ，并且有，并且有极值问题极值问题如果有如果有定义定义:8定理定理极值点存在的条件极值点存在的条件数值方法的基本思路：迭代数值方法的基本思路：迭代给定初始点给定初始点x0根据根据x0,依次迭代产生点列依次迭代产生点列xkxk的最后一点为最优解的最后一点为最优解xk有限有限xk无限无限xk收敛于最优解收敛于最优解 非线性规划方法概述非线性规划方法概述定义：下降方向定义：下降方向下降迭代算法小结下降迭代算法小结下降迭代算法大致由下述步骤组成下降迭代算法大致由下述步骤组成:1 选择初始点选择初始点 ,要求越接近最优解越好要求越接近最优解越好,2 寻找可行下降方向寻找可行下降方向 ,3 选取步长选取步长 ,4 迭代迭代:5 终止条件终止条件:)(kp运运 筹筹 学学运运 筹筹 学学第六章第六章 单变量函数的寻优方法单变量函数的寻优方法基本过程：基本过程：1.1.给出给出a,b,a,b,使得使得t t*在在a,ba,b中。中。a,ba,b称为搜称为搜索区间。索区间。2.2.迭代缩短迭代缩短a,ba,b的长度。的长度。3.3.当当a,ba,b的长度小于某个预设的值，或者导的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。数的绝对值小于某个预设的正数，则迭代终止。消去区间法消去区间法为单峰函数,即在区间上有唯一极小点缩小搜索区间一般遵循的原则去坏留好.对称等比收缩1等间隔分割法消去区间后,区间缩小为原来区间长度的2/3二二.0.618法（黄金分割法）法（黄金分割法）等间隔分割法特点:算法简单,计算次数多,这是因为每分割一次要进行两次函数值计算,采用黄金分割法,则每次分割只需计算一次函数值收缩比0.618的由来?三.Fibonaoci法Fibonaoci 数列Fibonaoci 分数数列为整数序列前后两项之比性质:黄金分割法是Fibonacci法的简单形式这是因为:当Fibonacci数列中运运 筹筹 学学运运 筹筹 学学第七章第七章 无约束条件下多变量函数无约束条件下多变量函数 的寻优方法的寻优方法寻优方法的关键是确定寻优方向，然后确定在该方寻优方法的关键是确定寻优方向，然后确定在该方向上的最优步长（一维寻优）。寻优方向确定的不向上的最优步长（一维寻优）。寻优方向确定的不同，得到各种寻优方法。同，得到各种寻优方法。n元函数的无约束非线性规划问题：求解无约束极值问题通常使用迭代法，迭代法大体可分为两类：解析法：使用导数的方法，要用到函数的解析性质；直接法：无须考虑函数是否可导，直接使用函数值。关于梯度的复习：梯度是一个向量。n元函数f(x1,x2,xn)在某点x处的梯度为：梯度的方向与函数f的等值线的一个法线方向相同，从较低的等值线指向较高的等值线。梯度的方向就是函数f的值增加最快的方向，其相反方向就是函数值降低最快的方向。一.最速下降法梯度法又称为最速下降法，由Cauchy于1847年给出。是最为古老但又十分基本的一种方法。梯度法解决的是具有连续可微的目标函数的无约束极值问题。梯度法的基本思想：从当前点xk出发寻找使得目标函数下降最快的方向，即负梯度方向。优点：迭代过程简单，使用方便。最速下降法计算公式最速下降法计算公式确定下一个近似点：搜索方向：算法步骤:1)初始化:2)方向:3)收敛?若,则停.否则,转44)求最优步长,进行一维寻优5)令转2)解:例1:用最速下降法求的极小值,只迭代一次代入目标函数得：令继续迭代,计算可得说明：最速下降方法相邻的两个搜索方向是相互垂直的，即x1 x0垂直x1 x2；最速下降法的缺陷：迭代点越靠近最优解则目标函数下降的速度越慢；优点：迭代点列总是收敛的，而且计算过程简单。二.牛顿法一.算法原理作二次近似在牛顿法迭代公式改进牛顿法牛顿法计算公式牛顿法计算公式确定下一个近似点：搜索方向：例2:用牛顿法求的极小值,解:1)计算2)方向3)求最优步长代入目标函数得：令4)判断即为所求三.共轭梯度法共轭方向：设X和Y是n维欧氏空间的两个向量，A为nn对称正定阵，如果X和AY正交，即有就称X和Y关于共轭，或X和Y为共轭。当时，上述条件就是正交条件。所以，共轭概念实际上是正交概念的推广。定理 设A为nn对称正定阵，d(1),d(2),d(n)为共轭的非零向量，则这组向量线性无关。无约束极值的一个特殊情形是其中A为nn对称正定阵定理 设向量d(i)，i=0，1，2，n-1，为A共轭，则从任一点X(0)出发，相继以d(0),d(1),d(n-1)为搜索方向的下述算法经过n次一维搜索收敛于原问题的极小点X*.正定二次函数的共轭梯度法正定二次函数的共轭梯度法共轭方向法：搜索方向d(0),d(1),d(n-1)必须共轭；确定各近似极小点时按最优一维搜索进行。共轭梯度法是共轭方向法的一种，它的搜索方向是利用一维搜索所得极小点处的梯度生成的。共轭梯度法计算公式共轭梯度法计算公式共轭梯度法计算步骤（1）选取初始近似X(0)，给出允许误差0.（2）计算d(0)=-f(X(0)，计算X(1).（3）假定已得出X(k)和d(k)，则计算d(k+1)，X(k+1)：d(k+1)=-f(X(k+1)+kd(k)X(k+1)=X(k)+kd(k).（4）若停止计算，X(K+1)就是要求的近似解，否则转入第(3)步。例3:共轭梯度法求的极小值,解:1)计算2)利用最速下降法计算3)求共轭系数4)一维寻优,求最优步长写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits43谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal
展开阅读全文