非线性规划山大刁在筠运筹学讲义.doc

第四章非线性规划教学重点:凸规划及其性质,无约束最优化问题的最优性条件及最速下降法,约束最优化问题的最优性条件及简约梯度法。教学难点:约束最优化问题的最优性条件。教学课时:24学时主要教学环节的组织:在详细讲解各种算法的基础上,结合例题,给学生以具体的认识,再通过大量习题加以巩固,也可以应用软件包解决一些问题。第一节基本概念教学重点:非线性规划问题的引入,非线性方法概述。教学难点:无。教学课时:2学时主要教学环节的组织:通过具体问题引入非线性规划模型,在具体讲述非线性规划方法的求解难题。1、非线性规划问题举例例1曲线最优拟合问题已知某物体的温度 与时间t之间有如下形式的经验函数关系:(*)其中,,是待定参数。现通过测试获得n组与t之间的实验数据,i=1,2,…,n。试确定参数,,,使理论曲线(*)尽可能地与n个测试点拟合。例2构件容积问题通过分析我们可以得到如下的规划模型:基本概念设,,如下的数学模型称为数学规划(MathematicalProgramming,MP):约束集或可行域MP的可行解或可行点MP中目标函数和约束函数中至少有一个不是x的线性函数,称(MP)为非线性规划令,其中,,那么(MP)可简记为或者当p=0,q=0时,称为无约束非线性规划或者无约束最优化问题。否则,称为约束非线性规划或者约束最优化问题。(MP),若,并且有则称是(MP)的整体最优解或整体极小点,称是(MP)的整体最优值或整体极小值。如果有则称是(MP)的严格整体最优解或严格整体极小点,称是(MP)的严格整体最优值或严格整体极小值。(MP),若,并且存在的一个领域,使,则称是(MP)的局部最优解或局部极小点,称是(MP)的局部最优值或局部极小点。如果有,则称是(MP)的严格局部最优解或严格局部极小点,称是(MP)的严格局部最优值或严格局部极小点。,若存在 ,使则称向量p是函数f(x)在点处的下降方向。,若存在,使则称向量p是函数f(x)在点处关于X的可行方向。一般解非线性规划问题的迭代方法的步骤:第一步:选取初始点;第二步:构造搜索方向;第三步:根据,确定步长;第四步:令若已满足某种终止条件,停止迭代,输出近似最优解,否则令,转回第二步。常用规则:1、相邻两次迭代点的绝对差小于给定误差,即;2、相邻两次迭代点的相对差小于给定误差,即;3、;4、第二节凸函数和凸规划教学重点:凸函数的概念及性质,凸规划的概念、性质及判定。教学难点:凸规划的概念及性质。教学课时:4学时主要教学环节的组织:首先介绍凸函数的定义,然后给出凸函数及凸规划的性质。凸函数的定义及性质:,,如果对任意的有,则称f是S上的凸函数,或f在S上是凸的。如果对于任意的有,则称f是S上的严格凸函数,或f在S上是严格凸的。若-f是S上的(严格)凸函数,则称f是S上的(严格)凹函数,或f在S上是(严格)凹的。(a)凸函数(b)凹函数凸函数的性质:。(1)若是S上的凸函数,,则是S上的凸函数;(2)若都是S上的凸函数,则是S上的凸函数。,是凸函数,,则集合是凸集。注:一般来说上述定理的逆是不成立的。,可微,则f是S上的凸函数的充要条件是,其中是函数f在点处的一阶导数或梯度。f是S上的严格凸函数的充要条件是,,对有:故()由多元函数Taylor展开式可知:将其带入(),由凸知,对分别有: ()和()将()乘以,()乘以,两式相加得到证明和(1),二阶连续可导,则f是S上的凸函数的充要条件是f的Hesse矩阵在S上是半正定的。当在S上是正定矩阵时,f是S上的严格凸函数。(注意:该逆命题不成立。)凸规划及其性质约束集如果(MP)的约束集X是凸集,目标函数f是X上的凸函数,则(MP)叫做非线性凸规划,或简称为凸规划。(MP),若皆为上的凸函数,皆为线性函数,并且f是X上的凸函数,则(MP)是凸规划。。证明:设是凸规划(MP)的一个局部解,存在则的临域使得若不是(MP)的整数最优解,则存在,使又因为是凸函数,有显然,当充分小时,有出现矛盾。(MP)是凸规划解答:将二次目标函数改写为::的一、二、三阶顺序主子式分别为:正定,为凸函数。而半正定,是凸函数。其他约束条件均为线性。故改(MP)为凸规划。