python - Scipy 优化最小化总是返回初始猜测（SLSQP）

Question

就像标题解释的那样，我的程序总是返回最初的猜测。

就上下文而言，该计划正试图找到在多个商店中分配某些产品的最佳方式。每家商店都有他们预计在接下来几天内销售的商品的预测 (sales_data)。这个预测不一定是整数，或者大于 1（很少是这样），它是统计意义上的预期。因此，如果一家商店的 sales_data = [0.33, 0.33, 0.33] ，则预计 3 天后，他们将售出 1 件产品。

我想尽量减少出售我分配的单位所需的总时间（我想以最快的速度出售它们），我的限制是我必须分配我可用的单位，并且我不能分配负数的产品到一家商店。我现在可以进行非整数分配。对于我的初始分配，我在所有商店中平均分配我可用的单位。

以下是我遇到问题的代码的较短版本：

import numpy, random
from scipy.optimize import curve_fit, minimize

unitsAvailable = 50
days = 15

class Store:

    def __init__(self, num):
        self.num = num

        self.sales_data = []


stores = []
for i in range(10):
    # Identifier
    stores.append(Store(random.randint(1000, 9999)))
    # Expected units to be sold that day (It's unlikey they will sell 1 every day)
    stores[i].sales_data = [random.randint(0, 100) / 100 for i in range(days)]
    print(stores[i].sales_data)


def days_to_turn(alloc, store):
    day = 0

    inventory = alloc
    while (inventory > 0 and day < days):
        inventory -= store.sales_data[day]
        day += 1
    return day

def time_objective(allocations):
    time = 0
    for i in range(len(stores)):
        time += days_to_turn(allocations[i], stores[i])
    return time

def constraint1(allocations):

    return unitsAvailable - sum(allocations)

def constraint2(allocations):

    return min(allocations) - 1

cons = [{'type':'eq', 'fun':constraint1}, {'type':'ineq', 'fun':constraint2}]
guess_allocs = []

for i in range(len(stores)):
    guess_allocs.append(unitsAvailable / len(stores))

guess_allocs = numpy.array(guess_allocs)

print('Optimizing...')

time_solution = minimize(time_objective, guess_allocs, method='SLSQP', constraints=cons, options={'disp':True, 'maxiter': 500})

time_allocationsOpt = [max([a, 0]) for a in time_solution.x]

unitsUsedOpt = sum(time_allocationsOpt)
unitsDaysProjected = time_solution.fun

for i in range(len(stores)):
    print("----------------------------------")
    print("Units to send to Store %s: %s" % (stores[i].num, time_allocationsOpt[i]))
    print("Time to turn allocated: %d" % (days_to_turn(time_allocationsOpt[i], stores[i])))

print("----------------------------------")
print("Estimated days to be sold: " + str(unitsDaysProjected))
print("----------------------------------")
print("Total units sent: " + str(unitsUsedOpt))
print("----------------------------------")

优化成功完成，只有 1 次迭代，无论我如何更改参数，它总是返回初始的guess_allocs。

有什么建议吗？

标签： pythonnumpyscipyscipy-optimizescipy-optimize-minimize

Answer 1

目标函数没有梯度，因为它返回离散的天数倍数。这很容易可视化：

import numpy as np
import matplotlib.pyplot as plt

y = []
x = np.linspace(-4, 4, 1000)
for i in x:
    a = guess_allocs + [i, -i, 0, 0, 0, 0, 0, 0, 0, 0]    
    y.append(time_objective(a))

plt.plot(x, y)
plt.xlabel('relative allocation')
plt.ylabel('objective')
plt.show()

如果你想优化这样的功能，你不能使用基于梯度的优化器。有两种选择： 1）找到一种使目标函数可微的方法。2) 使用不同的优化器。第一个很难。其次，让我们尝试双重退火。不幸的是，它不允许约束，所以我们需要修改目标函数。

将N个数字约束为一个常数和与拥有N-1 个不受约束的数字并将第N个数字设置为常数 - 和相同。

import scipy.optimize as spo

bounds = [(0, unitsAvailable)] * (len(stores) - 1)

def constrained_objective(partial_allocs):
    if np.sum(partial_allocs) > unitsAvailable:
        # can't sell more than is available, so make the objective infeasible
        return np.inf
    # Partial_alloc contains allocations to all but one store.
    # The final store gets allocated the remaining units.
    allocs = np.append(partial_allocs, unitsAvailable - np.sum(partial_allocs))
    return time_objective(allocs)

time_solution = spo.dual_annealing(constrained_objective, bounds, x0=guess_allocs[:-1])
print(time_solution)

这是一种随机优化方法。您可能希望多次运行它以查看它是否可以做得更好，或者使用可选参数...

最后，我认为目标函数有问题：

for i in range(len(stores)):
    time += days_to_turn(allocations[i], stores[i])

这表示商店不会同时销售，而是一个接一个。是否每家商店都在等待销售，直到前一家商店的商品用完？我想不是。相反，它们将同时销售，所有单位销售所需的时间是商店花费时间最长的时间。试试这个：

for i in range(len(stores)):
    time = max(time, days_to_turn(allocations[i], stores[i]))