Почему scipy.optimize.linprog не может решить простую проблему

Мне нужно написать функцию, используя scipy.optimize.linprog, чтобы решить матрицу 3x3, чтобы найти равновесие Нэша.

Проблема определяется как:
1- x_i — это вероятность выбрать строку.
2- Выплата столбца представляет собой произведение x_i с соответствующим значением в col_j. (Например, выплата col_1 = 0 * x_1 - 1 * x_2 + 1 * x_3)

Это задача линейной программы, определяемая следующим образом:

 #The matrix to solve  
    col_1 col_2 col_3  
x_1 [[0.0,  1.0, -1.0],  
x_2 [-1.0,  0.0,  1.0],   
x_3 [ 1.0, -1.0,  0.0]]

maximize rows payoff:      
    (0 + 1 -1)X_1 + (-1 + 0 + 1)X_2 + (1 - 1 + 0)X_3

subject to:                    
  0-x_2+x_3=x_1+0-x_3 ---> -x_1-x_2+2x_3=0 #Payoff col_1 = Payoff col_2    
  0-x_2+x_3=-x_1+x_2+0 ---> x_1-2x_2+x_3=0 #Payoff col_1 = Payoff col_3   
  0<=x_1<=1 #Probability bounds of x_1  
  0<=x_2<=1 #Probability bounds of x_2  
  0<=x_3<=1 #Probability bounds of x_3  
  x_1+x_2+x_3=1  #Sum of probabilities of all rows

Решение должно быть: [0,33333, 0,33333, 0,33333]

но когда я запускаю свой код, я получаю следующую ошибку:

 message: 'Optimization failed. Unable to find a feasible starting point.'
     nit: 2
  status: 2
 success: False
       x: nan

Ниже моя функция, и я не знаю, почему она терпит неудачу

def solve_Mixed_NE_LP(X):
    num_of_rows = X.shape[0]
    num_of_columns = X.shape[1]
    c = np.sum(X, axis=1).T #objective to maximize
    b_eq = np.array([])
    A_eq = None
    bounds = []

    #Probabilities bounds: 0 <= x_i <= 1
    for i in range(num_of_rows):
        bounds.append((0.,1.))

    #Total rows selection probabilities must sum to 1
    b_eq = np.append(b_eq, np.array([1]))
    A_eq = np.array([[1 for i in range(num_of_rows)]]).T


    XT = X.T
    for i in range(1,num_of_columns):
        b_eq = np.append(b_eq, np.array([0]))
        constraint = XT[0,:] - XT[i,:]
        constraint = np.array([constraint]).T
        A_eq = np.hstack((A_eq, constraint))


    return optimize.linprog(c=c, A_ub=None, b_ub=None, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='simplex')

python scipy mathematical-optimization linear-programming

07.04.2019 03:07

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

386

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ваша матрица A_eq и вектор b_eq неверны. В соответствии с вашей задачей оптимизации это должно быть:

In [21]: A_eq                                                                                        
Out[21]: 
array([[-1, -1,  2],
       [ 1, -2,  1],
       [ 1,  1,  1]])
In [22]: b_eq                                                                                        
Out[22]: array([0., 0., 1.])

вместо

In [25]: A_eq                                                                                        
Out[25]: 
array([[ 1., -1.,  1.],
       [ 1., -1., -2.],
       [ 1.,  2.,  1.]])

In [26]: b_eq                                                                                        
Out[26]: array([1., 0., 0.])

Изменение вашей функции на

def solve_Mixed_NE_LP(X):
    num_of_rows = X.shape[0]
    num_of_columns = X.shape[1]
    c = np.sum(X, axis=1).T #objective to maximize

    #Probabilities bounds: 0 <= x_i <= 1
    bounds = [(0,1) for i in range(num_of_rows)]

    #Total rows selection probabilities must sum to 1
    A_eq = np.zeros(X.shape)
    b_eq = np.zeros(num_of_rows)
    A_eq[-1,:] = np.ones(num_of_columns)
    b_eq[-1] = 1
    for i in range(num_of_rows-1):
        A_eq[i, :] = X[:, 0] - X[:, i+1]


    return optimize.linprog(c=c, A_ub=None, b_ub=None, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='simplex')

дает мне:

     con: array([0., 0., 0.])
     fun: 0.0
 message: 'Optimization terminated successfully.'
     nit: 6
   slack: array([], dtype=float64)
  status: 0
 success: True
       x: array([0.33333333, 0.33333333, 0.33333333])

Я удалил транспонированные ограничения и использовал vstack вместо hstack, и это сработало. Спасибо за подсказки по коду

— 07.04.2019 12:44

07.04.2019 08:17