第4章 非线性规划-张

第四章非线性规划模型PAGEPAGE70第四章非线性规划模型第一节非线性规划的实例与基本概念一、非线性规划的实例例1化学反应的平衡组成设现有原料由种原子组成，各种原子数量依次为共生成种分子（产品），设生产数量（待求）依次为。设第种分子中含各种原子的数量依次为所有产品中含第种原子数之和为由熟知的质量守恒定律有在一定的温度、压力下，每种化合物都具有一定的自由能，根据化学热力学原理，当化学反应达到平衡状态时，系统的总自由能最小。用表示第种化合物具有的自由能，它的表达式为其中是与温度、压力及有关的常数。总自由能为问题变为求使（4-1）（4-2）式（4-1），（4-2）构成的数学模型显然与前几章的数学模型不同，它就是我们即将介绍的非线性规划模型。例2成组气田开发的最优化模型设有一组个气田，要求在一定开发期内产气总量为，而为第个气田的极限产量，为第个气田的最优产量（待求），为第个气田的生产井数，可按公式计算，其中，分别为第个气田的地层边界压力和井底流动压力，，，是与第个气田的地层形状、流动条件、井排数、井排半径及井距有关的常数。要求各气田适当配产，使单产成本最低。根据题意可得如下数学模型（4-3）（4-4）其中，，分别与第个气田的管线成本、生产消耗、气压站和综合处理站、钻井成本有关的参数。式（4-3），（4-4）也是一个非线性规划模型。二、非线性规划的基本概念1．非线性规划的定义称形如，（4-5）（4-6）（4-7）的数学模型为一个数学规划，称为该数学规划的目标函数，称（4-6）式为等式约束，（4-7）式为不等式约束，若中至少有一个是变量的非线性函数，则称模型（4-5）—（4-7）是非线性规划问题（或非线性最优化问题），否则称（4-5）—（4-7）为线性规划问题（或线性优化问题）。当时，称问题，为无约束最优化问题，简称为无约束问题。2．最优解的概念满足（4-6），（4-7）的维向量称为该数学规划的一个可行点，所有可行点做成的集合称为可行集或可行域，即对于，若有，使，对所有满足的都成立，则称为该规划的一个局部最优解；若对所有都成立，则称为该规划的整体最优解或全局最优解。若对于，有，使，对所有满足且都成立，则称为该规划的一个严格局部最优解；若对所有且都成立,则称为该规划的一个严格整体最优解。例3设有非线性规划问题可行集D如图所示，由于，又，，因此是该问题的一个整体最优解.当然也是局部最优解001图1例3的可行集D第二节n元函数微分学与最优性条件一、n元函数微分学知识为了给出非线性规划问题的最优性条件，先来介绍一些元函数的微分学知识.在下边的讨论中，假设元函数具有讨论中所遇到的可微性阶数.1．梯度函数在点处的梯度，定义为在点处的个偏导数构成的列向量，记为，即（4-8）2．二阶偏导数矩阵（Hesse矩阵）称如下的阶方阵（4-9）为函数在点处的二阶偏导数矩阵亦称为Hesse矩阵，当时，为一实对称矩阵.3．公式元函数在点处的公式（写到二次项）为(4-10)其中为比高阶的无穷小量.4．最速下降方向下面证明，是在点处的最速下降方向.因为函数沿方向的变化率是，故在点处最速下降方向的单位向量应是问题（4-11）的解，注意到，其中是与方向的夹角。极小化该式，便得到当即时，的值最小，这时，因此称为函数在点处的最速下降方向，同样理由称为在点处的最速上升方向。5．一维搜索与下降方向给定点，方向向量，称问题为由点始沿方向的一维搜索.这是一元函数求极小点的问题。将函数在点展开得（4-12）当且充分小时，由上式得即当充分小且时，函数值较小，因此，若，称为函数在点处的下降方向，类似地，若，且充分小，由（4-8）式知，因此，此时称为函数在点处的上升方向。二、无约束问题的最优性条件定理1（一阶必要条件）设函数连续可微，若点是的局部极小点，则。证明用反证法，设，取，则，因而存在，使当时，，这与为的局部极小点矛盾.故应有。若有点使，则称为的驻点或稳定点.由此，定理1表明，若函数连续可微，且不是驻点，则不是的局部极小点。定理2（二阶必要条件）若函数二阶连续可微，且是的局部极小点，则，且半正定。证明由题设及公式有于是（4-13）令，由于，故由（4-9）式得，又由的任意性知，半正定。定理3（二阶充分条件）设函数二阶连续可微，且，正定，则为的严格局部极小点。证明据已知条件和公式得（4-14）由正定知，存在正数使得，故由（4-14）式得：（4-15）因此据式（4-15）知，存在使当时，即当且时，，故为的严格局部极小点。三、约束极值问题的最优解的一阶必要条件定理4设是约束极值问题，（4-16）（4-17）（4-18）的局部最优解，且向量组，，，，线性无关，其中为在点处有效不等式约束的指标集，则存在向量，且，使（4-19）（4-20）证明略.条件（4-19），(4-20)称为Kuhn-Tuker条件,这个条件是很重要的.它是设计算法、研究算法收敛性、给出判断程序终止准则的理论基础。常称定理4为Kuhn-Tuker定理，满足Kuhn-Tuker条件的可行点称为K-T点。四、凸规划及其最优性条件1．凸集中的一个非空子集称为凸集,若及,有。2．凸函数在凸集上定义的函数称为凸函数，若，及，有若函数为凸集上的凸函数，则称为上的凹函数.易知凸集上的线性函数即是凸函数又是凹函数。3．凸规划对于非线性规划问题（4-16）—（4-18），若为一凸函数，为凹函数，而为线性函数，则称该问题为一凸规划问题。4．凸规划的最优性条件定理5设为凸规划问题（4-16）—（4-18）的一个可行点，则为该问题的最优解的充分必要条件是为该问题的K-T点。证明略。应指出，对于凸规划问题，任何局部最优解均为全局最优解。第三节一维搜索算法对于一元函数，,求使达到极小，对于，，当给定，，，问题也是一种求一元函数的极小问题，这就是一维搜索问题。一维搜索算法一般分为两步：第一步，找一个包含极小点区间，称为极小区间，第二步，逐步缩小极小区间，直到极小区间的长度已充分小，则区间中点可近似作为的极小点。本节先给出求极小区间的“倍增半减法”，再给出缩短极小区间的法。一、求极小区间的倍增半减法对于问题，可取一初始步长，及，计算，（其中），若即向右搜索时，下降，令，，计算，，表明向右搜索时，仍下降，令，，直到第步有，且，则令，，为一极小区间。图2求极小区间框图如果时已有把的数值对换，且令，计算，若则令；否则令，，直到函数值增加，即有某个使时，则令。将以上步骤做成框图，见图2。二、缩短极小区间的0.618法前段已得到极小区间，现在要按比例来缩短区间的长度，待定.在内取点，.设下一个极小区间为，见图3。图3法缩短区间过程即设，在新区间内仍按比例缩短区间，即取点,,由，得今希望新点中有一点与重合，以便少算一次函数值.据的表达式知：若让，则得，导致，不符合要求。若让得，，整理得，解得，取。由及得缩短区间的算法框图如图4，设控制精度为。图4法缩短极小区间框图附注：由上述讨论可知，0.618这个数恰好是区间的缩短率；此外需指出，法只是一维搜索算法的一部分，必须上接求极小区间的倍增半减法，二者合起来才构成一个完整的一维搜索算法。第四节共轭梯度法共轭方向法是一类比较有效的求解无约束问题的方法,此类方法中较常用的一种方法是共轭梯度法。本节内容分为三部分，第一部分介绍本节所需要的代数预备知识，第二部分一般地介绍共轭方向法的基本性质，第三部分给出共轭梯度法的迭代步骤与性质。一、代数预备知识1．一般认为，在元函数的极小点附近，目标函数的性态与正定二次函数相近.这里所说的正定二次函数是指，其中为阶正定矩阵，为维列向量，为给定的维列向量。2．维正交定理命题1若中的向量与个线性无关的维向量均正交，则有.证明由于线性无关，因而构成的一组基，故可表作用左乘上式两端得，即，因此。3．共轭向量定义设为阶正定矩阵，，为维列向量，若，则称与为共轭（或正交）的。命题2若为两两共轭（为阶正定矩阵）的维非零向量组，则线性无关（）。证明设有数使用左乘上式两边得由正定及得，故由上式得，，因此线性无关。设为元正定二次函数，而令，其中为阶正定矩阵。4．若，则，因此式可表达成，（4-21）证明以左乘两边得即，故。5．若满足则由得（4-22）二、共轭方向法定义若一算法对于正定二次函数产生共轭（为阶正定矩阵）的方向向量组，则称此算法为一共轭方向法.如果一个算法经过有限次的一维搜索即可求得正定二次函数的极小点，则称此算法具有二次终止性质.下边的定理表明共轭方向法具有二次终止性质.定理1设是共轭的非零向量组，若由开始，依次沿这个方向搜索的极小点，设得到点，记，，则（4-23）特别当时，，故为的极小点，这就是说，沿共轭的至多个方向依次各作一次一维搜索，可得到的极小点。证明由（4-20）式得，。又因为用左乘上式两端并由题设得：综合起来即有，当时，上式表明与均正交，由命题2知，线性无关，再由命题1知.即，但正定，故为的整体极小点（也是唯一极小点）。三、共轭梯度法共轭梯度法的第一次迭代仍为最速下降法。即给定初始点，计算，取为点处的搜索方向，求满足令，，当时终止，即为的极小点，否则取下一个搜索方向为与的适当组合，即令（4-24）其中（4-25）再求使即由开始沿作一维搜索，得，令，当时，下一迭代方向为，仿此迭代下去，即为共轭梯度法。在实际计算中，应采用每次迭代就重新开始的策略.就是说，对于元函数，当采用共轭梯度法时，在处，若，应令为新的初始点，再由最速下降法起步，继而应用共轭梯度法迭代。应该指出，（4-22）、（4-23）可一般写成（4-26）（4-27）现给出共轭梯度法的计算框图，下面的定理给出了共轭梯度法的性质，即共轭梯度法是一种共轭方向法，从而在理论上是一种较好的算法，实际上，它的确是一种有效的算法。图5共轭梯度法框图例1用共轭梯度法求解下列问题：取初始点。解，第一次迭代：令从出发，沿方向作一维搜索，即求使因，由解得：，第二次迭代：，令从出发，沿方向作一维搜索，即求使因为由解得：。于是由于，而正定，即为严格凸函数，故为的唯一极小点.事实上用导数法可直接验证，确是的唯一极小点。定理2当共轭梯度法用于正定二次函数时，如果在点处没有结束，则1）两两正交；2）关于两两共轭，因此至多次迭代可得到的极小点。证明：略。第五节乘子法乘子法是把约束极值问题化为一系列无约束问题来求解的一种算法，同时也是在原始罚函数法的基础上发展起来的一种很有用的罚函数法.下面首先介绍等式约束问题的乘子法，再给出等式-不等式约束问题的乘子法.一、等式约束问题先考虑等式约束问题（4-28）1、增广函数由K-T条件，若为（4-26）的最优解，则使（4-29）（4-27）式显然可成将上式整理得（4-30）令（4-31）则问题（4-32）的最优解应满足此即（4-30）式。这样，求(4-28)的K-T点的问题变为解无约束问题（4-32）。在（4-31）式中，当时，是经典的函数，而当诸时，（4-31）是外罚函数，因此一般称（4-31）式为增广函数。2、等式约束问题乘子法步骤对于给定的，，设为的极小点，则有即据此于是当时有，这就是说，的最优解是问题（4-33）的最优解.于是当近似满足约束时就得到了（4-27）的最优解.因此，可预先给定，求解问题，当得到的满足，时，就得到了（4-28）的最优解.这样就得到了为（4-26）的最优解的一个判别准则，.（4-34）而为的解的必要条件是但，还应为（4-26）的解而满足（4-29），故令，.(4-35)以此式修正成为，于是得到乘子法的步骤为步1.给定适当大的，，，给定初始点，给定。步2.以为初始点求的无约束极小，设为。步3.若，则为（4-26）的最优解，停.否则计算，若，转步4，若往下。步4.用（4-35）式计算，，转步2。附注1：在上述步骤中，出现得向量范数为向量的2范数即向量的长度。附注2：在步3中，当时，表明趋于0太慢，应扩大罚因子以代替。二、等式-不等式约束问题1．增广函数对于等式-不等式约束问题,(4-36)通过引入松弛变量，将其转化为等式约束问题，再类似于上一段的推导，并消去松弛变量，可得相应于问题的增广函数（4-37）2．乘子的修正公式，.（4-38），（4-39）3．计算终止准则对于等式约束情况，当，时即停止.而对于问题（4-35），令（4-40）则当时停止计算，为该问题的最优解。图6等式-不等式约束问题乘子法框图4．步骤与框图步1.给定，，，给定，，，计算，给定，，，。步2.以为初始点，用无约束问题算法求使步3.用（4-36）式求。步4.若，停止迭代，输出最优解，停机.否则往下。步5.若，则转步6.否则，，往下。步6.置，；，；，，，转步2。现把上述步骤表达为框图的形式，框图中设定最大迭代次数，超过此次数，认为原问题没有可行解，运算停止.第六节模式搜索法本节介绍求解无约束极值问题的一种直接方法即不需要计算导数的方法，这就是模式搜索法。1．基本思想模式搜索法是由Hooke和Jeeves提出的，因此又称为Hooke-Jeeves方法.这种方法的基本思想从几何意义上讲，是寻找具有较小函数值的“山谷”，力图使迭代产生的序列沿“山谷”走向逼近极小点.算法从初始基点开始，包括两种类型的移动，这就是探测移动和模式移动。探测移动依次沿个坐标轴进行，用以确定新的基点和有利于函数值下降的方向.模式移动沿相邻两个基点的连线方向进行，试图顺着“山谷”使函数值更快减小，两种移动交替进行的具体情形如下（参看图7）。图7设目标函数为，.坐标方向，。给定初始步长，加速因子.任取初始点，作为第1个基点.下面以表示第个基点.在每轮探测移动中，自变量用表示，即是沿探测的出发点.这样，是沿探测的出发点，是沿探测得到的点.首先，从出发，进行探测移动.先沿探测，如果，则探测成功，令（4-41）并从出发沿方向探测.否则，沿方向探测失败，再沿方向探测.如果，则沿方向探测成功，令（4-42）并从出发沿探测.如果，则沿方向探测也失败.令（4-43）再从出发，沿方向探测，方法同上，得到的点记为.按此方式作下去，直到沿个坐标方向探测完毕，得到点。如果，则作为新的基点.记作（4-44）这时，可望是有利于函数值减小的方向。下一步，沿方向进行模式移动，令新的为（4-45）模式移动后，以为起点进行探测移动，这轮探测仍然沿坐标轴方向进行.探测完毕，得到的点仍记作。如果，则表明此次模式移动成功，于是取新的基点，再沿方向进行模式移动。如果，则表明模式移动及此次模式移动之后的探测移动均无效.于是退回到基点，减少步长，再从出发，依次沿各坐标轴方向进行探测移动。如此继续下去，直到满足精度要求，即步长小于事先给定的某个小的正数为止。2．计算步骤模式搜索法的计算步骤如下：步1.给定初始点，个坐标方向，初始步长，加速因子，缩减率，允许误差，置，，。步2.如果，则令，进行步4；否则，进行步3。步3.如果，则令，进行步4；否则，令，进行步4。步4.如果，则置，转步2；否则，进行步5。步5.如果，则进行步6；否则，进行步7。步6.置，令，置，，转步2。步7.如果，则停止迭代，得点；否则置，，，置，，转步2。例1用模式搜索法求解下列问题取初始点，坐标方向，；，，。解先在周围进行探测移动，令，探测情况如下：，（失败）=，。（成功）因此令，从出发沿方向探测情况如下：，。（成功）因此令，第一轮探测完成.由于，因此得到第2个基点。再沿方向进行模式移动，令模式移动后，立即从得到的点出发，进行第2轮探测移动。探测情况如下：先沿探测，此时有，（失败），（失败）沿正反向探测均失败，令。从出发沿方向探测，结果是；即沿正反向探测也都失败.令。比较在和基点处的函数值上式表明模式移动是成功的，因此得到新基点：从出发，沿方向进行模式移动。令。然后从出发进行探测移动.作下去就会发现，此次模式移动失败，因此退回到基点.减少步长，令。再从开始，依次沿和探测，还会发现，在周围的探测移动也是失败的，必须继续缩减步长，继续往下作，必能得出结论，是局部最优解。事实上，用导数方法易得确是该问题的最优解。该法的收敛速度较慢，但编程较简单，对变量不多的问题可使用。第七节非线性规划的一个典型例子节水洗衣机（1996年全国大学生数学建模竞赛B题）我国淡水资源有限，节约用水人人有责，洗衣在家庭用水中占有相当大的份额，目前洗衣机已非常普及，节约洗衣机用水十分重要。假设在放入衣物和洗涤剂后洗衣机的运行过程为：加水——漂洗——脱水——加水——漂洗——脱水…——加水——漂洗——脱水（称“加水——漂洗——脱水”为运行一轮）。请为洗衣机设计一种程序（包括运行多少轮，每轮加水量等）使得在满足一定洗涤效果的条件下，总用水量最少，选用合理的数据进行计算，对照目前常用的洗衣机的运行情况，对你的模型和结果做出评价。下面给比赛题给出参考解答1．假设和定义1.1基本假设1）只考虑离散的加水方案，即每次脱水完后，全换成清水进行下一次洗涤。2）每次洗漂加水量不能低于，否则洗衣机无法转动，加水量不能高于，否则会溢出，设。3）每次洗漂的时间是足够的，以便衣服上的脏物充分溶于水中，从而使每次所加的水被充分利用。4）脱水时间也是足够的，以便使脏水充分脱出，也就是让衣服所含的脏水量达到一个底限，设这个底限是大于0的常数，并由于脱水时不加水，所以。1.2变量及符号1）设共进行轮“洗漂——脱水”的过程，依次为第0轮，第1轮，…，第轮。2）第轮用水量设为。3）衣服上的初始脏物量为，在第轮脱水之后的脏物量为2．数学模型的建立2.1溶解特征和动态方程在第轮洗漂之后和脱水之前，第轮脱水之后的脏物量，已变成了两部分，（4-46）其中表示已溶于水中的脏物量，表示尚未溶于水的脏物量。与第轮的加水量有关，总的规律应是越大，就越大，当且仅当时，值最小（，因为洗衣机处于转动临界点，有可能无法转动），当时值最大（，其中称为溶解率）因此简单的选用线性关系表示这种溶解特性，则有：（4-47）在第轮脱水之后，衣服上尚有脏物，有脏水，其中脏水所含脏物量为，于是第轮完成后衣服上尚存的脏物总量为（4-48）将（4-47）式代入上式并整理后得系统动态方程（4-49）2.2优化模型由于是洗衣整个过程结束后衣服上残存的脏物量，而是初始脏物量，因此反映了洗衣的干净程度，称为洗衣效果。由系统动态方程（4-49）可得（4-50）其中符号表示变量的连乘积。又总用水量为（4-51）于是可得该问题的优化模型为（4-52）其中表示对洗净效果的要求，若令（4-53）（4-54）则优化模型可化为更简洁的形式（4-55）其中（4-56）3、分析和求解3.1最少洗衣轮数定义函数（4-57）易求得（4-58）可见是区间上的单调减函数，所以