运筹学(非线性规划)

第1页运筹帷幄之中决胜千里之外运筹学课件非线性规划Non-linearProgramming第2页非线性规划基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法第3页基本概念非线性规划问题非线性规划方法概述第4页非线性规划问题例1曲线的最优拟合问题已知某物体的温度与时间t之间有如下形式的经验函数关系：tcetcc321(*)其中1c，2c，3c是待定参数。现通过测试获得n组与t之间的实验数据),(iit，i=1，2，…,n。试确定参数1c，2c，3c，使理论曲线(*)尽可能地与n个测试点),(iit拟合。tn1i221)]([min3itciietcc第5页例2构件容积问题设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积为S，圆锥部分的高h和圆柱部分的高x2之比为a。确定构件尺寸，使其容积最大。x1x2x30,02..)3/1(max212121222211221xxSxxxxaxxtsxxaV第6页数学规划设nTnRxxx),...,(1，RRqjxhpixgxfnji:,...,1),(;,...,1),();(,如下的数学模型称为数学规划(MathematicalProgramming,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时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。第8页最优解和极小点定义4.1.1对于非线性规划(MP)，若Xx*，并且有X),()(*xxfxf则称*x是(MP)的整体最优解或整体极小点，称)(*xf是(MP)的整体最优值或整体极小值。如果有**),()(xxX,xxfxf则称*x是(MP)的严格整体最优解或严格整体极小点，称)(*xf是(MP)的严格整体最优值或严格整体极小值。定义4.1.2对于非线性规划(MP)，若Xx*，并且存在*x的一个领域),0()(**RxxRxxNn，使XxNxxfxf)(),()(**，则称*x是(MP)的局部最优解或局部极小点，称)(*xf是(MP)的局部最优值或局部极小点。如果有***,)(),()(xxXxNxxfxf，则称*x是(MP)的严格局部最优解或严格局部极小点，称)(*xf是(MP)的严格局部最优值或严格局部极小点。第9页非线性规划方法概述定义4.1.3设0,,,:pRpRxRRfnnn，若存在0，使),0(),()(txftpxf则称向量p是函数f(x)在点x处的下降方向。定义4.1.4设0,,,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步。第11页凸函数和凸规划凸规划及其性质凸函数及其性质第12页凸函数及其性质定义4.2.1设nRS是非空凸集，RSf:，如果对任意的)1,0(有)()1()())1((2121xfxfxxf，Sxx21,则称f是S上的凸函数，或f在S上是凸的。如果对于任意的)1,0(有)()1()())1((2121xfxfxxf，21xx则称f是S上的严格凸函数，或f在S上是严格凸的。若-f是S上的（严格）凸函数，则称f是S上的（严格）凹函数，或f在S上是（严格）凹的。第13页定理4.2.1设nRS是非空凸集。（1）若RRfn:是S上的凸函数，0，则f是S上的凸函数；（2）若RRffn:,21都是S上的凸函数，则21ff是S上的凸函数。有限个凸函数的非负线性组合仍为凸函数。第14页定理4.2.2设nRS是非空凸集，RRfn:是凸函数，Rc，则集合cxfSxcfHS)(),(是凸集。我们称集合cxfSxcfHS)(),(为函数f在集合S上关于c的水平集。第15页定理4.2.3设nRS是非空开凸集，RSf:可微，则（1）f是S上的凸函数的充要条件是)()()()(12121xfxfxxxfT，Sxx21,其中Tnxxfxxfxf))(,....,)(()(1111是函数f在点1x处的一阶导数或梯度。（2）f是S上的严格凸函数的充要条件是)()()()(12121xfxfxxxfT，2121,,xxSxx函数凸性的判定（一阶条件）第16页定理4.2.4设nRS是非空开凸集，RSf:二阶连续可导，则f是S上的凸函数的充要条件是f的Hesse矩阵)(2xf在S上是半正定的。当)(2xf在S上是正定矩阵时，f是S上的严格凸函数。（注意：该逆命题不成立。）22221222222122122122122)()()(....)(...)()()(....)()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf函数凸性的判定（二阶条件）第17页凸规划及其性质qjxhpixgtsxfji,...10,)((MP),...,1,0)(..)(minqjxhpixgRxXjin,...,1,0)(,...,1,0)(约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。第18页定理4.2.5对于非线性规划(MP)，若pixgi,...,1),(皆为nR上的凸函数，qjxhj,...,1),(皆为线性函数，并且f是X上的凸函数，则(MP)是凸规划。定理4.2.6凸规划的任一局部最优解都是它的整体最优解。第19页一维搜索方法目标函数为单变量的非线性规划问题称为一维搜索问题(t)min)0(0maxttt其中Rt。精确一维搜索方法0.618法Newton法非精确一维搜索方法Goldstein法Armijo法第20页0.618法（近似黄金分割法）第1步确定单谷区间[a,b]，给定最后区间精度0;第2步计算最初两个探索点)(618.0)(382.01abbabat)(618.02abat并计算)(11t，)(22t；第3步若21，转第4步。否则转第5步；第4步若at2，停止迭代，输出1t。否则令2:tb，12:tt，)(618.0:1abbt，12:，计算)(11t，转第3步；第5步若1tb，停止迭代，输出2t。否则令1:ta，21:tt，)(618.0:2abat，21:，计算)(22t，转第3步。函数)(t称为在[a,b]上是单谷的，如果存在一个],[*bat，使得)(t在],[*ta上严格递减，且在],[*bt上严格递增。区间[a,b]称为)(t的单谷区间。第21页Newton法)(mint其中)(t是二次可微的，且0)(t。第1步给定初始点1t，0，1:k；第2步如果)(kt，停止迭代，输出kt。否则，当0)(kt时，停止，解题失败；当0)(kt时，转下一步；第3步计算)()(1kkkktttt，如果kktt1，停止迭代，输出1kt。否则1:kk，转第2步。第22页abcd)0()(tyty)0()0(tmy)0()0(1tmy)0()0(2Goldstein法第23页第1步给定满足1021mm的正数21,mm，增大探索点系数1；初始探索点),0(0t（或],0(maxt）。令:,0:00ba（或maxt），0:k第2步计算)(kt若)0()0()(1kktmt，进行第3步；否则，令kkkktbaa:,:11转第4步；第3步若)0()0()(2kktmt，停止迭代，输出kt。否则，令kkkkbbta:,:11若1kb，进行第4步；否则，令1:,:1kkttkk，转第2步；第4步取2:111kkkbat，令1:kk，转第2步。Goldstein法步骤第24页Armijo法)0()(tytmy)0()0(ktkMt取定Mm10，用一下两个式子限定kt不太大也不太小：)0()0()(kkmtt)0()0()(kkmMtMt第25页无约束最优化方法无约束问题的最优性条件最速下降法共轭方向法)(minxf(UMP)其中nTnRxxx),...,(1，RRfn:第26页无约束问题的最优化条件定理4.4.1设RRfn:在点nRx处可微。若存在nRp，使0)(pxfT则向量p是f在点x处的下降方向。定理4.4.2设RRfn:在点nRx处可微。若*x是(UMP)的局部最优解，则0)(*xf定理4.4.3设RRfn:在点nRx处的Hesse矩阵)(*2xf存在。若0)(*xf，并且)(*2xf正定则*x是(UMP)的局部最优解。定理4.4.4设RRfn:，nRx*，f是nR上得可微凸函数。若有0)(*xf则*x是(UMP)的整体最优解。第27页最速下降法设（NMP）问题中的目标函数RRfn:一阶连续可微第1步选取初始点0x，给定终止误差0，令0:k；第2步计算)(kxf，若)(kxf，停止迭代，输出kx。否则进行第3步；第3步取)(kkxfp第4步进行一维搜索，求kt，使得)(min)(0kktkkktpxfptxf令kkkkptxx1，1:kk，转第2步。第28页共轭方向法定义4.4.1设A为n阶实对称，对于非零向量nRqp,，若有0AqpT则称p和q是相互A共轭的。对于非零向量组1,...,1,0,niRpni，若有jinjiAppjTi1,...,1,0,,0)(则称nppp,...,,10是A共轭方向组，也称它们为一组A共轭方向。定理4.4.5设A是n阶实对称正定矩阵，)1,...,1,0(niRpni是非零向量。若110,...,,nppp是一组A共轭方向，则它们一定是线性无关的。第29页二次严格凸函数的无约束最优化问题cxbAxxxfTT21)(min（AP）其中A是n阶实对称正定矩阵，nRb，Rc定理4.4.6对于问题(AP)，若110,...,,nppp为任意一组A共轭方向，则由任意初始点nRx0出发，依次沿110,...,,nppp进行精确一维搜索，则最多经n次迭代可达(AP)的整体最优解。第30页F-R法步骤第1步选取初始点0x，给定终止误差0；第2步计算)(0xf，若)(0xf，停止迭代，输出0x；否则，进行第3步；第3步取)(00xfp，令0:k；第4步进行一维搜索求kt使得)(min)(0kktkkktpxfptxf，令kkkkptx