• 时间:
  • 分类: 优化
  • 阅读量： 23

标签: Benchmark

为了之后优化问题的研究，我在此留一些日后自己写算法需要的测试函数（Benchmark），有简单到可以手算的，也有相对复杂的，根据实际情况我将持续更新本文.

注意，本文并不是讨论深度学习神经网络训练所使用的优化求解器意义下的 Benchmark ，在那种情况下，请右转 Kaggle 寻找对应的数据集.

无约束光滑优化

这里就是比较基本的无约束光滑函数问题，能称得上 Benchmark 的基本都是非凸、梯度性质较差的函数.

Rosenbrock 函数

公式为

$$ f(\boldsymbol{x}) = \sum\limits_{i=1}^{n-1} [100(x_{i+1} - x_{i}^{2})^{2} + (1-x_{i})^{2}] $$

函数是非凸的，并且有很狭长的山谷，优化时需要注意步长搜索的问题.

def rosenbrock(x: np.ndarray):
    # 最小值点为全 1 向量
    # 最小值为 0
    x = x.reshape((-1,))
    n = len(x)
    f = 0

    for i in range(n-1):
        f += 100 * ((x[i+1] - x[i] ** 2) ** 2) + ((1 - x[i]) ** 2)
    
    return f

Beale 函数

函数式为：

$$ f(x_{1}, x_{2}) = (1.5 - x_{1}+ x_{1}x_{2})^{2} + (2.25 - x_{1}+x_{1}x_{2}^{2})^{2} + (2.625 - x_{1}+ x_{1}x_{2}^{3})^{2} $$

对应的 Python 函数代码为：

def beale(x: np.ndarray):
    # 最小值点为 (3, 0.5)
    # 最小值为 0
    x = x.reshape((-1,))
    assert len(x) == 2

    return ((1.5 - x[0] + x[0] * x[1]) ** 2) + ((2.25 - x[0] + x[0] * x[1] ** 2) ** 2) + ((2.625 - x[0] + x[0] * x[1] ** 3) ** 2)

Booth 函数

这个是个纯粹的二次函数，比较简单：

$$ f(x_{1}, x_{2}) = (x_{1} + 2x_{2} - 7)^{2} + (2x_{1}+x_{2}-5)^{2} $$

其代码实现如下所示：

def booth(x: np.ndarray):
    # 最小值点为 (1, 3)
    # 最小值为 0
    x = x.reshape((-1,))
    assert len(x) == 2

    return (x[0] + 2 * x[1] - 7) ** 2 + (2 * x[0] + x[1] -5) ** 2

Matyas 函数

这个函数也是个二次函数，和 Booth 函数类似：

$$ f(x_{1},x_{2}) = 0.26 (x_{1}^{2} + x_{2}^{2}) - 0.48 x_{1}x_{2} $$

def matyas(x: np.ndarray):
    # 最小值点为 (0, 0)
    # 最小值为 0
    x = x.reshape((-1,))
    assert len(x) == 2

    return 0.26 * (x[0] ** 2 + x[1] ** 2) - 0.48 * x[0] * x[1]

Powell 函数

函数式为：

$$ f(\boldsymbol{x}) = (x_{1}+ 10 x_{2})^{2} + 5(x_{3}-x_{4})^{2} + (x_{1}-2x_{3})^{4} + 10 (x_{1}-x_{4})^{4} $$

手算得到最小值的方法很简单，就是让括号里面的一次式都为 $0$ ，有

$$ \begin{cases} x_{1} + 10 x_{2} = 0 \\ x_{3} - x_{4} = 0 \\ x_{1} - 2x_{3} = 0 \\ x_{1} - x_{4} = 0 \end{cases} $$

即 $x_{1}=x_{2}=x_{3}=x_{4}=0$ 即可达到最小值 $0$ .

这个函数的特点在于：高度非凸，梯度变化相当剧烈. 其代码实现为：

def powell(x: np.ndarray):
    # 最小值点为 (0, 0, 0, 0)
    # 最小值为 0
    x = x.reshape((-1,))
    assert len(x) == 4

    return (x[0] + 10 * x[1]) ** 2 + 5 * (x[2] - x[3]) ** 2 + (x[0] - 2 * x[2]) ** 4 + 10 * (x[0] - x[3]) ** 4

Zakharov 函数

这个是一个凸函数，局部极值就是全局极值，所以优化起来还算方便.

$$ f(\boldsymbol{x}) = \sum\limits_{i=1}^{n} x_{i}^{2} + \left(\sum\limits_{i=1}^{n} 0.5 i x_{i}\right)^{2} + \left(\sum\limits_{i=1}^{n} 0.5 i x_{i}\right)^{4} $$

其代码为：

def zakharov(x: np.ndarray):
    # 最小值点为全 0 向量
    # 最小值为 0
    x = x.reshape((-1,0))

    f1 = np.sum(np.pow(x, 2))
    tmp = 0

    for i in range(len(x)):
        tmp += 0.5 * (i + 1) * x[i]
    
    f2 = tmp ** 2
    f3 = tmp ** 4

    return f1 + f2 + f3

更多的选择……

可以在一些网站上面找到优化函数的选择. 1

无约束非光滑优化

这部分收录可导但是并不光滑的函数，例如带有正则化的光滑函数等. 这里可以用来测试自己实现的 PGD、FISTA、ADMM 计算是否准确.

Huber 函数

以下函数式为 Huber 函数：

$$ h_{\delta} (z) = \begin{cases} \dfrac{1}{2} z^{2}, & |z| \leqslant \delta \\ \delta |z| - \dfrac{1}{2} \delta^{2}, & |z| > \delta \end{cases} $$

这个函数的最小值取决于 $\delta$ 的取值，当 $\delta=1$ 的时候，很明显就是 $z=0$ 时为最小值点.

函数实现如下：

def huber(x: np.ndarray, delta: float = 1.0):

    x_arr = np.asarray(x)
    mask = np.abs(x_arr) <= delta
    z = np.zeros_like(x_arr, dtype=np.float64)

    z[mask] = 0.5 * (x_arr[mask] ** 2)
    z[~mask] = delta * np.abs(x_arr[~mask]) - 0.5 * (delta ** 2)

    return z.item() if np.isscalar(x) else z

LASSO

这已经算非光滑优化里面几乎最经典的一类了，也就是 regularized optimization ，式子如下所示：

$$ \min \quad \frac{1}{2} \|\boldsymbol{y} - \boldsymbol{X \beta}\|_{2}^{2} + \lambda\|\boldsymbol{\beta}\|_{1} $$

这里 $\boldsymbol{X}\in \mathbb{R}^{n\times p}$ ，系数 $\boldsymbol{\beta}\in \mathbb{R}^{p}$ ，得到的解在 $\lambda>0$ 取值合适的情况下会变得稀疏.

这里构造数据并使用 CVXPY 2 来求解得到标准结果. 构造数据的方式为：

import numpy as np

np.random.seed(0)
X = np.random.randn(10, 3)
coef = np.random.randn(3)
y = X @ coef + 0.1 * np.random.random(10)

这里分别为：

X = np.array([[ 1.76405235, 0.40015721,  0.97873798]
 [ 2.2408932,   1.86755799, -0.97727788]
 [ 0.95008842, -0.15135721, -0.10321885]
 [ 0.4105985,   0.14404357,  1.45427351]
 [ 0.76103773,  0.12167502,  0.44386323]
 [ 0.33367433,  1.49407907, -0.20515826]
 [ 0.3130677,  -0.85409574, -2.55298982]
 [ 0.6536186,   0.8644362,  -0.74216502]
 [ 2.26975462, -1.45436567,  0.04575852]
 [-0.18718385,  1.53277921,  1.46935877]])
 
coef = np.array([ 0.15494743,  0.37816252, -0.88778575])

y = np.array([-0.37448669,  1.92709699,  0.24828903, -1.10592645, -0.20908343,  0.8117359, 2.02357285,  1.12342849, -0.18189803, -0.70997963])

可以通过 CVXPY 求解得到

-------------------------------------------------------------------------------
                                    Summary
-------------------------------------------------------------------------------
(CVXPY) Feb 13 02:10:26 PM: Problem status: optimal
(CVXPY) Feb 13 02:10:26 PM: Optimal value: 1.327e+00
(CVXPY) Feb 13 02:10:26 PM: Compilation took 9.012e-03 seconds
(CVXPY) Feb 13 02:10:26 PM: Solver (including time spent in interface) took 4.001e-03 seconds
最优值： 1.3266687768327428
x:
 [ 0.13671261  0.28283799 -0.79049985]

以供参考，求解的代码为：

import cvxpy as cp

beta = cp.Variable(3)
f = 0.5 * cp.sum_squares(y - X @ beta) + 1.0 * cp.norm1(beta)
prob = cp.Problem(cp.Minimize(f))

线性 Min-Max 问题

设

$$ f(\boldsymbol{x}) = \max_{1 \leqslant i \leqslant m} f_{i}(\boldsymbol{x}) $$

那么此时对于分段内的函数，取线性函数：

$$ f_{i}(\boldsymbol{x}) = \boldsymbol{a}_{i}^{\top} \boldsymbol{x} + b_{i} $$

就是线性的 Min-Max 函数，这种函数最小值存在，但是由于斜率的变化，会导致非光滑，因此在优化的时候需要注意.

函数实现为：

a = np.array([[2], [-1]])
b = np.array([1, 3])

def linear_min_max(x: np.ndarray):
    x = np.asarray(x).reshape(-1)
    return np.max(a @ x + b)

这是一个简单的例子：

$$ f(x) = \max(2x+1, -x+3) $$

最小值点就是 $\dfrac{2}{3}$ .

需要注意的是，根据 Rockfellar 的凸分析 3 ，这类函数都可以直接转换为线性规划来解决.

约束光滑优化

【待续】

约束非光滑优化

【待续】

无梯度优化

【待续】

贝叶斯优化

人为构造：Func-2C

这个来自于 CoCaBO 4 的优化 Benchmark ，是一个人工构造的黑盒函数，同时包含了类别变量输入和连续输入，这里：

  • 连续变量就是正常的无约束光滑优化函数的输入，可以就直接用本文开头的几个函数，例如 Rosenbrock 等.
  • 离散变量则是在加权求和这些无约束光滑函数的值的起作用的，它们代表了几个可选的权重.

下面直接给出代码，这里是我对 CoCaBO 当中 Func-2C 实验的一个简单复现：

import numpy as np

def beale(xy):
    x, y = xy
    return (1.5 - x + x*y)**2 + (2.25 - x + x*y**2)**2 + (2.625 - x + x*y**3)**2

def six_hump_camel(xy):
    x, y = xy
    return (4 - 2.1*x**2 + (x**4)/3)*x**2 + x*y + (-4 + 4*y**2)*y**2

def rosenbrock(xy):
    x, y = xy
    return 100*(y - x**2)**2 + (1 - x)**2

# six-hump camel global minimum is about -1.0316, shift up to make it nonnegative-ish
CAMEL_MIN = -1.0316284534898772
def camel_pos(xy):
    return six_hump_camel(xy) - CAMEL_MIN


def synthetic_func2c(x, h1, h2):
    """
    x: shape (2,), 在 [-1,1]^2
    h1: 0..2, h2: 0..4 ，文章中的类别变量
    """
    x = np.asarray(x, dtype=float)

    # 定义域
    xb = 4.5 * x      # beale often on [-4.5,4.5]^2
    xc = 3.0 * x      # camel often on [-3,3]^2
    xr = 2.0 * x      # rosen on a moderate range

    # 基础的函数值
    fb = beale(xb) / 50.0
    fc = camel_pos(xc) / 10.0
    fr = rosenbrock(xr) / 200.0

    # 离散系数，通过 h1 和 h2 类别变量来转换权重
    w_beale = np.array([1.0, 0.7, 0.2])                 # best at h1=2
    w_camel = np.array([1.0, 0.8, 0.2, 0.9, 1.1])        # best at h2=2
    w_rosen = 0.6 + 0.15*abs(h1-2) + 0.15*abs(h2-2)      # best at (2,2)

    g = w_beale[h1]*fb + w_camel[h2]*fc + w_rosen*fr

    # 转化为最大化问题
    return float(1.0 / (1.0 + g))

可以看到，其实关键就在如下的一块：

# 离散系数，通过 h1 和 h2 类别变量来转换权重
w_beale = np.array([1.0, 0.7, 0.2])                 # best at h1=2
w_camel = np.array([1.0, 0.8, 0.2, 0.9, 1.1])        # best at h2=2
w_rosen = 0.6 + 0.15*abs(h1-2) + 0.15*abs(h2-2)      # best at (2,2)

g = w_beale[h1]*fb + w_camel[h2]*fc + w_rosen*fr

那么根据这种离散系数的原理，其实很容易组合出非常多的 Benchmark.

  1. BenchmarkFcns : 一个多元函数优化 Benchmark 的汇总文档，本文无约束光滑优化部分的函数在该文档内基本都有. ↩
  2. Steven Diamond, Eric Chu, and Stephen Boyd, _CVXPY: A Python-Embedded Modeling Language for Convex Optimization, version 0.2_. (May 2014). [Online]. Available: http://cvxpy.org/ ↩
  3. R. T. Rockafellar, _Convex Analysis_. Princeton University Press, 1970. doi: 10.1515/9781400873173. ↩
  4. Binxin Ru, Ahsan S. Alvi, Vu Nguyen, Michael A. Osborne, and Stephen J Roberts, “Bayesian optimisation over multiple continuous and categorical inputs,” in _Proceedings of the 37th International Conference on Machine Learning_, in ICML’20, vol. 119. JMLR.org, Jul. 2020, pp. 8276–8285. Accessed: Jan. 22, 2026. [Online]. Available: https://dl.acm.org/doi/10.5555/3524938.3525704 ↩

添加新评论

（所有评论均需经过站主审核，违反社会道德规范与国家法律法规的评论不予通过）