从算法的性能指标看数值优化算法的创新性设计

来源:用户上传      作者:王宜举 陈海滨

　　[摘 要] 最优化问题的数值算法是运筹学专业研究生专业课“最优化方法”的核心。为提高研究生数值优化方法的学习效果和创新设计能力，对该教学内容，我们给出了数值优化算法的若干性能分析，并指出了设计高效数值优化算法时需注意的一些问题。
　　[关键词] 最优化算法;性能分析;创新性设计
　　 一、引言
　　最优化问题的数值算法是运筹学专业研究生专业课“最优化方法”的基础和核心，最优化问题的数值算法种类繁多，而要学习好这些算法并能设计新的有效算法，首先要掌握好算法的性能分析[1-6]。那么，对最优化问题的数值算法，我们从哪些方面进行比较？如何在此基础上设计更有效的数值算法？对此，我们先给出最优化问题数值算法的一些评价指标，然后指出设计最优化问题数值算法时的一些注意事项，以期提高研究生数值优化算法的学习能力和创新设计能力。
　　二、最优化问题数值算法的性能分析
　　众所周知，最优化问题的一个数值方法要被认可，既要有一定的理论保证，又要有满意的数值效果。对此，我们给出数值方法的有关性能指标。
　　1.收敛性与收敛速度。除非问题特殊，对最优化问题的数值算法，很难保证在有限步骤内得到优化问题的最优解。因此，人们寄希望于该算法产生的迭代点列能一步步靠近最优化问题的最优解，这便引出了算法收敛性的概念。
　　具体地，如果从任意的初始点出发，算法产生的迭代点列都收敛到最优化问题的最优解，则称该算法具有全局收敛性。若算法只有在初始点和最优解具有某种程度靠近时才能保证算法产生的迭代点列收敛到最优解，则称该算法具有局部收敛性。特别地，若算法产生的迭代点列的某聚点为最优化问题的最优解，则称该算法弱收敛。
　　在上述两收敛速度中，超线性收敛比线性收敛速度快。若一个迭代点列Q-（超）线性收敛，则它必R-（超）线性收敛。
　　2.算法稳定性，也就是算法的可靠性。众所周知，在数值计算时，初始数据的舍入误差会通过系列数据运算进行遗传和传播。如果起始数据的误差对最终结果的影响较小，即在运算过程中舍入误差增长缓慢，则称该算法是稳定的。若输出结果的误差随起始数据的舍入误差呈恶性增长，则称该算法是不稳定的。对后者，算法的舍入误差需要适当控制，否则就会像蝴蝶效应一样，使风和日丽的地区几个月后出现狂风暴雨。
　　3.计算复杂性和存储消耗。一个算法要保持高的计算效率，每一迭代步的计算量和存储量是一重要因素。为此，一个快速高效的数值算法，每一迭代步的计算量或存储量不应过大，否则会导致算法的迭代进程变缓，从而影响算法的效率。
　　上述三指标主要侧重算法的理论分析，如最坏情况分析和最好情况分析。它一方面使我们清楚算法对良态问题所具有的诱人性质和对病态问题可能呈现的最坏结果，从而找到算法所适用的问题类;另一方面使我们明白怎样取初始点，怎样取参数，同时帮助我们发现算法中的缺陷，进而改进之。需要说明的是，人们在进行最優化问题的数值算法的理论分析时，一般要对问题或其最优解做些某些假设，而这些假设多数难于验证。
　　4.数值效果。对最优化问题的数值方法进行数值实验是算法设计的重要一环。因为，最优化问题的数值算法最终能否被接受和认可关键在于其数值效果。其次，数值试验有时会很可靠地显露出某些可能的理论结果。只是在进行数值计算的时候，参数的取值和初始点的选取对数值效果的影响较大，同时，也要注意到，对同一算法，在程序的编制过程中，子程序和函数的调用、数据的调取和存储、数据运算的简化等对算法的数值结果影响较大。
　　一般地，一个好的数值优化算法不但要有好的理论性质，同时还要有诱人的数值效果。遗憾的是，如同线性规划问题的单纯形算法和Karmarkar算法，最优化问题的很多数值算法很难在数值效果和理论分析方面达到完美的统一。截至目前，人们还未找到一个理论性质和数值效果都令人满意的通用算法。一般情况下，人们只能宣称某个算法对某类问题有效。这也是非线性最优化问题的数值方法研究中多种方法并存的主要原因。
　　三、最优化方法的创新性设计
　　根据前一节给出的数值算法的性能分析，下面给出在进行最优化问题的数值算法设计时的注意要点。
　　1.严格控制每一迭代步的计算量。数值算法在每一迭代步的计算量是算法效率的保障。如果每一迭代步的计算量太大，必然导致算法在迭代过程中步履蹒跚，缓慢向前。
　　2.充分利用已产生迭代点的信息。除初始点外，一个算法在迭代过程中，已产生迭代点的信息是一宝贵的资源。它一方面显示迭代点列的大致走向，另一方面自觉不自觉地预示着迭代点附近最优值点的信息。所以，只有充分利用这些信息，才能保障算法的稳定性。
　　3.充分挖掘问题的结构性质。不同的问题有不同的结构，不同的结构有不同的算法。如果套用一种算法求解不同的最优化问题，数值效果会很差。反之，如果我们能充分挖掘问题的结构性质，并在算法设计时充分利用问题的结构特点，设计针对该问题的数值算法，效率就会高。
　　4.算法的不断更新。一个新设计的数值算法在进行数值计算时数值效果可能不令人满意，但这并不意味着算法完全不可取，有时候只要我们对算法适当修正就可以大幅度提高算法的效率。
　　参考文献
　　[1]陈宝林.最优化理论与方法[M].北京：清华大学出版社，1989.
　　[2]袁亚湘.非线性最优化数值方法[M].上海：上海科学技术出版社，1993.
　　[3]倪勤.最优化方法与程序设计[M].北京：科学出版社，2009.
　　[4]王宜举，修乃华.非线性最优化理论与方法[M].北京：科学出版社，2012.
　　[5]Bazaraa MS，Sherali HD，Shetty CM.Nonlinear Programming Theory and Algorithms[M].John Wiley and Sons，New York，1993.
　　[6]Bertsekas DP.Nonlinear Programming[M].Athena Scientific，1999.
转载注明来源:https://www.xzbu.com/9/view-15276250.htm