资源描述：
《非线性规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹帷幄之中决胜千里之外运筹学课件非线性规划Non-linearProgramming非线性规划基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法基本概念非线性规划问题非线性规划方法概述非线性规划问题例1曲线的最优拟合问题例2构件容积问题数学规划约束集或可行域MP的可行解或可行点向量化表示当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。最优解和极小点非线性规划方法概述非线性规划基本迭代格式凸函数和凸规划凸函数及其性质凸规划及其性质凸
2、函数及其性质凸规划及其性质约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。定理4.2.6凸规划的任一局部最优解都是它的整体最优解。解：（1）目标函数是不是凸函数？（2）gi(x)是不是凸函数？退出前一页后一页一维搜索问题的算法分类：精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）本节内容：两种精确一维搜索方法：0.618法，Newton法。两种非精确一维搜索方法：Goldstein法,Armijo法。退出前一页后一页1、0.6
3、18法（近似黄金分割法）问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？单谷函数退出前一页后一页搜索法求解：或基本过程：给出[a,b],使得t*在[a,b]中。[a,b]称为搜索区间。迭代缩短[a,b]的长度。当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。退出前一页后一页假定：已经确定了单谷区间[a,b]t1t2ababt1t2新搜索区间为[a,t2]新搜索区间为[t1,b]退出前一页后一页区间缩小比例的确定：区间缩短比例为(t2
4、-a)/(b-a)缩短比例为(b-t1)/(b-a)缩短比例满足：每次插入搜索点使得两个区间[a,t2]和[t1,b]相等；每次迭代都以相等的比例缩小区间。0.618法t1t2ababt1t2退出前一页后一页确定[a,b],计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：是否是停止，输出t1否以[a,t2]为新的搜索区间是停止，输出t2否以[t1,b]为新的搜索区间退出前一页后一页例：解：t1t230t1、第一轮：t1=1.146,t2=1.854t2－0
5、>0.5退出前一页后一页2、第二轮：t2=1.146,t1=0.708t2－0=1.146>0.53、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.438>0.51.8540tt2t11.4160tt2t1退出前一页后一页4、第四轮：t2=0.876,t1=0.708b-t1=1.146-0.708<0.5输出：t*=t2=0.876为最优解，最优值为-0.0798课下练习：参阅110页表格仔细分析上述迭代过程，体会0.618法的实质。01.416tt1t2退出前一页后一页2、Ne
6、wton法Newton法基本思想：用探索点tk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。退出前一页后一页解题步骤：给定初始点t1和精度是是停止，输出t1是否停止，解题失败否停止，输出t2否退出前一页后一页例：解：取t1=1,计算：迭代过程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退出前一页后一页3、非精确一维搜索法数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和
7、步长如果已经确定了搜索方向pk,则只要确定一个最佳的步长即可。所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。这样的搜索方法称之为非精确一维搜索方法退出前一页后一页Goldstein法原理：yt0bcdaY=(0)+´(0)tY=(0)+m2´(0)tY=(0)+m1´(0)t退出前一页后一页是Goldstein算法确定m1,m2,α,t0,a=0,b=+∞(t0)≤(0
8、)+m1’(0)t0(t0)≥(0)+m2’(0)t0是停止,输出t0否a=a,b=t0,t1=(a+b)/2否a=t0,b=b,t1=(a+b)/2(若b=+∞,则t1=αa)退出前一页后一页Goldstein法步骤Armijo法无约束最优化方法无约束问题的最优性条件最速下降法共轭方向法无约束问题的最优化条件1、无约束问题的最优性条件定理1定理2梯度为0的点称为函数的驻点。驻点可能是极小点，也可能是极大点，也可能即不是极大也不
