非线性规划

非线性规划（nonlinear programming）

　　非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。

　　公元前 500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为0.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是 最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。

　　最优化方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。

• ① 解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。
• ② 直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常 根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。
• ③ 数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。
• ④ 其他方法：如网络最优化方法等。

　　根据函数的解析性质，还可以对各种方法作进一步分类。例如，如果目标函数和约束条件都是线性的，就形成线性规划。线性规划有专门的解法，诸如单纯形法、解乘数法、椭球法和卡马卡法等。当目标或约束中有一非线性函数时,就形成非线性规划。当目标是二次的,而约束是线性时，则称为二次规划。二次规划的理论和方法都较成熟。如果目标函数具有一些函数的平方和的形式，则有专门求解平方和问题的优化方法。目标函数具有多项式形式时，可形成一类几何规划。

　　非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩·塔克条件)的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法,它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有 广泛的应用，为最优设计提供了有力的工具。

　　第二次世界大战前后，由于军事上的需要和科学技术和生产的迅速发展，许多实际的最优化问题已经无法用古典方法来解决，这就促进了近代最优化方法的产生。近代最优化方法的形成和发展过程中最重要的事件有：

• 以苏联康托罗维奇和美国G.B.丹齐克为代表的线性规划；
• 以美国库恩和塔克尔为代表的非线性规划；
• 以美国R.贝尔曼为代表的动态规划；
• 以苏联庞特里亚金为代表的极大值原理等。

　　这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用

　　对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系,称之为目标函数。然后将各种限制条件加以抽象,得出决策变量应满足的一些等式或不等式，称之为约束条件。非线性规划问题的一般数学模型可表述为求未知量x1,x2,…,xn,使满足约束条件：

• gi(x1，…，xn)≥0　i＝1,…,m
• hj(x1，…，xn)＝0　j＝1,…,p

　　并使目标函数f(x1，…,xn)达到最小值(或最大值)。其中f，诸gi和诸hj都是定义在n维向量空间Rn的某子集D(定义域)上的实值函数,且至少有一个是非线性函数。

　　上述模型可简记为：

• min f(x)
• s.t. gi(x)≥0　i＝1,…,m
• hj(x)＝0 j＝1,…,p

　　其中x＝(x1，…,xn)属于定义域D，符号min表示“求最小值”，符号s.t.表示“受约束于”。

　　定义域D中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解x*,如果存在x*的一个邻域，使目标函数在x*处的值f(x*)优于(指不大于或不小于)该邻域中任何其他可行解处的函数值，则称x*为问题的局部最优解（简称局部解）。如果f(x*)优于一切可行解处的目标函数值,则称x*为问题的整体最优解（简称整体解）。实用非线性规划问题要求整体解，而现有解法大多只是求出局部解。

一维最优化方法 　

　　指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。

• ① 黄金分割法：又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。
• ② 切线法：又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。
• ③ 插值法：又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。

　　此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。

无约束最优化方法 　

　　指寻求 n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。

　　无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数,称为解析法。另一类不涉及导数，只用到函数值,称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向,沿这个方向进行一维寻查,得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：

• ① 梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。
• ② 牛顿法：收敛速度快，但不稳定，计算也较困难。
• ③ 共轭梯度法：收敛较快，效果较好。
• ④ 变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。

　　属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。

约束最优化方法

　　指前述一般非线性规划模型的求解方法。常用的约束最优化方法有四种。

• ① 拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。
• ② 制约函数法：又称系列无约束最小化方法，简称SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。
• ③ 可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克－沃尔夫法、投影梯度法和简约梯度法都属于此类算法。
• ④ 近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。

凸规划

　　这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸gi都是凹函数,诸hj都是一次函数，则称之为凸规划。所谓f是凸函数,是指f有如下性质：它的定义域是凸集,且对于定义域中任意两点x和y及任一小于1的正数α，下式都成立：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　f((1-α)x +αy)α≤(1-α)f(x)+αf(y)

　　将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。

二次规划

　　一类特殊的非线性规划。它的目标函数是二次函数，约束条件是线性的。求解二次规划的方法很多。较简便易行的是沃尔夫法。它是依据库恩·塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。

几何规划

　　一类特殊的非线性规划。它的目标函数和约束函数都是正定多项式（或称正项式）。几何规划本身一般不是凸规划，但经适当变量替换，即可变为凸规划。几何规划的局部最优解必为整体最优解。求解几何规划的方法有两类。一类是通过对偶规划去求解；另一类是直接求解原规划，这类算法大多建立在根据几何不等式将多项式转化为单项式的思想上。

　　非线性规划在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费最小；如何安排库存储量，既能保证供应，又使储存费用最低；如何组织货源，既能满足顾客需要，又使资金周转最快等。对于静态的最优化问题，当目标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可应用非线性规划的方法去处理。