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

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

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

Пусть 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, который включает в себя несколько алгоритмов нелинейного программирования (нулевого, первого и второго порядка).

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

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

Простая задача (показана на диаграмме) может быть определена ограничениями

х ₁ ≥ 0

х ₂ ≥ 0

х ₁² + х ₂² ≥ 1

х ₁² + х ₂² ≤ 2

с целевой функцией, которую необходимо максимизировать

ж ( Икс ) знак равно Икс ₁ + Икс ₂

где Икс знак равно ( Икс ₁ , Икс ₂ ).

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

Другая простая задача (см. диаграмму) может быть определена ограничениями

Икс ₁² - Икс ₂² + Икс ₃² ≤ 2

х ₁² + х ₂² + х ₃² ≤ 10