无导数优化方法及应用

高静 曹健

摘 要：信息时代的优化问题多以大数据为研究基础，其模型通常规模庞大且函数不具有典型性。传统最优化方法已无法省时高效的求解此类问题，于是无导数优化方法脱颖而出。本文介绍了无导数优化的概念、国内外研究现状以及其在图像配准、动态定价和网络优化等领域的应用。

关键词：最优化理论；无导数优化方法

1 概述

最优化理论与方法在军事、金融和工业生产等领域都具有巨大的指导意义。在我国，最优化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科。最优化问题的一般数学模型为

min f（x）

s.t.x∈Ω，

其中x∈Rn是决策变量，f（x）为目标函数，ΩRn为优化问题的可行域。最优化问题随目标函数、决策变量和约束条件的不同，可作为不同分支的优化问题来研究，如线性规划、非线性规划以及随机规划等，解决方法不断推陈出新，应用效果日渐完美。随现代信息技术的革新，海量数据得到广泛应用，致使最优化问题呈现出规模巨大，目标函数性状不光滑、不稳定或者导函数信息不可用等特点。众所周知，在优化问题中许多经典的最优化方法框架均基于导函数信息，一旦导函数信息缺失，传统最优化方法运算起来就会十分费力耗时，甚至有一部分问题难以求解，为此需要新的优化思想有针对性的适应此类问题。于是，无导数优化思想受到学者们的广泛关注。

2 国内外研究现状

无导数优化思想是在有效避免使用目标函数或约束条件的导函数信息的前提下，获得最优化问题的近似最优解。在当前的研究领域中，求解带有不完整导数信息或者解决成本极高的目标函数的优化问题的实用性日益增长。日益复杂的数学建模，更加复杂的科学计算等都使得无导数优化算法的需求量逐渐增大。

关于无导数优化算法的研究，目前已有许多卓有成效的算法指导实践，如无导数优化算法应用在调整非线性优化方法的参数[1]时，根据目标问题集的特点，确定出适合该问题集的参数取值。使用这种取值方案，可以使目标问题集的求解总用时缩短15%。为了减少在优化过程中所需的详细分析，J.E.Booker[2]等人在带有直升机旋翼设计问题的测试问题中利用无导数优化思想开发了一个严格有效的管理方案。其中，在优化和预定进度检查中使用替代函数，它与繁杂的分析之间相互作用，使得该过程收敛于原始的解决方案。而且此方案给出的结果支持在DACE模型上使用ANOVA分解来识别最优设计问题中最重要的优化变量。此外，无导数优化思想还用于空气声学的形状设计和水动力设计等。这些无导数优化方法都是为解决特定的优化问题而设计的，缺点在于其局限性，无法广泛应用于各行各业。所以，还有另一种框架式的无导数优化方法，如J.Cao[3]等人提出的无导数优化算法是以信赖域方法为框架提出的。相比之下，这些算法的优势在于能够广泛应用到一类优化问题上。

3 无导数优化方法的应用

在大数据蓬勃发展的今天，无导数优化问题有着广泛的应用空间。在诊断病情和制定治疗方案时，为了给医生提供更全面，更直观的图像依据，往往需要将不同模态的图像信息在空间上达到一致，这一步骤称为配准。但由于配准的计算涉及到大量的浮点运算且数据量过大，配准过程复杂、费时，于是无导数优化方法在这里便有了用武之地。无导数优化问题中的模型搜索法是解决配准问题比较有效的一种方法，该算法轮流对变换参数进行优化，因为无需计算梯度，所以可以加快搜索变量与变量之间的统计相关性的速度，在局部范围内有很高效的寻优性。

网络销售渠道的出现使得动态定价策略日益重要。所谓动态定价，是指企业根据市场需求和自身供应能力，以不同的价格将同一产品适时地销售给不同的消费者或不同的细分市场，以实现收益最大化的一种策略。为实现客户与企业资产回报最大化，动态定价决策过程需要管理层投入大量宝贵的时间和精力，定价策略应与企业品牌战略同时进行而不相抵触。然而具体定价与企业品牌之间的函数关系，与市场价格浮动产生的影响之间的函数关系并没有具体的形态，所以性能价格比的评估值函数不确定。因此根据市场环境，应用无导数优化方法构造函数关系，计算出性能价格比的评估值，用户便可以根据评估值来选择适合自己的业务类型，自然而然的性能价格比高的业务类就会选择频率高，这样下来能给互联网服务提供商带来更多的商业利益。

无导数优化方法还可以运用到网络运营管理及优化中。通过分析网络流量、流向趋势变换，无导数优化算法能够及时调整资源配置进行网络优化使网络质量得分和利用率不断提升。它还可以根据网络信令数据，实时监控网络状况，识别分析出价值小区和业务热点小区，更精准的实施网络优化，使网络应用和用户可以实时智能匹配。

4 总结

日益发展的信息技术时代，为无导数优化方法提供了广阔的发展空间。以无导数优化方法获得的决策方案更为信息技术时代的最优化问题提供指导依据。无导数优化算法以其避免导函数信息、化繁为简为优势，为信息技术时代的革新发挥着重要的作用，未来前景值得期待。

参考文献：

[1]C.Audet，D.Orban，Finding optimal algorithmic parameters using derivative-free optimization，SIAM J.Optim，2006，17：642-664.

[2]A.J.Booker，J.E.Dennis，P.D.Frank，D.W.Moore，D.B.Serafini，Managing surrogate objectives to optimize a helicopter rotor design-further experiments，in AIAA Paper 1998-4717，8th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization，St.Louis，MO，1998.

[3]J.Gao，J.Cao，A class of derivative-free trust-region methods with interior backtracking technique for nonlinear optimization problems subject to linear inequality constraints，Journal of Inequalities & Applications，2018，2018（1）：108.

项目基金：国家自然科学基金（11626037）；吉林省教育厅“十三五”科学技术项目（JJKH20170036KJ）；北华大学青年培育计划项目（2017QNJJL10）

作者简介：高靜，女，讲师，研究方向：最优化理论与方法。

通讯作者：曹健，男，讲师，研究方向：网络优化算法。