非线性规划基础理论

单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,第六章 非线性规划,基础知识,引言,什么是非线性规划,线性规划问题和整数规划问题，其共同的特征是最优化问题中的目标函数和约束条件均为设计变量的线性函数。但在实际建模过程中还有大量的问题，其目标函数或约束条件很难用线性函数来表达，当目标函数或约束条件中有一个以上是非线性函数时，就不能用线性的方法来处理，而要采用非线性的方法，那么我们称这种问题为非线性规划问题,非线性规划的产生和发展,自从,1951,年,H. W. Kuhn,及,A. W. Tucker,探讨了非线性规划解的最优性条件，为非线性规划奠定了理论基础之后，非线性规划逐渐形成了一门十分重要且比较活跃的新兴学科，出现了许多解非线性规划问题的有效的算法。由,70,年代开始，该分支得到迅速发展：理论方面，非线性规划借鉴了数学理论中其他分支的成果，逐步形成自身的学科特色；在应用方面，非线性规划为系统的优化和管理提供了有力的工具。,随着电子计算机的应用，非线性规划在最优设计、管理科学、质量控制等许多领域得到越来越深入的应用。非线性规划发展到今天，虽然已经提出许多求解方法和策略，但是对于非线性规划的最优化问题目前还没有适于各种不同情况的一般算法，各个方法都有自己特定的适用范围。因而，这是需要人们更深入的进行研究的一个领域。,典型的非线性规划问题,选址问题,问题的提出,一家大型连锁超市在某地有家分店 ，为了数学语言描述的方便，可在平面直角坐标系给出其位置表述：,A,1,的坐标为,(,x,1,y,1,),，,A,2,的坐标为,(,x,2,y,2,),，以此类推，,A,n,的坐标为,(,x,n,y,n,),。现在超市拟在当地选择一个理想的位置建立一个供货点，由于该超市各分店在经营规模上的不同，出货量也不同，导致供货点对各分店的送货频率不同，假设供货点每周给,A,i,送货的次数为,c,i,(,i,=1,2,n,),，同时假设每公里的运输费保持定值,m,元,/,公里。那么超市应当把供货点设在什么地方可以使得运输成本最低？,问题分析,假设供货点坐标为,(,x,y,),，那么由供货点到某分店,A,i,的距离和运输费分别为：,故运输的总成本为对各个分店运输成本的总和，整个问题的数学模型可以表达为：,上述问题的目标函数为设计变量,x,和,y,的非线性函数，故为非线性规划问题，由于设计变量,x,和,y,不受任何条件的约束，故为无约束非线性规划。,典型的非线性规划问题,营业计划制定问题,问题的提出,某公司销售两种建材,A,和,B,以满足市场的需要，生产建材,A,和,B,均要消耗资原材料,M,和,N,，其中每吨,A,建材需要消耗,10,吨,M,和,18,吨,N,，每吨,B,需要消耗,20,吨,M,和,12,吨,N,，已知产品的利润是销售量的函数，现有原材料,200,吨,M,和,100,吨,N,，产品的售价、和资源的对应关系如表所示，该公司应当如何制定生产销售计划使得销售额最大。,典型的非线性规划问题,营业计划制定问题,问题分析,设,x,1,和,x,2,为产品,A,和产品,B,的销售量，由,A,的单价为,p,1,，,B,的单价为,p,2,，则可知公司的销售收入为 ，在该例中，单位售价为销量的函数，故由表中的公式可得,最优化的目标为使得销售额最大，即取得最大值。,由原材料的限制，可得约束条件为：,且考虑到和的产量应当为非负实数，故该问题的数学模型为：,上述问题的目标函数为设计变量,x,1,和,x,2,的非线性函数，约束条件为设计变量的,x,1,和,x,2,的线性函数，为有约束的非线性规划问题。,典型的非线性规划问题,容器设计问题,问题的提出,某工厂按照客户的要求定制专门的储藏用容器，订货合同要求该工厂制造一种敞口的长方体容器，容积为,10m,3,，该种容器的底必须为正方形，容器总质量不超过,56kg,已知用作容器四壁的材料为,20,元,/m,2,，重量为,3kg,；用作容器底的材料,30/m,2,，重量为,2kg,。则制造该容器所需的最小成本是多少？,问题分析,由于该容器的底为正方形，故设底边长为,x,1,，高为,x,2,，则该容器底部的面积为,m,2,，四壁的侧面积为,4,x,1,x,2,，该容器的容积为,10m,3,可得 ，根据题意，容器底部的重量为,kg,，侧面的重量为,kg,，由于容器的总质量不得超过,56kg,，故可得约束关系 ，打造该容器的成本为底部的材料费和四壁的材料费之和，为 ，我们设计的目标是使得制造该容器的最小成本，即使得取得最小值。且考虑到容器的底和高均为非负实数，故综合上述各式得到该最优化问题的数学模型为：,上述问题的目标函数为设计变量,x,1,和,x,2,的非线性函,数，约束条件也为设计变量的,x,1,和,x,2,的非线性函,数，为有约束的非线性规划问题。,非线性规划问题的数学模型,一般形式,非线性规划问题涉及的领域非常广泛，由实际的应用问题建立起来的非线性规划问题的具体形式也是各式各样的，为了讨论问题的方便，我们将其用统一的数学形式表达，简单的说，均可以将问题转化为求一个,n,维变量,x,的实函数,f,(,x,),的最大值或者最小值，同时受到一组约束的限制，这些约束可以是等式约束，也可以是不等式约束，其形式可以表达如下：,式中，,x,是,n,维欧氏空间,R,n,中的向量，,f,(,x,),为目标函数， 为约束条件。非线性规划要求目标函数和约束条件中至少有一个是,x,的非线性函数。在后面的讨论中，如果不特别指出，我们均采用上述标准模型。,若令,D,为非线性规划问题的可行解集合，即满足所有约束关系的解的集合，则上述标准型也可以写成如下形式：,非线性规划的理论基础,等值面和等值线,最优化问题的目标函数,f,(,x,),为设计变量,x,的可计算函数，这主要表现在如下两个方面：,若给出一个设计方案，即设定一组,x,1,x,2,x,n,的值，目标函数,f,(,x,),必有一确定的数值；,若给出目标函数,f,(,x,),的值，则可能有无限多组,x,1,x,2,x,n,数值与之对应。也就是说，当,f,(,x,)=,c,时，,x,在设计空间中有一个点集。一般情况下，把该点集称为目标函数的等值面。显然，在一个特定的等值面上，每个设计方案的目标函数值都是相等的。,目标函数的等值面具有以下性质,不同值的等值面之间不相交；,除了极值所在的等值面外，其余的等值面不会在区域的内部中断，这是因为目标函数都是连续函数；,等值面稠密的地方，目标函数值变化较快，稀疏的地方变化较慢。,非线性规划的理论基础,全局最优解和局部最优解,非线性规划问题的可行域,把满足非线性规划中约束条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域），记为,D,。,即,局部极小值点,对于非线性规划问题，设 ，若存在 ，使得对一切 ，且 ，都有 ，则称 是,f,(,x,),在,D,上的局部极小值点（局部最优解）,特别的，当 时，若 ，则称 是,f,(,x,),在,D,上的严格局部极小值点（严格局部最优解）,全局极小值点,对于非线性规划问题，设 ，对任意的 ，都有 ，则称 是,f,(,x,),在,D,上的全局极小值点（全局最优解）,特别的，当 时，若 ，则称 是,f,(,x,),在,D,上的严格全局极小值点（严格全局最优解）。,非线性规划的理论基础,凸函数和凸规划,上述有关最优化问题的极值点的定义描述了优化问题中解的判断条件，一般而言，我们的优化过程实际上就是找极值点或者最值点的过程，但是上面的定义往往并不便于执行，我们需要引入其他的手段进行分析和判断，故我们首先介绍凸集、凸函数和凸规划的概念，在这类特殊的问题之中，极值条件有着其特殊性。,对于一个非线性规划的目标函数，有局部极小值和全局极小值的概念，那么我们提出凸集和凸函数的概念就是为了区分目标函数的极小值在什么情况下是局部极小值，什么情况下是全局极小值。,凸集,设 ，若对于 都有 则称,T,为凸集,用形象一点的语言描述就是凸集的特征是集合中任两点连成的线段必属于这个集合。下图是二维空间中具有典型特征的凸集和非凸集的例子。,非线性规划的理论基础,凸函数和凸规划,凸函数,设,f,(,x,),是定义在非空凸集 上的函数，若 ，都有 ，则称,f,(,x,),为,上的凸函数。,如果把上述“”换成“,”,，则可以定义上的凹函数和严格凹函数。换一种表述方法，如果,-,f,为,上的凸函数，则称,f,为,上的凹函数。,一元凸函数有明显的几何意义：过函数图象上任意两点的弦线段，处处都在函数图象的上方，而凹函数的情形则正好相反,非线性规划的理论基础,凸函数的性质,设 为定义在凸集,上的凸函数，则,所有凸函数的线性组合 也为凸函数,设,为,R,n,中的一个非空凸集，,f,(,x,),为定义在凸集,上的凸函数，,是一个实数，则水平集 是凸集。,设,为,R,n,中的一个内部非空的凸集，,f,(,x,),为定义在凸集,上的凸函数，则,f,(,x,),在,内连续。,当函数一阶或二阶可微时，除了可以根据定义判断其是否为凸（凹）函数外，更常用的办法是使用即将介绍的一阶和二阶判别条件这些条件中，有的是充要条件，有的仅仅是充分条件，在使用时要注意条件的性质。,凸函数的一阶充要条件,设,是,R,n,中的非空开凸集，,f,(,x,),是定义在,上的可微函数。那么，,f,(,x,),是,上的凸函数的充要条件是：对 恒有,非线性规划的理论基础,凸函数的性质,严格凸函数的一阶充要条件,凸函数的二阶充要条件,严格凸函数的二阶充分条件,非线性规划的理论基础,凸函数的性质,凸函数在其定义域上的任一极小点都是其在定义域上的全局极小点，且全体极小点的集合是凸集,凸函数极小点的充分条件,非线性规划的理论基础,凸函数的性质,非线性规划的理论基础,凸规划,非线性规划的理论基础,无约束非线性规划问题的极值条件,一元函数极值点存在的必要条件和充分条件,多元函数极大值点的充要条件,多元函数极小值点的充要条件,非线性规划的理论基础,多维有约束非线性规划问题的极值条件,K-T,条件,一般的非线性规划问题可以表述为：,解上述问题的实质是在所有的约束条件所形成的可行域内，求得目标函数的极值点，即满足约束条件的最优点。由于约束最优点不仅与目标函数本身的性质有关，还与约束函数的性质有关，因此约束条件下的优化问题比无约束条件下的优化问题更为复杂和难以求解。,库恩,-,塔克（,Kuhn-Tucker,）条件（简称,K-T,条件）是非线性规划领域中最重要的理论成果之一，它是由,H. W. Kuhn,和,A. W. Tucker,在,1951,年提出的，我们通常借助库恩,-,塔克条件来判断和检验约束优化问题中某个可行点是否为约束极值点，即将,K-T,条件作为确定一般非线性规划问题中某点是否为极值点的必要条件，对于凸规划问题，,K-T,条件同时也是一个充分条件。但是如何判别所找到的极值点是全域最优点还是局部极值点，至今还没有一个统一而有效的判别方法。,非线性规划问题的求解,分类,根据非线性规划问题的目标函数和约束形式的类型，我们可以将非线性规划问题可以分为无约束的非线性规划问题（即目标函数是决策变量的非线性函数，没有约束条件）和有约束的非线性规划问题。其中，有约束非线性规划问题要比无约束非线性规划问题的求解困难得多。而且非线性规划问题也不像线性规划问题那样有类似于单纯形法的通用算法。对非线性规划问题目前还没有适用于各种问题的一般算法，它的各种算法都有自己特定的适用范围。,方法,目前常见的无约束非线性规划问题的算法有不基于梯度信息的坐标轮换法、或者是基于梯度信息的最速下降法、牛顿法、共轭方向法等等。,而对于有约束的非线性规划问题，求解有约束极值问题要比求解无约束极值问题困难得多。对极小化问题来说，除了要使目标函数经每次迭代后有所下降之外，还要时刻注意解的可行性问题，这就给寻优工作带来了很大困难。为了简化优化工作，通常的做法是：尽量将非线性规划问题化为线性规划问题，将有约束问题化为无约束问题。,非线性规划问题的求解,具体解法,直接法,直接法是一种数值方法，其原理是利用函数的局部性质和一些已知点的函数值，来确定下一步的迭代点，循环往复，以一定的条件作为迭代结束条件，求取函数极值。此类方法的典型代表有基于梯度信息的一类迭代方法，如牛顿法、变尺度算法等。对于目标函数难以用解析式表达的问题，这种方法较适用。,解析法,解析法则是按照函数极值的必要条件，用数学分析的方法求出其相应的解析解，再按照充分条件确定最优解，如梯度投影法、容许方向法等。对于目标函数是设计变量的显函数，且解析性质较好的这样一类问题，这种方法较合适。,用线性规划或二次规划逼近的方法,这是一种近似求解的方法。前者是将非线性规划问题在某个近似解处将约束条件和目标函数展开成泰勒级数，略去其二次项及二次以上的项，使约束条件和目标函数都成为线性的，原来的问题就用这个线性问题来近似代替。这种算法比较适合求解变量和约束较多，但只有少量约束是非线性的规划问题；二次规划适合于约束为线性的而目标函数是二次函数这种简单的非线性规划问题。,把非线性规划问题转化为无约束极值问题，通过一系列无约束问题的求解来逼近非线性规划的解，如罚函数法等。这种方法通常用于求解目标函数和约束条件的表达式较复杂的这样一类问题。,非线性规划问题的求解,迭代法的基本思想,非线性规划问题的求解,迭代法选取方向和步长的原则,非线性规划问题的求解,迭代法的步骤,