非线性规划.ppt

文档介绍：第1页运筹帷幄之中决胜千里之外运筹学课件非线性规划Non-linear Programming第2页非线性规划?基本概念?凸函数和凸规划?一维搜索方法?无约束最优化方法?约束最优化方法第3页基本概念?非线性规划问题?非线性规划方法概述第4页非线性规划问题例1曲线的最优拟合问题已知某物体的温度?与时间t之间有如下形式的经验函数关系:321???? (*)其中1c,2c,3c是待定参数。现通过测试获得n组?与t之间的实验数据),(iit?,i=1,2,…,n。试确定参数1c,2c,3c,使理论曲线(*)尽可能地与n个测试点),(iit?拟合。t??????n1i221)]([?第5页例2 构件容积问题设计一个右图所示的由圆锥和圆柱面围成的构件,要求构件的表面积为S,圆锥部分的高h和圆柱部分的高x2之比为a。确定构件尺寸,使其容积最大。x1x2x3???????????????0,02..)3/1(max212121222211221xxSxxxxaxxtsxxaV????第6页数学规划设nTnRxxx??),...,(1,RRqjxhpixgxfnji?:,...,1),(;,...,1),();(??,如下的数学模型称为数学规划(Mathematical Programming, MP):?????????qjxhpixgtsxfji,...,1,0)(,...,1,0)(..)(min????????????????qjxhpixgRxXjin,...,1,0)(,...,1,0)(约束集或可行域Xx??MP的可行解或可行点第7页向量化表示令Tpxgxgxg))(),...,(()(1?Tpxhxhxh))(),...,(()(1?,其中,qnpnRRhRRg??:,:,那么(MP)可简记为???????0)(0..)(minxhg(x)tsxf或者)(minxfXx?当p=0,q=0时,称为无约束非线性规划或者无约束最优化问题。否则,称为约束非线性规划或者约束最优化问题。(MP),若Xx?*,并且有X),()(*???xxfxf则称*x是(MP)的整体最优解或整体极小点,称)(*xf是(MP)的整体最优值或整体极小值。如果有**),()(xxX,xxfxf????则称*x是(MP)的严格整体最优解或严格整体极小点,称)(*xf是(MP)的严格整体最优值或严格整体极小值。定义 (MP),若Xx?*,并且存在*x的一个领域??),0()(**RxxRxxNn??????????,使?XxNxxfxf)(),()(**????,则称*x是(MP)的局部最优解或局部极小点,称)(*xf是(MP)的局部最优值或局部极小点。如果有?***,)(),()(xxXxNxxfxf?????,则称*x是(MP)的严格局部最优解或严格局部极小点,称)(*xf是(MP)的严格局部最优值或严格局部极小点。第9页非线性规划方法概述定义 ,,,:???pRpRxRRfnnn?,若存在0??,使),0(),()(?????txftpxf则称向量p是函数f(x)在点x处的下降方向。定义 ,,,????pRpXxRXnn,若存在0?t,使Xtpx??则称向量p是函数f(x)在点x处关于X的可行方向。第10页非线性规划基本迭代格式第1步选取初始点0x,k:=0;第2步构造搜索方向kp;第3步根据kp,确定步长kt;第4步令kkkkptxx???1,若1?kx已满足某种终止条件,停止迭代,输出近似解1?kx;否则令k:=k+1,转回第2步。