linprog(method=’interior-point’)#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, границы=(0, None), метод='highs', callback=None, опции=None, x0=None, integrality=None)

Линейное программирование: минимизация линейной целевой функции при линейных ограничениях равенства и неравенства с использованием метода внутренней точки [4].

Устарело с версии 1.9.0: method='interior-point' будет удалён в SciPy 1.11.0. Заменён на method='highs' потому что последний быстрее и надежнее.

Линейное программирование решает задачи следующего вида:

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

где \(x\) является вектором переменных решения; \(c\), \(b_{ub}\), \(b_{eq}\), \(l\), и \(u\) являются векторами; и \(A_{ub}\) и \(A_{eq}\) являются матрицами.

Альтернативно, это:

минимизировать:

c @ x

такой, что:

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

Обратите внимание, что по умолчанию lb = 0 и ub = None если не указано с помощью bounds.

Параметры:
cОдномерный массив

Коэффициенты линейной целевой функции для минимизации.

A_ub2-D массив, опционально

Матрица ограничений неравенства. Каждая строка A_ub определяет коэффициенты линейного ограничения-неравенства на x.

b_ub1-D массив, необязательный

Вектор ограничений-неравенств. Каждый элемент представляет верхнюю границу соответствующего значения A_ub @ x.

A_eq2-D массив, опционально

Матрица ограничений равенства. Каждая строка A_eq задает коэффициенты линейного ограничения равенства на x.

b_eq1-D массив, необязательный

Вектор ограничения равенства. Каждый элемент A_eq @ x должен равняться соответствующему элементу b_eq.

границыsequence, optional

Последовательность (min, max) пары для каждого элемента в x, определяя минимальное и максимальное значения этой переменной решения. Используйте None чтобы указать, что ограничения отсутствуют. По умолчанию ограничения (0, None) (все переменные решения неотрицательны). Если одиночный кортеж (min, max) предоставляется, тогда min и max будет служить границами для всех переменных решения.

методstr

Это документация, специфичная для метода 'interior-point'. ‘highs’, ‘highs-ds’, 'highs-ipm', ‘revised simplex’, и 'simplex' (устаревший) также доступны.

callbackвызываемый объект, необязательный

Функция обратного вызова, выполняемая один раз за итерацию.

Возвращает:
resOptimizeResult

A scipy.optimize.OptimizeResult состоящий из полей:

xОдномерный массив

Значения переменных решения, которые минимизируют целевую функцию при соблюдении ограничений.

funfloat

Оптимальное значение целевой функции c @ x.

slackОдномерный массив

(Номинально положительные) значения переменных ослабления, b_ub - A_ub @ x.

conОдномерный массив

(Номинально нулевые) невязки ограничений-равенств, b_eq - A_eq @ x.

successbool

True когда алгоритму удается найти оптимальное решение.

statusint

Целое число, представляющее статус завершения алгоритма.

0 : Оптимизация успешно завершена.

1 : Достигнут предел итераций.

2 : Проблема, по-видимому, неразрешима.

3 : Проблема, по-видимому, неограничена.

4 : Возникли численные трудности.

messagestr

Строковый дескриптор статуса завершения алгоритма.

nitint

Общее количество итераций, выполненных на всех этапах.

Смотрите также

Для документации по остальным параметрам см. scipy.optimize.linprog

Опции:
——-
maxiterint (по умолчанию: 1000)

Максимальное количество итераций алгоритма.

dispbool (по умолчанию: False)

Установить в True если индикаторы статуса оптимизации должны выводиться в консоль на каждой итерации.

предварительное решениеbool (по умолчанию: True)

Предварительное решение пытается выявить тривиальные несовместимости, определить тривиальную неограниченность и упростить задачу перед отправкой её основному решателю. Обычно рекомендуется сохранять настройки по умолчанию True; установить в False если предварительное решение должно быть отключено.

tolfloat (по умолчанию: 1e-8)

Допуск завершения, используемый для всех критериев завершения; см. [4] Раздел 4.5.

autoscalebool (по умолчанию: False)

Установить в True для автоматического выполнения уравновешивания. Рассмотрите использование этой опции, если числовые значения в ограничениях различаются на несколько порядков величины.

rrbool (по умолчанию: True)

Установить в False чтобы отключить автоматическое удаление избыточности.

alpha0float (по умолчанию: 0.99995)

Максимальный размер шага для направления поиска предиктора-корректора Мехроты; см. \(\beta_{3}\) of [4] Таблица 8.1.

betafloat (по умолчанию: 0.1)

Желаемое сокращение параметра пути \(\mu\) (см. [6]) когда предиктор-корректор Мехроты не используется (редко).

разреженныйbool (по умолчанию: False)

Установить в True если задача должна рассматриваться как разреженная после предварительной обработки. Если любой из A_eq или A_ub является разреженной, эта опция будет автоматически установлена True, и задача будет рассматриваться как разреженная даже во время предварительного решения. Если ваши матрицы ограничений содержат в основном нули и задача не очень мала (менее чем около 100 ограничений или переменных), рассмотрите установку True или предоставляя A_eq и A_ub как разреженные массивы.

lstsqbool (по умолчанию: False)

Установить в True если проблема ожидается очень плохо обусловленной. Это всегда следует оставлять False если не возникают серьёзные численные трудности. Оставьте это значение по умолчанию, если вы не получили предупреждение, предлагающее иное.

sym_posbool (по умолчанию: True)

Оставить True если ожидается, что задача даст хорошо обусловленную симметричную положительно определенную матрицу нормальных уравнений (почти всегда). Оставьте это значение по умолчанию, если вы не получите сообщение с предупреждением, предлагающим иное.

choleskybool (по умолчанию: True)

Установить в True если нормальные уравнения должны быть решены явным разложением Холецкого с последующей явной прямой/обратной подстановкой. Это обычно быстрее для задач, которые численно хорошо обусловлены.

pcbool (по умолчанию: True)

Оставить True если должен использоваться метод предиктор-корректор Мехроты. Это почти всегда (если не всегда) полезно.

ipbool (по умолчанию: False)

Установить в True если улучшенное предложение начальной точки благодаря [4] Желателен раздел 4.3. Будет ли это полезно или нет, зависит от задачи.

permc_specstr (по умолчанию: ‘MMD_AT_PLUS_A’)

(Имеет эффект только с sparse = True, lstsq = False, sym_pos = True, и без SuiteSparse.) Матрица факторизуется на каждой итерации алгоритма. Эта опция определяет, как переставлять столбцы матрицы для сохранения разреженности. Допустимые значения:

  • NATURAL: естественный порядок.

  • MMD_ATA: упорядочивание по минимальной степени на структуре A^T A.

  • MMD_AT_PLUS_A: упорядочивание по минимальной степени на структуре A^T+A.

  • COLAMD: приближённое упорядочение столбцов по минимальной степени.

Эта опция может влиять на сходимость алгоритма внутренней точки; протестируйте различные значения, чтобы определить, какие лучше подходят для вашей задачи. Для получения дополнительной информации обратитесь к scipy.sparse.linalg.splu.

unknown_optionsdict

Дополнительные аргументы, не используемые этим конкретным решателем. Если unknown_options не пусто, выдаётся предупреждение со списком всех неиспользуемых опций.

Примечания

Этот метод реализует алгоритм, описанный в [4] с идеями из [8] и структурой, вдохновленной более простыми методами [6].

Метод следования по примально-двойственному пути начинается с начальных «предположений» примальных и двойственных переменных задачи стандартной формы и итеративно пытается решить (нелинейные) условия Каруша-Куна-Такера для задачи с постепенно уменьшаемым логарифмическим барьерным членом, добавленным к целевой функции. Эта конкретная реализация использует однородную самодвойственную формулировку, которая предоставляет сертификаты несовместности или неограниченности, где это применимо.

Начальная точка по умолчанию для прямых и двойственных переменных – это определённая в [4] Раздел 4.4 Уравнение 8.22. Опционально (установкой опции начальной точки ip=True), альтернативная (потенциально улучшенная) начальная точка может быть рассчитана в соответствии с дополнительными рекомендациями [4] Раздел 4.4.

Направление поиска вычисляется методом предиктор-корректор (одна коррекция), предложенным Мехротой и подробно описанным в [4] Раздел 4.1. (Потенциальным улучшением могла бы быть реализация метода множественных поправок, описанного в [4] Раздел 4.2.) На практике это достигается решением нормальных уравнений, [4] Раздел 5.1 Уравнения 8.31 и 8.32, выведенные из уравнений Ньютона [4] Раздел 5 Уравнения 8.25 (сравните с [4] Раздел 4 Уравнения 8.6-8.8). Преимущество решения нормальных уравнений вместо прямого решения 8.25 заключается в том, что задействованные матрицы являются симметричными положительно определенными, поэтому можно использовать разложение Холецкого вместо более затратной LU-факторизации.

При настройках по умолчанию решатель, используемый для выполнения факторизации, зависит от доступности стороннего программного обеспечения и обусловленности задачи.

Для плотных задач решатели пробуются в следующем порядке:

  1. scipy.linalg.cho_factor

  2. scipy.linalg.solve с опцией sym_pos=True

  3. scipy.linalg.solve с опцией sym_pos=False

  4. scipy.linalg.lstsq

Для разреженных задач:

  1. sksparse.cholmod.cholesky (если установлены scikit-sparse и SuiteSparse)

  2. scipy.sparse.linalg.factorized (если установлены scikit-umfpack и SuiteSparse)

  3. scipy.sparse.linalg.splu (который использует SuperLU, поставляемый с SciPy)

  4. scipy.sparse.linalg.lsqr

Если решатель не срабатывает по любой причине, последовательно пробуются более надежные (но медленные) решатели в указанном порядке. Попытки, сбои и перезапуск факторизации могут занимать много времени, поэтому если задача численно сложная, можно установить опции для обхода решателей, которые не срабатывают. Установка cholesky=False переходит к решателю 2, sym_pos=False переходит к решателю 3, и lstsq=True переходит к решателю 4 для разреженных и плотных задач.

Потенциальные улучшения для борьбы с проблемами, связанными с плотными столбцами в иначе разреженных задачах, описаны в [4] Раздел 5.3 и [10] Раздел 4.1-4.2; последний также обсуждает смягчение проблем точности, связанных с подходом подстановки к свободным переменным.

После вычисления направления поиска рассчитывается максимально возможный размер шага, который не активирует ограничения неотрицательности, и применяется меньший из этого размера шага и единицы (как в [4] Раздел 4.1.) [4] Раздел 4.3 предлагает улучшения для выбора размера шага.

Новая точка проверяется согласно условиям завершения [4] Раздел 4.5. Тот же допуск, который можно установить с помощью tol опция, используется для всех проверок. (Возможным улучшением было бы предоставить возможность независимой настройки различных допусков.) Если оптимальность, неограниченность или несовместность обнаружены, процедура решения завершается; в противном случае она повторяется.

В то время как верхний уровень linprog модуль ожидает задачу вида:

Минимизировать:

c @ x

При условии:

A_ub @ x <= b_ub
A_eq @ x == b_eq
 lb <= x <= ub

где lb = 0 и ub = None если не установлено в bounds. Задача автоматически преобразуется к виду:

Минимизировать:

c @ x

При условии:

A @ x == b
    x >= 0

для решения. То есть, исходная задача содержит ограничения равенства, верхней границы и переменных, тогда как специфичный для метода решатель требует ограничений равенства и неотрицательности переменных. linprog преобразует исходную задачу к стандартной форме, преобразуя простые границы в ограничения верхней границы, вводя неотрицательные дополнительные переменные для ограничений-неравенств и выражая неограниченные переменные как разность двух неотрицательных переменных. Задача преобразуется обратно в исходную форму перед отчётом результатов.

Ссылки

[4] (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16)

Андерсен, Эрлинг Д., и Кнуд Д. Андерсен. «Внутренний точечный оптимизатор MOSEK для линейного программирования: реализация однородного алгоритма». Высокопроизводительная оптимизация. Springer US, 2000. 197-232.

[6] (1,2)

Фройнд, Роберт М. "Прямо-двойственные внутренние методы для линейного программирования на основе метода Ньютона." Неопубликованные конспекты курса, март 2004. Доступно 25.02.2017 на https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf

[8]

Андерсен, Эрлинг Д., и Кнуд Д. Андерсен. «Предварительное решение в линейном программировании». Математическое программирование 71.2 (1995): 221-245.

[9]

Bertsimas, Dimitris, и J. Tsitsiklis. «Введение в линейное программирование.» Athena Scientific 1 (1997): 997.

[10]

Andersen, Erling D., et al. Implementation of interior point methods for large scale linear programming. HEC/Universite de Geneve, 1996.