计算机求解问题的实用指南

1.3.3.1　选择最优化方法的原则

各种方法都有其各自的优缺点，选择最优化方法总的原则是：

1）尽可能多地使用可以合理提供的导数信息，使用的信息越多，方法的效果越好。当然这里所指的合理性很重要，如果导数计算不方便，那么随着复杂性的增加，可靠性就会降低，就需使用不需要导数值的方法。

例如，根据这条原则，在选择无约束最优化方法时选用的次序为：牛顿型、拟牛顿型（变尺度型）、共轭梯度型、不用导数的直接法（例如单纯形搜索法等）。当然方法的适用范围的大小，其次序与上述的正好相反。

2）尽可能使最优化问题的结构特征得到最大利用。

例如，对大规模问题，首先考虑它是否具有稀疏性。若有，则尽可能地采用稀疏离散Newtown法那一类方法；否则选用共轭梯度型的方法。

又如，选择约束非线性问题的解法时，首先要考虑问题的本身是否要求迭代点必须为可行点。

3）根据可靠的计算软件的可得性及工程问题的时间紧迫性选用不同算法。

如果单纯是为了某个具体问题的应用，一般都选用市场或计算机程序库的成熟软件，这样可节省大量开发软件的时间，如果得不到现成的软件，工程的时间要求又很紧迫，这时可选用容易编制与调试程序的算法，例如Monte Carlo方法等。

1.3.3.2　选择算法时应考虑问题的哪些特性？

要考虑的主要几点为：变量数、变量的取值范围、问题中函数的可微性、函数与导数值计算的有效性、大规模问题的稀疏性、约束数与变量数的比较，以及是否出现非线性等式约束、问题的函数在可行域之外值是否可求、是否有意义。

1.3.3.3　选用专用方法还是通用方法

从概念上讲，专用技术的计算速度、精度等方面，通常是优于通用方法的，因而，如果需要反复求解相同类型的问题，就应该考虑采用专用技术。但是，对于只解一次的问题来说，把它作为一个具有特殊结构的问题用专门的方法求解，从由研究问题具有何种特殊结构、选用有关的专用算法、准备相应的程序与所需的输入数据、上机计算等构成的解题全过程来看，可能要比作为一个一般问题用通用方法求解，耗费工程技术人员更多的时间、精力与费用。

1.3.3.4　开始要尽量简单

解题应当从简单的数学模型和程序做起，在简单的情形已能正常工作后，逐步增加复杂性。这样的做法比较容易发现问题，避免错误和绕过困难。例如，存在一些整数变量，开始时可以把它们处理为连续变量；开始使用格式较粗的输出，在各项输出内容已正确无误时，再将输出格式修改的细致、完善；在最基本的软件包已调试通过后，再往里面引入附加的可以有选择的内容；开始运行程序时，先使用程序提供的缺省值（Default），这种参数值最“安全”，最有代表性。(www.xing528.com)

1.3.3.5　问题运行失败时该注意之点

假如首次最优化的运行是结合一个实际问题进行的，运行的结果是问题不能收敛。那么最优化运行失败的表现形式可能为：初始点是不可行的，迭代点根本没有产生移动；迭代点已经移动了某些距离，但在不可行点处停了下来；迭代点在可行域中移动，但在一个明显的非最优点处停顿下来。

造成上例各种失败的原因可能是：

1）初始点是不可行的，问题在不可行初始点处是病态的。

2）初始点是不可行的，最优化算法又不能很好地处理不可行初始点。

3）问题对于所用的特殊最优化算法而言是病态的。

4）问题的约束过多，以致无可行解存在，或者问题被约束得太紧，使可行域很小。

解决故障的方法：首先需要打印输出该算法最后所得的目标函数、约束函数和各个变量的值，由这些值可以看出失败是属于哪一种表现形式的。如果迭代停止在不可行域中，这时，故障可能是由于问题的约束过多或者问题被约束得太紧造成的。建议首先验证故障产生的原因，放松有关的约束。从最后的打印输出中可看出哪些是没有被满足的约束，这给出了应该放松哪些约束的线索。这可以分成几步来做，直到算法有希望使迭代点移入可行域。如果这样做后仍不能正常运行，则应该更换初始点和试用别的最优化策略；如果失败的表现形式为初始点不可行的，迭代点根本没有产生移动，则另一种解决的方法采用合适的方法求出一个可行初始点。因而求解将分成两个阶段，第一阶段是用一个方法求出可行点，第二阶段可能要用另一个方法求出最优点。如果失败的形式为在一个明显的非最优点处停顿下来，迭代停止在可行域中，这种故障很可能是对所用的算法而言，问题是病态的，至少在部分范围内是这样的。这时，应该使用不同的算法，通过调整算法中所含的可调参数（例如步长等）有可能得到某些改进，但不一定有明显的效果。

1.3.3.6　检验达到的解是否为全局解的实用方法

寻找一个全局最优解不仅是由于它是最好的可行解，而且是由于在研究参数对解的影响时，如果产生多个局部最优解，那么会使研究结果的解释发生严重的混乱。例如，有一组参数使算法结束于某个局部最优值上，而另一组参数使算法结束于另一个不同的局部最优值上，这就很难说明参数变化对解的真实影响。显然，如果在所有的情况下都只能找到全局最优值，那么解释上的混乱就不会存在。

如果是个凸规划，就能保证所得的解是全局解，但是这样的情况很少。实践中最成功、使用最广泛的策略就是全局最优值。当然这里存在一个可信度的问题，运行次数越多，目标函数的一致性越好，所得结果的可信度也越高。如果多次运行得到的目标函数值和变量值都大致相同，则可认为问题具有唯一解；如果目标函数值大致相同，而某些变量值却相差较大，则可认为问题具有不唯一解；目标函数值一致性不好，则可以认为问题具有多个局部最优值。

不同初始点的选取，可使用确定性的格点法，也可使用随机性的取样法。

寻找全局最优的策略是当前的一个研究课题，已有不少研究报告发表，可是至今尚未有一个简单有效的方法，一些较有理论依据的方法大都需要在很严格的条件下才能使用，并且往往需要十分大的计算量，以致除了变量数很小的问题外，一般都不能实际应用。