MINOS - это программный пакет Fortran для решения линейных и нелинейных задач математической оптимизации . MINOS (модульная система нелинейной оптимизации в ядре) может использоваться для линейного программирования, квадратичного программирования и более общих целевых функций и ограничений, а также для поиска допустимой точки для набора линейных или нелинейных равенств и неравенств. [1]
MINOS был впервые разработан Брюсом Муртагом и Майклом Сондерсом , в основном в Лаборатории оптимизации систем Департамента исследований операций Стэнфордского университета. [2] В 1985 году Сондерс был награжден первой премией Орчарда-Хейса [3] от Общества математического программирования (ныне Общество математической оптимизации ) за его работу над MINOS. Несмотря на то, что пакет является одним из первых появившихся решателей ограниченной оптимизации общего назначения, он по-прежнему активно используется. MINOS поддерживается в AIMMS , AMPL , APMonitor , GAMS и TOMLAB.системы моделирования. Кроме того, он остается одним из наиболее часто используемых решателей на сервере NEOS [4] [5] и в GAMS . [6]
Операция [ править ]
В идеале пользователь должен предоставлять градиенты нелинейных функций. (Это происходит автоматически в большинстве упомянутых выше систем моделирования.) Если некоторые или все градиенты не предоставлены, MINOS аппроксимирует недостающие с помощью конечных разностей, но это может быть медленным и менее надежным. Если целевая функция выпуклая, а ограничения линейны, полученное решение будет глобальным минимизатором. В противном случае полученное решение может быть локальным минимизатором.
Для линейных программ используется двухфазный простой симплекс-метод . Первая фаза сводит к минимуму сумму невозможностей. Для задач с линейными ограничениями и нелинейной целью используется метод пониженного градиента. Квазиньютоновское приближение сокращенного гессиана поддерживается для получения направлений поиска. Этот метод наиболее эффективен, когда в решении активно много ограничений или границ.
Для задач с нелинейными ограничениями используется метод Лагранжа с линейными ограничениями. [7] Это включает в себя последовательность основных итераций, каждая из которых решает (возможно, приближенно) подзадачу с линейными ограничениями. Цель подзадачи - это расширенный лагранжиан , а ограничения подзадачи - это линеаризации нелинейных ограничений в текущей точке.
MINOS предназначен для больших разреженных задач. Нет фиксированного ограничения на размер проблемы. Большая часть рабочей памяти содержится в одном массиве двойной точности (который должен быть достаточно большим). Исходный код подходит для всех научных машин с компилятором Fortran.
Ссылки [ править ]
- ^ Б. Мерта, М. Сондерс (2003). «Руководство пользователя MINOS 5.51» (PDF) . Цитировать журнал требует
|journal=( помощь ) - ^ Б. Мерта, М. А. Сондерс (1978). «Масштабная оптимизация с линейными ограничениями» (PDF) . Математическое программирование . 14 : 41–72.
- ^ Победителей Бил-Орчард-Hays премии
- ^ Сервер NEOS
- ^ Сондерс, Майкл (2013). Алгоритмы и программное обеспечение оптимизации в SOL (PDF) .
- ^ Руководство по GAMS / MINOS Solver
- ^ Подробнее, Хорхе Дж .; Райт, Стивен Дж. (1993). «Глава 8: Оптимизация с ограничениями». Руководство по оптимизации программного обеспечения . Границы прикладной математики. DOI : 10.1137 / 1.9781611970951.ch8 .
Дальнейшее чтение [ править ]
- Б.А. Муртаг, М.А. Сондерс (1982). «Спроектированный алгоритм Лагранжа и его реализация для разреженных нелинейных ограничений» (PDF) . Математическое программирование . 16 : 84–117.
Внешние ссылки [ править ]
- Лаборатория системной оптимизации, Лаборатория системной оптимизации Стэнфордского университета (SOL).
- MINOS 5.5 - Описание - Распространители программного обеспечения.
