DIRECT算法及其实现

葛仁磊 王亚男 王毅 张明浩

关键词： 为了有效地解决传统Lipschitz函数极值求解方法向高维推广时遇到的复杂度及计算量急剧增加的问题，DIRECT算法使用超矩形的中心点替代顶点，降低了算法的复杂度及运算量。在进行初始化后，迭代进行“查找潜在超矩形”和“细分超矩形”，直至运算结果满足要求。本文从实用角度出发，对该算法的原理及实现的细节进行了全面介绍，并对算法进行了实现，验证了算法的可行性。

关键词： DIRECT算法; 全局优化; 细分超矩形; 潜在超矩形

中图分类号：TP312          文獻标识码：A    文章编号：1006-8228（2021）05-01-05

DIRECT algorithm and its Python implementation

Ge Renlei， Wang Yanan， Wang Yi， Zhang Minghao

（Offshore Oil Engineering Co.， Ltd.， Qingdao， Shandong 266500， China）

Abstract： In order to effectively solve the problem that the complexity and calculation increase sharply when the traditional Lipschitz function extremum solving method is extended to high dimension， DIRECT algorithm uses the center point of hyper-rectangles to replace the vertices， which reduces the complexity and calculation of the algorithm. After initialization， iteratively "finding potentially optimal hyper-rectangles" and "subdividing the hyper-rectangles" until the calculation results meet the requirements. In this paper， from the practical point of view， the principle and implementation details of the algorithm are comprehensively introduced， and the algorithm is implemented to verify its feasibility.

Key words： DIRECT algorithm; global optimization; subdividing the hyper-rectangle; potentially optimal hyper-rectangle

0 引言

DIRECT（DIvidingRECTangles，细分矩形法）算法是属于Lipschitz函数在有限区间内极值问题的一种求解方法，其本质是一种采样算法。DIRECT算法不需要求解目标函数的参数，非常适合于黑箱函数的优化仿真[1]。本文抛开DIRECT算法的技术与理论细节，展示其具体实现，使得读者能够对照本文快速实现应用，并在文章最后给出实际案例以供参考。

1 Lipschitz函数

函数[fx]为闭区间[a，b]上的函数，如果存在正常数[K]使[fx]满足：

[fx-fx'≤Kx-x'   x，x'∈a，b] ⑴

则称[fx]为区间[a，b]上的Lipschitz函数，[K]为Lipschitz常数，所有满足条件中的[K]中最小的为最佳Lipschitz常数。一阶可导且有界的函数都是Lipschitz连续的[2]。根据定义⑴可得，对任意[x∈a，b]都有：

[ fx≥fa-Kx-a fx≥fb+Kx-b] ⑵

则直线[y=fa-Kx-a]与[y=fb+Kx-b]都位于函数曲线下方。两条直线的交点[x1， gK， fa， fb]为函数[fx]的下界值。

使用相同的方法可以求得在[[a， x1]]和[[x1， b]]两个区间内下[fx]的下界值。依此类推，区间的划分和最小值的求解可以一直迭代下去，直到下界值无限逼近[fx]的最小值。如图1所示。

2 DIRECT算法

传统的算法对于一维的Lipschitz函数最小值的求解问题非常有效，但不便于向n维空间推广。……