规划模型专题二非线性规划优秀课件.ppt

规划模型专题二非线性规划第1页，本讲稿共60页第一部分第一部分 非线性规划非线性规划v 前面有老师介绍了线性规划问题，典型前面有老师介绍了线性规划问题，典型的问题的问题“下料问题下料问题”、“运输问题运输问题”等，这等，这些问题都比较简单。但实际中的问题不仅仅些问题都比较简单。但实际中的问题不仅仅是简单的线性规划问题，可能是比较繁杂的是简单的线性规划问题，可能是比较繁杂的非线性规划问题。非线性规划问题。下面我们从一个竞赛题目出发，以理解非线性下面我们从一个竞赛题目出发，以理解非线性规划的定义、建模过程及其求解过程。规划的定义、建模过程及其求解过程。第2页，本讲稿共60页 在约在约1万米的高空的某边长为万米的高空的某边长为160km的正方的正方形区域内，经常有若干架飞机作水平飞行，区域形区域内，经常有若干架飞机作水平飞行，区域内每架飞机的位置和速度向量均由计算机记录其内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，计算机记录其数据后，的飞机到达区域边缘时，计算机记录其数据后，要立即计算并判断是否会发生碰撞。若会发生碰要立即计算并判断是否会发生碰撞。若会发生碰撞，则应计算如何调整各架飞机（包括新进入的撞，则应计算如何调整各架飞机（包括新进入的飞机）飞行的方向角，以避免碰撞，且使飞机的飞机）飞行的方向角，以避免碰撞，且使飞机的调整的幅度尽量小，调整的幅度尽量小，例例1 1995年全国数学建模年全国数学建模A题：飞行管理问题题：飞行管理问题一、例题讲解一、例题讲解第3页，本讲稿共60页该题比较有意思的一句话是：该题比较有意思的一句话是：“使调整弧度最小使调整弧度最小”开放性的一句话，没有限制得很死，较灵活，开放性的一句话，没有限制得很死，较灵活，给参赛者的创新空间比较大一些，使得构建模型给参赛者的创新空间比较大一些，使得构建模型的目标函数表现形式很多，再加上模型求解方法的目标函数表现形式很多，再加上模型求解方法（算法）的多样性，从而可以呈现出五花八门的论（算法）的多样性，从而可以呈现出五花八门的论文。文。第4页，本讲稿共60页v不碰撞的标准为任意两架飞机的距离大于不碰撞的标准为任意两架飞机的距离大于8km;假设条件：假设条件：v飞机飞行的方向角调整幅度不应超过飞机飞行的方向角调整幅度不应超过 ；v（因飞机飞行的速度变化不大）所有飞机的飞行（因飞机飞行的速度变化不大）所有飞机的飞行 速度速度 v 均为均为800km/h;有时需要通过查阅文献、资料给出合理假设有时需要通过查阅文献、资料给出合理假设注：注：第5页，本讲稿共60页v进入该区域的飞机在到达区域边缘时，与区域内进入该区域的飞机在到达区域边缘时，与区域内 飞机的距离应在飞机的距离应在60km以上；以上；v最多需考虑六架飞机；最多需考虑六架飞机；v不必考虑飞机离开此区域后的状况。不必考虑飞机离开此区域后的状况。根据当年竞赛题目给出的数据，可以验证新进根据当年竞赛题目给出的数据，可以验证新进入的飞机与区域内的飞机的距离超过入的飞机与区域内的飞机的距离超过60公里。公里。根据当年竞赛题目给出的数据，可以验证区域根据当年竞赛题目给出的数据，可以验证区域内的飞机不超过架内的飞机不超过架(包括新进入的包括新进入的)。第6页，本讲稿共60页v个人的想法不同，队友之间争执不下的情况下，若时个人的想法不同，队友之间争执不下的情况下，若时间允许，都可一一写到论文中去，建立的模型一、模间允许，都可一一写到论文中去，建立的模型一、模型二型二；或者经讨论后，选择一个认为更合理的。或者经讨论后，选择一个认为更合理的。费时较多的是计算（那时侯是自己编程解费时较多的是计算（那时侯是自己编程解NLP）v现在看来，无论是构建模型，还是计算，都不太难。现在看来，无论是构建模型，还是计算，都不太难。v本例题未给出数据，将重点放在如何构建模型上本例题未给出数据，将重点放在如何构建模型上第7页，本讲稿共60页解：解：(1)不考虑飞机的尺寸，用点代表飞机；不考虑飞机的尺寸，用点代表飞机；(2)已在区域内的已在区域内的5架飞机按给定的方向角作架飞机按给定的方向角作 直线飞行，则必不会碰撞，也不会发生直线飞行，则必不会碰撞，也不会发生 意外；意外；(应该根据题目中所给出的数据简应该根据题目中所给出的数据简 单的单的 验证一下验证一下)(3)飞机调整方向角的过程可在瞬间完成飞机调整方向角的过程可在瞬间完成,(不不 计调整方向所花费的时间计调整方向所花费的时间)。为解决该问题，补充假设：为解决该问题，补充假设：第8页，本讲稿共60页变量、参数的符号假设变量、参数的符号假设（为了建模）（为了建模）在区域内飞行在区域内飞行飞飞时间（可以根据数据算出来）时间（可以根据数据算出来）第9页，本讲稿共60页说明：说明：用初等数学的知识即可完成，用初等数学的知识即可完成，思考：思考：在哪个时间段某两架飞机可能相撞？在哪个时间段某两架飞机可能相撞？In fact,我们只需考虑两架飞机我们只需考虑两架飞机同时同时在区域内在区域内飞行时的情况，也就是说，飞行时的情况，也就是说，才是同在区域内的状况。才是同在区域内的状况。记为记为第10页，本讲稿共60页根据题目条件，需计算第根据题目条件，需计算第 架飞机之间架飞机之间的的最短距离最短距离第11页，本讲稿共60页为此，我们可以给出原问题的模型如下：为此，我们可以给出原问题的模型如下：思考：思考：是否还有其他的表达形式？是否还有其他的表达形式？非线性规非线性规划模型划模型分别从目标函数和约束条件角度思考分别从目标函数和约束条件角度思考第12页，本讲稿共60页首先思考一下目标函数是否有其它的表达？首先思考一下目标函数是否有其它的表达？同学们首先想到的可能是同学们首先想到的可能是Oh,Sorry!有正有负有正有负抵消抵消第13页，本讲稿共60页最小一乘最小一乘 法法最小二乘最小二乘 法法 因最小一乘法带绝对值，不好计算，以上两式，因最小一乘法带绝对值，不好计算，以上两式，比较而言，后者较好。比较而言，后者较好。为为了了避避免免抵抵消消or第14页，本讲稿共60页有的队员这样考虑：有的队员这样考虑：令为令为 ,转化为二次规划转化为二次规划用到经验模型中确定参数的近似准则用到经验模型中确定参数的近似准则:就所有飞机而言，就所有飞机而言，让调整弧度最大的让调整弧度最大的即即尽可能小，尽可能小，Chebshavf 准则准则第15页，本讲稿共60页 全国数学建模竞赛开展之初全国数学建模竞赛开展之初,竞赛题大多竞赛题大多是优化类型的题目是优化类型的题目,那时的计算机性能没有现那时的计算机性能没有现在好在好,速度也没有现在快速度也没有现在快,因此在模型的计算因此在模型的计算方面花的培训时间比较多。方面花的培训时间比较多。虽然目前可供选择的软件比较多，但是必要虽然目前可供选择的软件比较多，但是必要的优化知识是必须掌握的。的优化知识是必须掌握的。第16页，本讲稿共60页其次讨论一下约束条件是否有其它表达？其次讨论一下约束条件是否有其它表达？若考虑区域内不发生碰撞若考虑区域内不发生碰撞(若时间允许，也可若时间允许，也可以考虑出了区域的情况，另外建模以考虑出了区域的情况，另外建模)、错层飞行、错层飞行(飞高或者飞低避免碰撞飞高或者飞低避免碰撞)，进行模型的进一步改，进行模型的进一步改进，重点应放在解决问题的方法上。进，重点应放在解决问题的方法上。第17页，本讲稿共60页第18页，本讲稿共60页 无论选择哪一种表达，怎样考虑约束条件，无论选择哪一种表达，怎样考虑约束条件，目标函数都不可能是线性的。目标函数都不可能是线性的。现在看来，那年的题目建模不难，只是在条件现在看来，那年的题目建模不难，只是在条件的考虑上和建模中目标函数的表达方面较难一点。的考虑上和建模中目标函数的表达方面较难一点。但在当时不然。但在当时不然。是一个带不等式约束的非线性规划问题。是一个带不等式约束的非线性规划问题。而且不可能转化成线性的形式。而且不可能转化成线性的形式。第19页，本讲稿共60页 若目标函数或约束条件中含有非线性函数，则称若目标函数或约束条件中含有非线性函数，则称这种模型问题为这种模型问题为非线性规划非线性规划（Non-Linear Prog-ramming），简记为），简记为NLP。NLP的一般形式的一般形式 其中，其中，中至少有一个是中至少有一个是 非线性函数。非线性函数。第20页，本讲稿共60页 无约束极值问题是无约束极值问题是NLP的一种特殊形式的一种特殊形式如如数据拟合的最小二乘问题就是一个无约束极值数据拟合的最小二乘问题就是一个无约束极值问题。问题。其思想是：观察点（实验数据点）到曲线的其思想是：观察点（实验数据点）到曲线的距离的平方之和最小距离的平方之和最小二、无约束极值问题二、无约束极值问题第21页，本讲稿共60页理论上无约束极值问题可化成求解理论上无约束极值问题可化成求解 即解一个即解一个 n 元方程组，且往往是非线性方程元方程组，且往往是非线性方程组。组。而一般说来，非线性方程组的求解并不比求而一般说来，非线性方程组的求解并不比求无约束极值容易。无约束极值容易。第22页，本讲稿共60页求解无约束极值问题的基本方法：求解无约束极值问题的基本方法：迭代法迭代法 从一个给定的初始可行点从一个给定的初始可行点 出发，依次出发，依次产生一个可行点列产生一个可行点列的一个极小值点的一个极小值点,恰好是恰好是使得某个使得某个基本思路：基本思路：或或收敛于收敛于,称具有这种性质的算法称具有这种性质的算法是是收敛的收敛的.第23页，本讲稿共60页由由迭代到迭代到时时,记记即即其中向量其中向量为为搜索方向搜索方向,实数实数称为称为步长步长,确定以后确定以后,由由可唯一地确定可唯一地确定从从出发就可确定点列出发就可确定点列第24页，本讲稿共60页迭代的方法很多迭代的方法很多,各种迭代法的区别在于选取各种迭代法的区别在于选取的方式不同的方式不同,而而尤为关键尤为关键.一般要求一般要求递减递减,具有这种性质的算法叫做具有这种性质的算法叫做下降下降算法算法.下面介绍的迭代法均为下降算法下面介绍的迭代法均为下降算法第25页，本讲稿共60页若已得若已得下降得最多下降得最多,并确定了并确定了的可行下降方向的可行下降方向上选取步长上选取步长则在射线则在射线使使且使且使即求即求求求的过程称为的过程称为一维搜索一维搜索.1.下降算法下降算法第26页，本讲稿共60页于是一维搜索归结为求解一维无约束极值问题于是一维搜索归结为求解一维无约束极值问题:其算法有其算法有Newton法、平分法、黄金分割法法、平分法、黄金分割法（0.618法）、分数法（法）、分数法（Fibonacci法）、抛物线法法）、抛物线法（二次插值法）等，（二次插值法）等，前两种算法需计算前两种算法需计算的导数，的导数，后三种算法只需计算后三种算法只需计算的函数值。的函数值。下面仅介绍下面仅介绍Newton法，对其他方法的了解可参法，对其他方法的了解可参考有关书籍。考有关书籍。第27页，本讲稿共60页按按 给定初始可行点给定初始可行点 和控制误差和控制误差 ，迭代格式迭代格式迭代，迭代，当当时，时，即求得即求得的最优解的近似解的最优解的近似解停止计算。停止计算。Newton 法介绍法介绍第28页，本讲稿共60页 一个好的算法必须以较快的速度收敛到一个好的算法必须以较快的速度收敛到最优解。最优解。设算法产生的点列设算法产生的点列收敛于最优解收敛于最优解若存在若存在及及使使则称则称为为 p 阶收敛的。阶收敛的。该算法也是该算法也是 p 阶收敛的。阶收敛的。第29页，本讲稿共60页 称为称为线性收敛；线性收敛；当当且且时，时，称为称为超线性收敛；超线性收敛；当当时，时，称为称为平方收敛；平方收敛；当当时，时，第30页，本讲稿共60页一个算法是否收敛，一个算法是否收敛，往往与往往与的选取有关的选取有关 若当若当充分接近充分接近时，时，由算法产生的点列由算法产生的点列才收敛于才收敛于则称该算法为具有局部收敛则称该算法为具有局部收敛性的算法；性的算法；若对若对则称该算法为具有全局收敛性的算法。则称该算法为具有全局收敛性的算法。由算法产生由算法产生 的点列的点列均收敛均收敛于于第31页，本讲稿共60页 Newton法是平方收敛的，具有局部收敛性；法是平方收敛的，具有局部收敛性；抛物线法是超线性收敛的，具有全局收敛性；抛物线法是超线性收敛的，具有全局收敛性；平分法、黄金分割法、分数法是线性收敛的，平分法、黄金分割法、分数法是线性收敛的，具有全局收敛性。具有全局收敛性。常见一维搜索算法的收敛性常见一维搜索算法的收敛性第32页，本讲稿共60页当当具有多个极小值点时，具有多个极小值点时，则算法求得则算法求得的往往是的往往是的一个局部极小值点。的一个局部极小值点。此时可此时可改变改变的取值，重新迭代求解。的取值，重新迭代求解。若求得多个极小值点，则从中选择一个若求得多个极小值点，则从中选择一个较满意的结果。较满意的结果。说明：说明：第33页，本讲稿共60页 在多数情况下，一维搜索的一个基本工具，在多数情况下，一维搜索的一个基本工具，而此时一维搜索的精度并不要求很高，故一维而此时一维搜索的精度并不要求很高，故一维搜索实现的方便性更重要些。搜索实现的方便性更重要些。第34页，本讲稿共60页 1847年年Cauchy提出了第一个无约束极值问题的算提出了第一个无约束极值问题的算法法梯度法或最速下降法：梯度法或最速下降法：其中其中给定初始点给定初始点和控制误差和控制误差求求当当时，时，即得即得的最优解的最优解的近似解的近似解停止计算。停止计算。2.梯度法梯度法第35页，本讲稿共60页 该算法具有全局收敛性，是线性收敛的，但有时该算法具有全局收敛性，是线性收敛的，但有时是很慢的线性收敛，这似乎与是很慢的线性收敛，这似乎与“最速下降最速下降”矛盾。矛盾。其实不然，最速下降方向函数在某点处的局部性质，其实不然，最速下降方向函数在某点处的局部性质，对局部来说是最速下降方向，对全局来说却不一定对局部来说是最速下降方向，对全局来说却不一定是最速下降方向，故梯度法不是有效的实用算法。是最速下降方向，故梯度法不是有效的实用算法。通过对它改进或利用它与其他收敛快的算法通过对它改进或利用它与其他收敛快的算法相结合可得相结合可得Newton法、法、Fletcher-Reeves共轭共轭梯度法、变尺度法和梯度法、变尺度法和Powell法法等有效算法。等有效算法。第36页，本讲稿共60页 下面仅介绍前两者，对后两者的了解可参阅有关下面仅介绍前两者，对后两者的了解可参阅有关书籍。书籍。当当时，时，则则 。其中其中称为称为在在 处的处的Hesse矩阵。矩阵。Newton法法第37页，本讲稿共60页 该算法是平方收敛的，具有局部收敛性。该算法是平方收敛的，具有局部收敛性。对对Newton法进行改进，可得具有超线性收敛的法进行改进，可得具有超线性收敛的且具有全局收敛性的且具有全局收敛性的阻尼阻尼Newton法法或或修正修正Newton法法：当当时，时，有有 。第38页，本讲稿共60页 Fletcher-Reeves共轭梯度法共轭梯度法当当时，时，有有 。该算法的收敛速度介于梯度法和该算法的收敛速度介于梯度法和Newton法法其中其中之间，既克服了前者的慢收敛性，又避免了之间，既克服了前者的慢收敛性，又避免了后者计算量大和仅具有局部收敛性的缺陷。后者计算量大和仅具有局部收敛性的缺陷。第39页，本讲稿共60页 求解无约束极值问题的算法非常多，不同算法求解无约束极值问题的算法非常多，不同算法的效果和实际效率也可能与所求解的问题有关，软的效果和实际效率也可能与所求解的问题有关，软件包中往往提供了多种算法。件包中往往提供了多种算法。后面将有教练专讲如何使用软件包求解非线性后面将有教练专讲如何使用软件包求解非线性规划问题。规划问题。第40页，本讲稿共60页 求解一般的求解一般的 NLP 比求解的无约束极值问题和比求解的无约束极值问题和 LP 都要复杂，虽然目前已发展了许多都要复杂，虽然目前已发展了许多 NLP 的算的算法，但不象法，但不象 LP 那样有通用的单纯形法，而是各那样有通用的单纯形法，而是各种算法都有特定的使用范围。即便如此，种算法都有特定的使用范围。即便如此，NLP 的实际应用还是相当广泛的。的实际应用还是相当广泛的。三、有约束极值问题三、有约束极值问题第41页，本讲稿共60页首先回顾首先回顾“NLP的一般形式的一般形式”其中，其中，中至少有一个是中至少有一个是 非线性函数。非线性函数。第42页，本讲稿共60页 由于无约束极值问题的求解目前已有许多有由于无约束极值问题的求解目前已有许多有效的算法，因此很自然想到把它们推广到有约束效的算法，因此很自然想到把它们推广到有约束的的 NLP，但存在不少困难，特别是对于非线性，但存在不少困难，特别是对于非线性约束，困难更大。约束，困难更大。（一）罚函数法（一）罚函数法 一种可行的方法是根据约束问题的求解，构造一种可行的方法是根据约束问题的求解，构造某种某种“惩罚惩罚”函数，把它加到目标函数中去，将约函数，把它加到目标函数中去，将约束问题的求解转化为一系列无约束问题的求解。在束问题的求解转化为一系列无约束问题的求解。在无约束问题处，无约束问题处，“惩罚惩罚”项必须趋于项必须趋于0，而约束条，而约束条件要近似地满足。件要近似地满足。第43页，本讲稿共60页1.外罚函数法外罚函数法令令通常取通常取称之为罚函数，称之为罚函数，则约束问题转化为无约束问题则约束问题转化为无约束问题其中其中 M 0 为罚因子为罚因子.显然显然,符合上述符合上述惩罚策略惩罚策略,即即第44页，本讲稿共60页 当当 为可行解时为可行解时,不受不受“惩罚惩罚”;当当 为非可行解时为非可行解时,M 越大越大,“惩罚惩罚”越重越重.因此因此,当当 M 充分大时充分大时,要使要使极小极小,则则 应充分小应充分小,从而从而的极小值点充分逼近可行域的极小值点充分逼近可行域,的最优解的最优解逼近逼近 的最优解的最优解.第45页，本讲稿共60页 给定给定 (可为非可行解点可为非可行解点),可以取小一些可以取小一些初始惩罚因子初始惩罚因子(如取如取 ),迭代过程迭代过程中中 M 不断增加不断增加,放大系数放大系数 c 1(可取可取 c=10).令令k=0,以以 为初始点求为初始点求 得得最优解最优解 若若则则 ;否则否则,令令以以 为初始点求为初始点求该算法所得该算法所得 是从可行域外部是从可行域外部故故 又称为又称为外罚函数法外罚函数法或或外点法外点法.趋于趋于第46页，本讲稿共60页说明说明v外罚函数的构造形式有多种外罚函数的构造形式有多种,迭代格式也有迭代格式也有 多种多种,目前有不少专家在做这方面的工作目前有不少专家在做这方面的工作;v对于最优解对于最优解 靠近边界的情况不太好靠近边界的情况不太好;v对保证在可行域内迭代很有效对保证在可行域内迭代很有效.第47页，本讲稿共60页而只是近似满足约束，而只是近似满足约束，这是某些实际问题不能这是某些实际问题不能“挡挡”在可行域内了在可行域内了.这种方法称为这种方法称为内罚函数法内罚函数法或或 外点法的每个迭代点外点法的每个迭代点 往往不是可行解往往不是可行解,接受的接受的.为使迭代点总是可行解为使迭代点总是可行解,在可行域的在可行域的 边界筑起一道边界筑起一道“墙墙”，当迭代点靠近边界时，目标当迭代点靠近边界时，目标 函数值陡然增大，以示惩罚，于是迭代点就被函数值陡然增大，以示惩罚，于是迭代点就被内点法内点法.只适用于只适用于不等式约束不等式约束问题问题2.内罚函数法内罚函数法第48页，本讲稿共60页当当 从可行域内部趋于边界时从可行域内部趋于边界时,至少有某个至少有某个内罚函数：内罚函数：趋于趋于0,无限增大无限增大.于是所求解的有于是所求解的有约束问题转化为求解如下的无约束问题约束问题转化为求解如下的无约束问题其中其中 r 0 为罚因子为罚因子.可实现上述可实现上述“惩罚惩罚”第49页，本讲稿共60页而而 r 很小很小,几乎不受惩罚几乎不受惩罚;策略，即策略，即 无限增大，无限增大，当当 为可行域的内点时，为可行域的内点时，为有限正数，为有限正数，施以重罚施以重罚,迫使迭代点落在可行域内，迫使迭代点落在可行域内，的最优解的最优解.当当 接近可行域的边界时，接近可行域的边界时，最终逼近最终逼近第50页，本讲稿共60页 给定初始可行点给定初始可行点 ,初始惩罚因子初始惩罚因子(可取可取 ),缩小系数缩小系数 0 c 1令令 k=0,以以 为初始点求为初始点求 得最优解得最优解 .若若则则 ;否则否则,令令以以 为初始点求为初始点求(可取可取 c=0.1).缩小到原缩小到原来的来的1/101/10控制在误差范围之内，控制在误差范围之内，从而使得从而使得之间的误差也在控制之间的误差也在控制范围内范围内第51页，本讲稿共60页困难的。困难的。因此可将内点法和外点法结合起来使用，因此可将内点法和外点法结合起来使用，外点法，外点法，内点法，即令内点法，即令 内点法要求内点法要求 为可行域的内点为可行域的内点,有时这是很有时这是很得到所谓的得到所谓的混合罚函数法。混合罚函数法。那些不等式约束用那些不等式约束用3.混合罚函数法混合罚函数法当给定当给定 后，对后，对等式约束和不被等式约束和不被 满足的满足的 而对被而对被 满足的那些不等式约束用满足的那些不等式约束用第52页，本讲稿共60页为简便为简便起见，起见，取平方取平方其其中中r 充分小，充分小，1/r 充分大，充分大，这样少用一这样少用一个参数个参数第53页，本讲稿共60页罚函数法中的罚因子的选取对方法的收敛快慢罚函数法中的罚因子的选取对方法的收敛快慢有较大影响，尤其是当有较大影响，尤其是当M不断增大和不断增大和r不断减少不断减少时，时，越来越越来越“病态病态”，使得，使得求解无约束问题很困难。为此，人们提出了许多求解无约束问题很困难。为此，人们提出了许多改进的方法，其中最有效的是改进的方法，其中最有效的是“乘子法乘子法”。需要。需要详细了解时参阅相关书籍。详细了解时参阅相关书籍。4.其他方法其他方法第54页，本讲稿共60页 罚函数法要用到目标函数和约束函数的偏导数，而某罚函数法要用到目标函数和约束函数的偏导数，而某些实际问题中出现的函数很复杂，甚至难以解析表达，些实际问题中出现的函数很复杂，甚至难以解析表达，无法求得函数的偏导数，此时常用直接法无法求得函数的偏导数，此时常用直接法(主要跟函主要跟函数的函数值打交道数的函数值打交道)。这一类方法一般算法简单，直观性强，对函这一类方法一般算法简单，直观性强，对函数无特殊要求，但计算量随维数和约束条件数的数无特殊要求，但计算量随维数和约束条件数的增加而成指数增大，故增加而成指数增大，故对维数低、函数复杂、要求对维数低、函数复杂、要求精度不高的问题较适用精度不高的问题较适用。（二）网格法（二）网格法第55页，本讲稿共60页 对有约束问题，假定已知变量的取值范围，对有约束问题，假定已知变量的取值范围，若无上、下界约束，则可根据问题的性质估若无上、下界约束，则可根据问题的性质估计一下最优解所在范围。计一下最优解所在范围。最简单的一种直接方法就是最简单的一种直接方法就是网格法网格法，它是，它是在区域在区域上打网格，网格等间距与否皆可，求网格点的约上打网格，网格等间距与否皆可，求网格点的约束函数和目标函数值，比较满足约束条件的点的束函数和目标函数值，比较满足约束条件的点的目标函数值的大小，从中选择小的。目标函数值的大小，从中选择小的。第56页，本讲稿共60页网格的间距是要求的解的误差上限，若网格的间网格的间距是要求的解的误差上限，若网格的间距超过控制误差，则在求出的点附近加密网格再距超过控制误差，则在求出的点附近加密网格再求。否则，便求得了近似最优解。求。否则，便求得了近似最优解。网格法遍历全部网格点才能得出极小值点的网格法遍历全部网格点才能得出极小值点的大体位置。如果考虑不是这样有规律地取试验点，大体位置。如果考虑不是这样有规律地取试验点，而是随机地选取试验点，即使只计算预定点数的而是随机地选取试验点，即使只计算预定点数的一部分，只要这部分点在区域一部分，只要这部分点在区域E中是均匀分布，则中是均匀分布，则对对 f(x)在在E 中的大致形态能有所了解。在中的大致形态能有所了解。在E中投中投入一定量的试验点后，往往发现较好的点集中在入一定量的试验点后，往往发现较好的点集中在E的某一部分，因此，可将的某一部分，因此，可将（三）随机试点法（三）随机试点法第57页，本讲稿共60页E 缩小后再重复上述过程。通过不断收缩缩小后再重复上述过程。通过不断收缩E来求极来求极小值点。这就是随机试验法的基本思路。小值点。这就是随机试验法的基本思路。此外，求解一般非线性规划还有此外，求解一般非线性规划还有序列线性规划法、序列线性规划法、可行方向法可行方向法以及最有效的算法之一的以及最有效的算法之一的广义简约梯广义简约梯度法（度法（GRP法）。法）。Goldfarb投影梯度法投影梯度法是求解是求解线性约束的线性约束的NLP的最有效的算法之一，的最有效的算法之一，Wolf算法算法是求解目标函数为二次函数而约束条件为线性函数是求解目标函数为二次函数而约束条件为线性函数的二次规划的最有效的算法。可参阅有关书籍。的二次规划的最有效的算法。可参阅有关书籍。第58页，本讲稿共60页 NLPNLP也可用也可用 Lingo Lingo 或或 Matlab Matlab（优化工具（优化工具箱）软件求解，但其结果往往依赖于初值的箱）软件求解，但其结果往往依赖于初值的选择。选择。第59页，本讲稿共60页第60页，本讲稿共60页