Нелинейное программирование

В математике нелинейное программирование ( НЛП ) — это процесс решения задачи оптимизации , где некоторые ограничения не являются линейными равенствами или целевая функция не является линейной функцией . Задача оптимизации — это вычисление экстремумов (максимумов, минимумов или стационарных точек) целевой функции по набору неизвестных действительных переменных и условий выполнения системы равенств и называются неравенств , которые в совокупности ограничениями . Это раздел математической оптимизации , который занимается нелинейными задачами.

Определение и обсуждение

Пусть n , m и p — положительные целые числа. Пусть X — подмножество R ^н (обычно с коробчатыми ограничениями), пусть f , g _i и h _j — вещественнозначные функции на X для каждого i в { 1 , ..., m } и каждого j в { 1 , ..., p }, причем по крайней мере один из f , g _i и h _j является нелинейным.

Задача нелинейного программирования — это задача оптимизации вида

{\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}

В зависимости от набора ограничений существует несколько возможностей:

допустимая проблема – это такая проблема, для которой существует хотя бы один набор значений переменных выбора, удовлетворяющий всем ограничениям.
задачей невыполнимой является задача, для которой ни один набор значений переменных выбора не удовлетворяет всем ограничениям. То есть ограничения взаимно противоречивы, и решения не существует; допустимое множество — это пустое множество .
Неограниченная задача — это осуществимая задача, для которой целевую функцию можно сделать лучше, чем любое заданное конечное значение. Таким образом, оптимального решения не существует, поскольку всегда существует допустимое решение, которое дает лучшее значение целевой функции, чем любое предложенное решение.

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

Некоторые частные случаи нелинейного программирования имеют специализированные методы решения:

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

Применимость

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

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

Методы решения общей нелинейной программы

Аналитические методы

При условиях дифференцируемости и ограничений условия Каруша – Куна – Такера (ККТ) обеспечивают необходимые условия для оптимальности решения. Если некоторые из функций недифференцируемы, субдифференциальные версии условий Каруша – Куна – Такера (ККТ) . доступны ^[1]

При выпуклости условия ККТ достаточны для глобального оптимума . Без выпуклости эти условия достаточны только для локального оптимума . В некоторых случаях число локальных оптимумов невелико, и их все можно найти аналитически и найти тот, для которого объективное значение наименьшее. ^[2]^{: Раздел 5}

Числовые методы

В большинстве реальных случаев очень сложно решить условия ККТ аналитически, поэтому задачи решаются численными методами . Эти методы являются итеративными: они начинаются с начальной точки, а затем переходят к точкам, которые должны быть ближе к оптимальной точке, используя некоторое правило обновления. Существует три типа правил обновления: ^[2]^: 5.1.2

Подпрограммы нулевого порядка – используют только значения целевой функции и функций ограничений в текущей точке;
Подпрограммы первого порядка – используйте также значения градиентов этих функций;
Подпрограммы второго порядка — используйте также значения гессианов этих функций.

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

Ветвь и граница

Другой метод предполагает использование методов ветвей и границ , когда программа делится на подклассы, которые необходимо решить с помощью выпуклых (задача минимизации) или линейных аппроксимаций, которые образуют нижнюю границу общей стоимости внутри подразделения. При последующих делениях в какой-то момент будет получено фактическое решение, стоимость которого равна наилучшей нижней границе, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, и не единственным. Алгоритм также может быть остановлен раньше, с уверенностью, что наилучшее возможное решение находится в пределах допуска от найденной лучшей точки; такие точки называются ε-оптимальными. Завершение до ε-оптимальных точек обычно необходимо для обеспечения конечного завершения. Это особенно полезно для больших, сложных задач и задач с неопределенными затратами или значениями, где неопределенность можно оценить с помощью соответствующей оценки надежности.

Реализации

Существует множество решателей нелинейного программирования, в том числе с открытым исходным кодом:

ALGLIB (C++, C#, Java, Python API) реализует несколько решателей нелинейного программирования первого порядка и без производных.
NLopt (реализация C/C++ с многочисленными интерфейсами, включая Julia, Python, R, MATLAB/Octave), включает в себя различные решатели нелинейного программирования.
SciPy (де-факто стандарт научного Python) имеет решатель scipy.optimize, который включает в себя несколько алгоритмов нелинейного программирования (нулевого, первого и второго порядка).
IPOPT (реализация C++ с многочисленными интерфейсами, включая C, Fortran, Java, AMPL, R, Python и т. д.) — это решатель метода внутренней точки (производные нулевого порядка и, возможно, первого и второго порядка).

Численные примеры

2-мерный пример

Простая задача (показана на схеме) может быть определена ограничениями ${\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\x_{1}^{2}+x_{2}^{2}&\geq 1\\x_{1}^{2}+x_{2}^{2}&\leq 2\end{aligned}}$ с целевой функцией, которую необходимо максимизировать $f(\mathbf {x} )=x_{1}+x_{2}$ где $Икс знак равно (Икс 1, Икс 2)$ .

3-мерный пример

Другая простая задача (см. диаграмму) может быть определена ограничениями ${\begin{aligned}x_{1}^{2}-x_{2}^{2}+x_{3}^{2}&\leq 2\\x_{1}^{2}+x_{2}^{2}+x_{3}^{2}&\leq 10\end{aligned}}$ с целевой функцией, которую необходимо максимизировать $f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}$ где $Икс знак равно (Икс 1, Икс 2, Икс 3)$ .

См. также

Подгонка кривой
Минимизация методом наименьших квадратов
Линейное программирование
нл (формат)
Нелинейный метод наименьших квадратов
Список программного обеспечения для оптимизации
Квадратичное программирование с квадратичными ограничениями
Вернер Фенхель , создавший основу нелинейного программирования.

Ссылки

^ Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . стр. xii+454. ISBN 978-0691119151 . МР 2199043 .
^ Jump up to: ^а ^б Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

Дальнейшее чтение

Авриэль, Мордехай (2003). Нелинейное программирование: анализ и методы. Дуврское издательство. ISBN 0-486-43227-0 .
Базараа, Мохтар С. и Шетти, CM (1979). Нелинейное программирование. Теория и алгоритмы. Джон Уайли и сыновья. ISBN 0-471-78610-1 .
Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006). Численная оптимизация: Теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. дои : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-Х . МР 2265882 .
Люенбергер, Дэвид Г .; Йе, Иньюй (2008). Линейное и нелинейное программирование . Международная серия по исследованию операций и науке управления. Том. 116 (Третье изд.). Нью-Йорк: Спрингер. стр. xiv+546. ISBN 978-0-387-74502-2 . МР 2423726 .
Носедал, Хорхе и Райт, Стивен Дж. (1999). Численная оптимизация. Спрингер. ISBN 0-387-98793-2 .
Ян Бринхейс и Владимир Тихомиров, Оптимизация: идеи и приложения , 2005, Princeton University Press.

Внешние ссылки

Глоссарий по математическому программированию

[1] Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . стр. xii+454. ISBN 978-0691119151 . МР 2199043 .

[:0-2] Jump up to: ^а ^б Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

[1]

[2]