python - 使用 scipy.optimize 最小化多元可微函数

Question

我正在尝试使用 scipy.optimize 最小化以下函数:

这是它的梯度:

(对于那些感兴趣的人，这是用于成对比较的 Bradley-Terry-Luce 模型的似然函数。与逻辑回归密切相关。)

很明显，向所有参数添加常量不会改变函数的值。因此，我让\theta_1 = 0。以下是目标函数和梯度在 python 中的实现(theta 在这里变为 x):

def objective(x):
    x = np.insert(x, 0, 0.0)
    tiles = np.tile(x, (len(x), 1))
    combs = tiles.T - tiles
    exps = np.dstack((zeros, combs))
    return np.sum(cijs * scipy.misc.logsumexp(exps, axis=2))

def gradient(x):
    zeros = np.zeros(cijs.shape)
    x = np.insert(x, 0, 0.0)
    tiles = np.tile(x, (len(x), 1))
    combs = tiles - tiles.T
    one = 1.0 / (np.exp(combs) + 1)
    two = 1.0 / (np.exp(combs.T) + 1)
    mat = (cijs * one) + (cijs.T * two)
    grad = np.sum(mat, axis=0)
    return grad[1:]  # Don't return the first element

这是一个 cijs 的例子:

[[ 0  5  1  4  6]
 [ 4  0  2  2  0]
 [ 6  4  0  9  3]
 [ 6  8  3  0  5]
 [10  7 11  4  0]]

这是我为执行最小化而运行的代码:

x0 = numpy.random.random(nb_items - 1)
# Let's try one algorithm...
xopt1 = scipy.optimize.fmin_bfgs(objective, x0, fprime=gradient, disp=True)
# And another one...
xopt2 = scipy.optimize.fmin_cg(objective, x0, fprime=gradient, disp=True)

然而，它总是在第一次迭代中失败:

Warning: Desired error not necessarily achieved due to precision loss.
         Current function value: 73.290610
         Iterations: 0
         Function evaluations: 38
         Gradient evaluations: 27

我不知道为什么会失败。由于这一行而显示错误: https://github.com/scipy/scipy/blob/master/scipy/optimize/optimize.py#L853

所以这个“Wolfe 线搜索”似乎没有成功，但我不知道如何从这里继续......感谢任何帮助!

Answer 1

作为@pv。作为评论指出，我在计算梯度时犯了一个错误。首先，我的目标函数梯度的正确(数学)表达式是:

(注意减号。)此外，我的 Python 实现完全错误，除了符号错误之外。这是我更新的渐变:

def gradient(x):
    nb_comparisons = cijs + cijs.T
    x = np.insert(x, 0, 0.0)
    tiles = np.tile(x, (len(x), 1))
    combs = tiles - tiles.T
    probs = 1.0 / (np.exp(combs) + 1)
    mat = (nb_comparisons * probs) - cijs
    grad = np.sum(mat, axis=1)
    return grad[1:]  # Don't return the first element.

为了调试它，我使用了:

• scipy.optimize.check_grad:表明我的梯度函数产生的结果与近似(有限差分)梯度相去甚远。
• scipy.optimize.approx_fprime 了解值应该是什么样子。
• 一些精心挑选的简单示例，如果需要可以手动分析这些示例，以及一些用于完整性检查的 Wolfram Alpha 查询。