Scipy 最小化 - 不断出现奇异矩阵错误

Question

我正在尝试优化 20x5 矩阵以最大化返回值 y。我需要包括 1 个主要约束：

1. 所有元素的总和必须在最小和最大范围之间

但是，我不断收到以下奇异矩阵错误：

Singular matrix C in LSQ subproblem    (Exit mode 6)
            Current function value: -3.0867160133139926
            Iterations: 1
            Function evaluations: 261
            Gradient evaluations: 1

我附上了下面的完整代码。我似乎看不出我做错了什么？

# Import Libraries
import pandas as pd
import numpy as np
import scipy.optimize as so
import random

# Define Objective function
def obj_func(matrix):
    return np.sum(output_matrix)


# Create optimizer function
def optimizer_result(tot_min_sum, tot_max_sum, matrix_input):


    # Create constraint 1) - total matrix sum range
    constraints_list = [{'type': 'ineq', 'fun': lambda x: np.sum(x) - tot_min_sum},
                        {'type': 'ineq', 'fun': lambda x: -(np.sum(x) - tot_max_sum)}]


    # Create an inital matrix
    start_matrix = [random.randint(0, 3) for i in range(0, 20)]

    # Run optimizer
    optimizer_solution = so.minimize(cost, start_matrix, method='SLSQP', bounds=[(0, total_matrix_max_sum)] * 260,
                                     tol=0.01,
                                     options={'disp': True, 'maxiter': 100}, constraints=constraints_list,
                                     callback=callback)
    return optimizer_solution


# Initalise constraints
tot_min_sum = 0
tot_max_sum = 20000
matrix_input = np.zeros((52, 5))
matrix_input[0, 0] = 100


# Run Optimizer
y = optimizer_result(total_matrix_min_sum, total_matrix_max_sum, column_sum_min_lst, column_sum_max_lst, matrix_input)
print(y)

Answer 1

不要对线性问题使用非线性求解器。目标是矩阵的总和，以及您规定的界限，问题很简单：设置 100、200、300 的固定元素，其余为 0。

milp

会告诉您：

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint

I = 52
J = 5

matrix_input = np.zeros((I, J))
matrix_input[0, 0] = 100
matrix_input[0, 1] = 200
matrix_input[0, 2] = 300

total_matrix_min_sum = 0
total_matrix_max_sum = 20000
column_sum_min_lst = [0, 0, 0, 0, 0]
column_sum_max_lst = [10000, 2000, 8000, 0, 0]

# minimize sum of entire matrix
c = np.ones(I*J)

n_fixed = np.count_nonzero(matrix_input)
n_constraint = J + n_fixed + 1
A = np.empty((n_constraint, I*J))
lb = np.empty(n_constraint)
ub = np.empty(n_constraint)

# column bounds
A[:J, :] = np.tile(np.eye(J), (1, I))
lb[:J] = column_sum_min_lst
ub[:J] = column_sum_max_lst

# fixed elements
fixed_flat = matrix_input.ravel()
fixed_idx = fixed_flat.nonzero()
fixed_vals = fixed_flat[fixed_idx]
fixed = np.zeros((n_fixed, I*J))
fixed[np.arange(n_fixed), fixed_idx] = 1
A[J:-1, :] = fixed
lb[J:-1] = fixed_vals
ub[J:-1] = fixed_vals

# total matrix sum bounds
A[-1, :] = 1
lb[-1] = total_matrix_min_sum
ub[-1] = total_matrix_max_sum

result = milp(
    c=c,
    bounds=Bounds(lb=0),  # the only simple constraint is the overall lower bound of 0
    constraints=LinearConstraint(A=A, lb=lb, ub=ub),
)
print(result.message)
x = result.x.reshape((I, J))

Answer 2

我逆向设计了一个数学模型。

最小化将所有变量推向零，所以我将目标切换到最大化。我还假设变量是非负的。

这是一个非凸模型，因此您需要一个全局求解器来确保您不会陷入局部最小值。我给了 Baron 求解器 10 分钟，结果是：

----     75 VARIABLE x.L  cell values

             col1        col2        col3

row1      100.000     200.000     300.000
row9                             7700.000
row13                1800.000
row43    9900.000

这还没有被证明是全球最优的：报告的差距是 4%。找不到比这更好的解决方案。当然，可能有些事情我没有正确解释甚至实施（第一次运行应该持保留态度）。