卢伟荣，张磊

（中山大学数学学院，广州 510275）

一种加速搜索函数极值的剪枝方法

卢伟荣，张磊

（中山大学数学学院，广州 510275）

函数的极值求解问题是实际应用中有许多优化问题的最基本的问题，大多数模型的优化问题最终都转化为目标函数的极值问题，如最大似然估计和最小二乘估计。在极值问题的数值解法中，遍历搜索可用于函数的高精度极值求解问题，但其时间复杂度非常高；为解决遍历搜索时间过长的问题，随机搜索方法被引入，如遗传算法和模拟褪火算法，而遗传算法极不稳定不适合大数据下智能问题的复杂目标函数的极值搜索。结合遍历搜索和随机搜索，设计一种基于二进制编码的搜索树，并引入基于模拟退火思想的随机剪枝算法，在保证模型精度的基础上对搜索树进行剪枝。在实验环节使用多种形态的函数进行效用分析，说明其在精度和稳定性及时间效用方面的优势。

极值求解；遍历搜索；模拟退火；数值解法

0 引言

在科学技术的各个领域，通常会对所处理的实际问题进行抽象、简化，进而建立数学模型。其中，函数的极值求解对应了一类常见的实际问题，针对处理在一定条件下，如何实现收益最大，或者成本最低等问题。另外，函数的极值求解问题是实际应用中有许多优化问题的最基本的问题，大多数模型的优化问题最终都转化为目标函数的极值问题，如最大似然估计和最小二乘估计。

根据求解方法的不同，函数极值求解可分为以下两类，精确解法和数值解法。……