Оптимизация функции с линейными ограничениями, содержащей сингулярную матрицу, в Python ⇐ Python

[Anonymous]

Я работаю с данными о дорожном движении, чтобы попытаться восстановить матрицу отправления и назначения региона, основываясь на статье Bell1983.
По сути, для каждой пары мест нам нужно получить, сколько транспортных средств (/пассажиров) переезжает из одного места в другое, и для этого у нас есть данные о дорожном движении общего пользования. Это будет матрица O-D. Он хранится в векторе odm (сплющенном) длиной M, ежедневный трафик для каждой дороги хранится в векторе v длиной N, а дополнительная матрица P, описывающая вероятность прохождения определенной дороги при движении из места A в место B, хранится в массиве P размера N x M (эта матрица строится с помощью некоторой простой эвристики). В моем случае 31 дорога и 120 пар локаций (из 16 выбираем 2).
Цель та же, что и в статье: с учетом ограничений отношения этих переменных получить решение, минимизирующее функцию f. С практической точки зрения следует отметить еще одну важную вещь: ограничение всегда содержит сингулярную матрицу. (В статье на самом деле выводится общая процедура поиска решения, но сейчас я пытаюсь написать код, чтобы получить решение для любой целевой функции.)
Модели имеют ограничение v = P * odm, поэтому у нас есть уравнения M для переменных M.
Проблема в том, что в практических случаях P будет недоопределен из-за таких вещей, как 3 места, лежащих на одном месте. одна и та же линия (например, соединена только двумя дорогами, у вас есть только 2 независимых уравнения для значений пары из 3 мест), поэтому P не будет иметь обратного значения. То же самое и в моем случае, P имеет только 28 независимых уравнений вместо 31. По этой причине существует множество возможных решений уравнения. Классические методы вводят некоторую функцию и выбирают решение, минимизирующее эту функцию - такая функция обычно максимизирует энтропию (== минимизирует (-1)*энтропию).
Используя Python, я попробовал scipy.optimize.minimize с простой функцией для минимизации с учетом ограничения, но получил сообщение: Сингулярная матрица C в подзадаче LSQ. Я знаю, что P имеет единственное число, и это вызвало эту проблему, но P всегда будет единственным, недоопределенным, я могу только с ним работать. Код:

Код: Выделить всё

from scipy.optimize import minimize, Bounds

#Objective function
def f(odm):
#Entropy maximizing (== minimizing the negative entropy)
return np.sum(odm * np.log(odm))

#Constraint(s)
def constraint_eq(odm):
return P @ odm - v
constraints = {'type': 'eq', 'fun': constraint_eq}

bounds = Bounds(1e-5, np.inf) #positive values for log
res = minimize(f, odm, constraints=constraints, bounds=bounds)
optimal_odm = res.x

Всегда будет несколько решений (и гарантированно, что будет хотя бы одно решение), и если задано пространство решений, то будет легко найти то, которое минимизирует f.
Как запустить оптимизацию, которая учитывает сингулярные матрицы в ограничении? Нужно ли мне использовать другой метод решателя?

Я знаю, что один из вариантов — просто исключить 3 уравнения, чтобы получить несингулярную матрицу P для оптимизации, а затем, после получения оптимального решения, решить оставшиеся уравнения, но это кажется довольно сложной задачей.

(Решения для MATLAB также были бы полезны, я с ними в некоторой степени знаком.)

Для воспроизведения проблемы вектор дороги будет иметь вид v = np.array([11479, 24663, 39783, 26064, 65054, 52134, 45172, 18807, 6386, 6544, 23218, 36905, 16558, 5385, 4562, 38232, 8263, 13132, 22395, 3759, 3910, 4100, 17482, 7736, 14255, 5154, 9436, 6554, 11623, 10747, 13110])

и P-матрицу, сохраненную в формате CSV, можно найти здесь: GitHub.

Подробнее здесь: https://stackoverflow.com/questions/783 ... atrix-in-p