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

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

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

Пусть 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}}

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

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

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

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

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

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

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

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

Методы решения общей нелинейной задачи

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

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

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

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

В большинстве реалистичных случаев очень сложно решить условия KKT аналитически, поэтому задачи решаются с помощью численных методов . Эти методы итеративные: они начинаются с начальной точки, а затем переходят к точкам, которые предположительно находятся ближе к оптимальной точке, используя некоторое правило обновления. Существует три вида правил обновления: ^[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-мерный пример

Простую задачу (показанную на схеме) можно определить с помощью ограничений с целевой функцией, которую необходимо максимизировать, где $x$ $= ($ $x$ $1$ $,$ $x$ $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}$

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

Другая простая задача (см. диаграмму) может быть определена ограничениями с целевой функцией, которую необходимо максимизировать, где $x$ $= ($ $x$ $1$ $,$ $x$ $2$ $,$ $x$ $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}$

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

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

Ссылки

^ Ruszczyński, Andrzej (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Princeton University Press . стр. xii+454. ISBN 978-0691119151. МР 2199043.
^ ab Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

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

Авриэль, Мордехай (2003). Нелинейное программирование: анализ и методы. Dover Publishing. ISBN 0-486-43227-0 .
Базараа, Мохтар С. и Шетти, К. М. (1979). Нелинейное программирование. Теория и алгоритмы. John Wiley & Sons. ISBN 0-471-78610-1 .
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе пересмотренное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. МР 2265882.
Luenberger, David G. ; Ye, Yinyu (2008). Линейное и нелинейное программирование . Международная серия по исследованию операций и науке управления. Т. 116 (третье изд.). Нью-Йорк: Springer. С. xiv+546. ISBN 978-0-387-74502-2. МР 2423726.
Нокедаль, Хорхе и Райт, Стивен Дж. (1999). Численная оптимизация. Springer. ISBN 0-387-98793-2 .
Ян Бринкхейс и Владимир Тихомиров, Оптимизация: идеи и приложения , 2005, Princeton University Press

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

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