非线性规划的求解方法

在实际问题中，其目标函数和（或）约束条件很难用线性函数来表示。如果目标函数或约束条件中包含有非线性函数，称这种规划问题为非线性规划。一般说来，解非线性规划问题比解线性规划问题困难得多，而且也不像线性规划有单纯形法这一通用方法，非线性规划问题则需要根据不同问题的特点选用不同的有效的优化算法。非线性规划的一般模型可描述为

非线性规划分为无约束非线性规划和约束非线性规划两种情况。它们分别有多种求解方法，具体归纳见表4-1和表4-2[17]。

表4-1　无约束非线性规划的主要求解方法

表4-2　约束非线性规划的主要求解方法

续表

① 可分函数指一个函数可以表示为单变量函数之和。(www.xing528.com)

可以看出，求解非线性规划问题的优化方法可归纳为两类，一类为确定性优化方法，比如常用梯度法、复合形法和枚举法等，这些方法都存在不足，如梯度法它要求目标函数的一阶或二阶导数存在，且当初始点选择不当时还可能陷入局部最优点，再则对于复杂的多峰问题，梯度法寻优则十分困难以致无效。复合形法则需要可行域为凸的。而枚举法的主要缺点则是寻优效率低，且存在“维数灾”；另一类则是随机性优化法，它是通过随机变量的大量抽样，以得到目标函数的变化特性，然后逐渐逼近最优点，该方法只要求目标函数和约束条件可计算都能进行，寻优范围大，但属盲目寻优，计算量大且搜索效率低[18]。为了克服上述问题，产生了许多新的模拟生物进化过程的进化算法，比如Holland教授1962年提出了基于生物进化特性的遗传算法，通过选择、杂交和变异操作计算反复进化迭代，优胜劣汰，最终不断逼近最优点，遗传算法是一种并行非数值算法，能很好地处理非连续、多峰和非凸的优化问题[19]。又如，作者受生物免疫原理的启发提出的免疫进化算法[20～22]。这些新的方法不仅克服了传统方法的不足，而且对目标函数和约束条件函数没有连续、可微的要求，是复杂非线性规划问题求解的有效方法。有关遗传算法和免疫进化算法的原理和算法将在相关章节详细介绍。