简单百科
非线性规划

非线性规划

非线性规划（Nonlinear programming）是最优化问题中具有非线性约束条件或目标函数的最优化，是论述一个目标函数在等式约束和不等式约束之下的最优化问题，被用来识别和计算多个变量的非线性函数的最优解。非线性规划是运筹学和最优化的一个重要分支，它的研究对象是非线性函数的数值最优化问题，主要研究求解多元函数问题的有关数学理论和算法，包含凸规划、二次规划、几何规划等规划问题。

“非线性规划”一词最早是由美国数学家哈罗德·威廉·托马斯·库恩（Harold William Kuhn）和加拿大数学家阿尔伯特·威廉·塔克（Albert William Tucker）在1950年提出的。到1951年，Kuhn-Tucker条件的建立，可以看作是非线性规划近代理论和方法研究的开始。第二次世界大战后，近代科学技术发展，非线性规划也得到了快速发展，新的理论和算法不断出现。如1959年提出的变尺度法、1960年提出的可行方向法，还有共轭梯度法、拟牛顿法、乘子法等。综合近现代算法，在求解非线性规划问题可以使用分析方法如数学分析模型，数值方法如一维搜索法、直接法、解析法。

在应用方面，非线性规划为系统的优化和管理提供了有用的工具，能在自然科学、工程、经济、工程设计、过程控制、经营管理等诸多领域提供强有力的数学工具。

定义

非线性规划是统筹学和最优化的一个重要分支，它的研究对象是非线性函数的数值最优化问题。如果一个最优问题的解不随时间变化，这个最优问题称作“静态最优或非线性规划”，它是通过数学模型的代数方程或超越方程来表达。

在最优化问题中，有一些数学模型具有如下结构：

第一是变量。即所考察的问题可归结为优选若干个称为参数或变量的量，这些变量都取实数值，可用中的维向量简记。

第二是约束。设问题中对变量所加的限制或约束可以用这些变量满足的如下等式和不等式表示出来：

第三是目标。设最优化问题的目的是在约束限制下确定变量的取值，使得某个个实函数取到极大值或极小值，或是最大值或是最小值。称为这一最优化问题中的目标函数。

根据上述结构得出如下数学规划（Mathematical Programming）：

其中定义于某个维区域，记号min意为极小化，是subject to的缩写，意为“受约束于”。满足所有约束的向量称为问题的可行解。所有可行解的全体组成可行域。非线性规划问题，则是寻找一个可行点使得对每一可行点有，这样的点称为该问题的最优解。

当全为的线性函数时，最优化便是线性规划（Linear Programming）；否则，即目标函数、约束函数中至少有一个不是的线性函数时，数学规划便称为非线性规划。若是去掉（MP）的约束条件，则称（MP）为无约束最优化问题。因此，也称问题（MP）为约束最优化问题。在约束优化问题中，如果只有等式约束，则称为等式约束优化问题。另一种特殊情形是所有的约束条件都是线性函数，这时便称为线性约束优化问题。等式约束、不等式约束或无约束的问题都划归为非线性规划问题。

在实际问题中，其目标函数或约束条件中含有非线性函数，就称这种规划问题为非线性规划问题，而解决这种问题就需要非线性规划的方法。由于非线性数值最优化问题是最优化研究中重要的中心课题，因此，通常的所谓最优化理论主要即指非线性规划理论，而最优化方法也主要是指非线性规划的求解方法。

非线性规划具有广泛适用性，可以通过建立非线性规划问题求解最优控制、结构设计、机械设计、电网络、水资源管理、随机资源分配、设施位置等最优化问题。

简史

古典时期

早在17世纪，英国科学家艾萨克·牛顿（Isaac Newton）创立微积分的时代，就已提出极值问题。后来法国数学家约瑟夫·拉格朗日（Joseph Louis Lagrange）研究一个函数在一组等式约束条件下的极值问题时提出了乘数法。从瑞士数学家莱昂哈德·欧拉（Leonhard Euler）和拉朗格日那时起，带等式约束的非线性规划理论就为人们所知。

到1847年，法国数学家奥古斯丁·路易斯·奥古斯丁-路易·柯西（Augustin Louis Cauchy）研究了函数值沿什么方向下降最快的问题，并提出了沿着负梯度方向寻找非线性函数极小点的方法(最速下降法)，而后牛顿法也应用到非线性规划，并在1948年被苏联经济学家列奥尼德·康托罗维奇（Leonid Kantorovich）推广到无穷维空间的非线性映射方程的求解中。

分析时期

1939年，美国数学家威廉·卡鲁什（William Karush）已经用一种相当令人满意的方式处理不等式约束的情况。但不幸的是，卡鲁什的工作大大被忽略了。他所使用的约束规格与托马斯·库恩和塔克所使用的是一样的。在卡鲁什后，但仍在库恩和塔克前，德裔美籍数学家弗里茨·约翰（Fritz John）就已经考虑过不等式约束的非线性规划问题并提出了约翰条件。

而后三十年代中期以来，塔克一直对张量计算中协变和反协变、组合拓扑中下同调和上同调之间的对偶性感到兴趣。1948年5月，美国数学家乔治·丹齐格（George Bernard Dantzing）在普林斯顿大学拜访了美国数学家约翰·冯·诺依曼（John Von Neumann），讨论了当时新兴的线性规划和博弈论之间潜在的联系。这次访问，促使他们研究线性规划和矩阵博弈之间的关系。同时，英国经济学家大卫·盖尔（David Gale）、托马斯·库恩和塔克也参与其中，并证明了线性规划的对偶性定义。

1949年，库恩把线性规划的对偶性作为Lagrange公式的一个鞍点性质表示出来。这个鞍点问题后来被选为讲解Kuhn-Tucker理论分析的出发点。几个数学家在对联性、网格理论和线性规划得到启发，对与最优化相邻近的一些学科的数学结构进行深化，并在凸分析、非线性系统分析和求解最优化问题的算法等课题中获得显著成就。

现代时期

二十世纪40年代前，对于最优化往往只能进行一些最小二乘计算，或对某些物理问题用到最速下降类型的梯度法。直到40年代中期，随着电子计算机的出现，在非线性规划方面出现了与问题的具体结构无关，并得到广泛应用的“爬山法”。20世纪50年代初，Kuhn-Tucker条件的建立，被看作是非线性规划近代理论和方法研究的开始。

第二次世界大战后，近代科学技术的发展，特别是电子计算机技术的飞速发展促进了最优化的迅速发展，出现了很多有效算法。如1959年，美国物理学家威廉·克莱德·戴维登（William Clyde Davidon）提出变尺度法，并由苏格兰大学数学系教授罗伊·弗莱彻（Roy Fletcher）和英国数学家迈克尔·詹姆斯·戴维德·鲍威尔（Michael James David Powell）在1963年加以简化。1960年荷兰数学家盖尔·祖腾迪克（Gerrit Zoutendijk）提出可行方向法，同年美国统筹学专家詹姆斯·B·罗森（James B Rosen）提出梯度投影法。1963年德国运筹学专家沃尔夫（Peter Wolf）提出既约梯度法，1964年罗伊·佛莱彻，英国数学家克里斯托弗·M·里弗斯（Christopher Michael Reeves）给出共轭梯度法，同年鲍威尔提出Powell方法。1969年美国哥伦比亚大学教授唐纳德·戈德法布（Donald Goldfarb）给出DFP变尺度法等等。

20世纪60年代后，这门新兴的基础学科便渗透到各个技术领域，形成了最优化与技术这门应用学科，并在此基础上，运筹学逐渐发展出了新的更细的研究分支——非线性规划。非线性规划作为运筹学的一个重要研究分支在近20年得到了快速发展。

非线性规划问题解决方法

分析方法

非线性规划的分析，是在建立一个体现所考察决策问题的数学模型过程后，对数学模型进行分析，并选择一个适当的求最优解的数值方法。非线性规划的数值解法依赖于目标函数和约束的性质以及最优化问题的结构。因此，在分析的基础上，决策者在现有数值解法中能确定哪一种能求得最优解。

非线性规划的分析，对于问题的结构提供了有价值的观察，并回答了关于能行决策和最优决策的存在性与特征性质问题。

数值方法

数值分析法内容包括解非线性方程组的理论与方法，常用的方法如Newton型方法，同伦延拓法，单纯形算法等。

讨论非线性最优化问题的数值解法，首先介绍无约束最优化方法的研究，包括不用导数的方法、共轭方向法和变尺度方法等。对于有约束非线性规划来说，惩罚函数法、无约束方法的扩充和近似型算法，皆属于最为广泛使用的或者最近发展起来并被认为有发展前途的算法。

一维搜索方法

一维搜索方法是研究非线性规划方法的重要基础。一维搜索方法是指，在求解非线性规划的方法研究中，求解只有一个决策变量的非线性规划问题。或在大多数无约束极值的算法中，为了确定极小化点列，要沿逐次确定的一系列射线求极小点，即所谓的一维搜索。而这实际上就是求一元函数的极小点问题。

一维搜索的方法很多，常用的有：

（1）0.618法：又称黄金分割法。由于任一斐波那契分数和0.618都是黄金分割数的近似值，所以斐波那契法和0.618法都是近似黄金分割法。由此，它们都具有近似黄金分割法所具有的在每一有限轮迭代时的最优性。

0.618法步骤如下：

第1步，选取初始数据。确定单谷区间，给出最后区间精度。

第2步，计算最初两个探索点。取按计算。

求，令。

第3步，比较目标函数值。若，进行第4步。否则，进行第5步。

第4步，向左搜索。若，停止迭代输出。否则，令，。求，令。令转第3步。

从0.618法求解的过程容易知道，此法从第2个探索点开始每增加一个探索点作一轮迭代之后，原单谷区间要缩短0.618倍。由于0.618法至多只能取10个探索点，所以它最多只能把最初的单谷区间的长度缩短成

因此，在使用0.618法时，精度只能要求取不小于的数，否则求解将是没有意义的。

下面给出0.618法框图

（2）裴波那契法（Fibonacci法）：又称分数法，是不断缩短函数的单股区间[a，b]的办法，来求得问题的近似最优解。这个求解的一维搜索方法是美国数学家杰克·基弗（Jack Kiefer）1953年提出的。

（3）插值法，用插值多项式来近似表达连续函数，即，把的极小值点作为的极小值点近似，解并判断，即得的极小值点的近似。通常取为二次或三次多项式，即得二次或三次插值法。

（4）切线法。牛顿法的基本思想是将非线性方程组逐次线性化，从而形成迭代算法。

无约束极值最优化问题方法

求解无约束极值问题时常使用迭代法，迭代法可大体分为两大类。一类要用到函数的一阶导数和（或）二阶导数，由于用到了函数的解析性质，故称为解析法；另一类在迭代过程中仅用到函数值，而不要求函数的解析性质，这类方法称为直接法。

属于解析法的有：

（1）最速下降法：又称梯度法，是从搜索点沿负梯度方向进行一维搜索，形成迭代过程。是求多变量函数极小问题的最早方法。

（2）共轭梯度法：一个完整的无约束极小化算法称为共轭梯度法，其基础是美国数学家马格纳斯·R·赫斯滕斯（Magnus R.Hestenes）、瑞士数学家爱德华·L·斯蒂费尔（Eduard L.Stiefel）为求解线性方程组提出的一个方法。

共轭梯度法的基本思想是在共轭方向法和最速下降法之间建立某种联系，以求得到一个既有效又有较好收敛性的算法。

属于直接法的有：

（1）交替方向法：最早的也是最简单的直接方法。它利用个坐标轴方向进行一维搜索。

（2）单纯形法：是另一个较早的直接方法。它的基本思想是：在每次迭代时利用已有的单纯形去寻找一个函数值更小的点。如果得到这样一个更好的点，则利用这个新点作为一个顶点构造新的单纯形。否则的话，将已有单纯形缩小重复迭代。

（3）共轭方向法：由定理3.4.3及推论，如果第k次迭代所取的方向与以前各次迭代所取的方向关于共轭，则从任意初始点出发，对二次函数作精确一维搜索，至多经过次迭代就可得到极小点。

（4）差分拟牛顿法：是用差商代替导数的拟牛顿法，是共轭方向法以外的另一类有效的直接方法。

（5）方向加速法（Powell法）：在不依赖于目标函数梯度的所有直接搜索法中，方向加速法是最有效的。它的基本出发点是利用§4性质（ii）去逐次构造共轭方向，并以此为搜索方向，去构成搜索算法。因此，从本质上讲方向加速法亦是共轭方向法。

约束极值最优化问题方法

实际工作中遇到的大多数极值问题，其变量的取值多受到一定限制，这种限制由约束条件来体现。带有约束条件的极值问题称为约束极值问题，也叫规划问题。

通常将约束问题化为无约束问题，将非线性规划问题化为线性规划问题将复杂问题变换为较简单问题来求解约束极值问题。

常用的方法有：

（1）罚函数法：罚函数法是求解一般约束最优化问题的重要方法。罚函数法，简记为SUMT（Sequential Unconstrained Minimizaton Technique），是根据约束的特点，构造某种“惩罚”函数，然后把它加到目标函数中去，将约束问题的求解转化为一系列无约束问题的求解。

一般来讲，制约函数常见的大致有这样两类，一是“惩罚函数”，另一种是“障碍函数”。对应这两种函数的不同特点，SUMT又可分为外点法和内点法。

外罚函数法：又称SUMT外点法。它对违反约束的点，在目标函数中加入惩罚项，而对可行域内的点不予惩罚。此法的迭代点一般在可行域外移动，随一个无约束问题求解转到另一个无约束问题的求解，相应的惩罚参数逐次加大，从而迫使迭代点像可行域靠近，并由此产生非可行点的序列。它的任一收敛子序列的极限是原来约束问题的一个最优解。

内罚函数法：为使迭代点始终保持在可行域内移动，可以使用这样的“惩罚策略”：在可行域的边界上筑起一道很高的“围墙”，当迭代点靠近边界时，目标函数陡然增大，以示惩罚，组织迭代点穿越边界，这样就可以把最优解“挡”在可行域内。这样的方法称为内罚函数法。

（2）可行方向法：可行方向法是通过从一个可行点移动到一个改进的可行点的方法。如近似线性化法、Zoutendijk法、罗森投影梯度法、沃尔夫简约梯度法等都属于此类算法。

下面的策略是典型的可行方向算法，因此这些方法通常称为原始方法：

给出一个可行点，确定一个方向，使得对充分小的下面的两条性质成立：①是可行的；②在的目标值比在的目标值好。在确定这样的方向以后，为了决定沿前进多远，必须求解一个一维最优化问题，这样导致一个新点，并重复这一过程。

（3）线性逼近法：线性逼近法是将非线性规划问题线性化，通过解线性规划来求解原问题的近似解。通过不同的方式形成线性规划可以得到不同的线性逼近法。如近似中华人民共和国城乡规划法是将原问题的目标函数和约束函数线性化，并对变量的取值范围加以限制，从而得到线性近似规划，再用单纯形方法解此线性规划，把其最优解作为原问题解的近似。每得到一个近似解后，再从这出发，重复以上步骤。通过解一系列线性规划，产生一个由线性规划最优解组成的序列。经验表明，这样的序列往往收敛于原非线性规划问题的解。

还有另一种典型的线性逼近法是割平面法。割平面法针对凸规划问题用多面集取代非线性规划的可行域，并在多面集上求解一系列不断改进的线性规划，使它们的解收敛于原问题的解。

（4）乘子法：等式约束问题乘子法计算步骤如下：

Step1：给定初始点，乘子向量初始估计，参数，允许误差，常数，置

Step2：以为初点，解无约束问题得解

Step3：若，停止计算，得到；否则，进行步Step4

Step4：若则置，转到Step5；否则，进行Step5

Step5：用公式计算，置，转Step2

拓展应用

物理

随着物理科学的发展，人们研究的物理问题体系越来越大，而最优化提供了一种有效的数学工具。最优化方法几乎遍及理论物理和实验物理中的各个领域。例如，在物理问题中，如何用一个含有多个可调参量的理论模型模拟一个实验现象或物理体系，并且逼近实际状态的过程。具体而言，在物理研究中最常碰到的问题就是用一个含有若干个参量的理论表达式去拟合实验曲线，就需要通过一定的数学规律调整这些参量，达到最小误差，搜索出最终最优解。

物理问题研究中应用最优化方法主要包括两个方面：从物理问题构造数学模型——确定目标函数和搜索变量以及确定求解数学模型的数学方法。

经济

背包问题

线性规划在经营管理中应用十分广泛，但当问题中的各有关的量不全是简单的比例关系时，就会出现非线性规划问题。如经典的背包问题：一个人带一个背包上山，背包可携带物品的总质量为。现有种物品，第种物品每件的质量为，若带件第种物品，则可获价值为，试问带哪几件物品各多少件，才能使获得的总价值最大？求解类似经营计划决策问题，需要构建类似背包问题的数学模型，并用非线性规划的方法求解。

石油分配

如何合理的将全国各油田提供的可加工的原油分配给各炼油厂，炼油厂如何选择合适的加工方案生产各种所需产品以及如何将各油厂的石油产品合理的调运到各消费区，使得总的运费最小、生产成本低、国家收益最大呢？该问题可分为两个部分来考虑，第一部分是根据各油田与炼油厂的地理位置、原油的品种、炼油厂的加工能力和工艺装备组成，把全国各油田提供的可加工原油分配给炼油厂进行加工，并选择各炼油厂的生产方案，要求原油运费省，炼油厂生产成本低，收益大。第二部分是将炼油厂生产的石油产品运往消费区（包括出口点），要求满足各消费区的需求，产品总运费低，运输流向合理。

根据问题要求，第一部分建立生产子模型，第二部分建立运输子模型。将这两个子模型合起来就成为石油产品生产运输模型，并通过非线性规划求解得到其最优值。

工程设计

非线性规划方法是工程设计中不可缺少的重要方法和手段。在工程技术问题中，如何使研制对象（一个工程或一个产品）在一定的客观条件下质量最佳，成本最低，效率最高，亦即最优的性价比，这些问题的求解就是一个最优化问题。优化过程有3个方面，即最优设计（静态优化问题）、优化控制（动态优化问题）和优化管理（方法问题）。对于水泥工业生产中的工程系统来说，无论是在设计过程中，还是在工业控制过程和生产管理过程中，总是存在许多可供优化的问题。另外，对于一些工程设计中所遇到的不确定的因素或问题，往往也可以借助于非线性规划方法进行解决或定量地分析和处理。

如在船舶方案设计中，由于船舶设计工作中充满着各种错综复杂的矛盾，这种估算校核的工作要经过多次反复，才能得到一个比较特合要求的设计方案。因此，非线性规划运用到船型方案设计中：首先根据设计船舶的具体要求确定设计变量、目标函数及约束条件，构造出描述有关技术及经济性能的数学模型；其次运用“运筹学”中有约束条件的非线性规划问题的罚函数算法、多目标决策问题的分层序列算法，结合MATLAB强大的“最优化 Toolbox”进行优化计算；最后通过航区内3种库型船的实际营运效果的对比得出船型方案优劣结果。

非线性规划

定义

简史

古典时期

分析时期

现代时期

相关概念

凸集和凸函数

梯度和Hesse矩阵

Taylor展开

Kuhn-Tucker条件

Lagrange乘子法

相关类别

凸规划

二次规划

几何规划