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

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

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

Предмет и назначение

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

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

Задачи НЛП возникают во многих областях:

• Инженерное проектирование (оптимизация конструкций, процессов).
• Экономика и финансы (оптимизация портфеля с учетом риска, моделирование рынка).
• Химическая технология (оптимизация режимов реакторов).
• Машинное обучение (обучение нейронных сетей, метод опорных векторов).
• Управление производственными процессами. Логистика (с учетом нелинейных затрат).

Математическая постановка задачи НЛП

Общая задача нелинейного программирования формулируется следующим образом:

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

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

Отличия от линейного программирования

Нелинейное программирование существенно отличается от линейного программирования (ЛП):

• Нелинейность: Целевая функция или ограничения (или и то, и другое) содержат нелинейные зависимости.
• Свойства ОДР: Область допустимых решений в НЛП может быть невыпуклой (в отличие от ЛП, где ОДР всегда выпуклый многогранник).
• Свойства оптимума: Оптимальное решение в НЛП не обязательно находится в вершине ОДР, оно может лежать на границе или внутри области. В НЛП могут существовать локальные оптимумы, которые не являются глобальными.
• Сложность решения: Задачи НЛП, как правило, значительно сложнее для решения, чем задачи ЛП. Не существует единого универсального алгоритма, аналогичного симплекс-методу, для всех задач НЛП.

Основные трудности и вызовы НЛП

Решение задач нелинейного программирования сопряжено с рядом трудностей:

• Наличие локальных экстремумов: Большинство методов НЛП гарантируют нахождение только локального оптимума (решения, лучшего в некоторой окрестности). Поиск глобального оптимума (наилучшего решения во всей ОДР) является сложной задачей, особенно для невыпуклых проблем.
• Невыпуклость: Если задача не является выпуклой (целевая функция или ОДР невыпуклы), то может существовать множество локальных оптимумов, и стандартные градиентные методы могут "застрять" в одном из них.
• Вычислительная сложность: Алгоритмы решения НЛП часто требуют значительно больших вычислительных ресурсов по сравнению с ЛП.

Важные классы задач НЛП

Несмотря на общую сложность, существуют важные подклассы задач НЛП, для которых разработаны эффективные методы решения:

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

Методы решения задач НЛП

Методы решения задач нелинейного программирования (НЛП)

I. Методы безусловной оптимизации (оптимизация без ограничений):

• Градиентные методы (метод наискорейшего спуска, метод сопряжённых градиентов);
• Метод Ньютона и квазиньютоновские методы (например, BFGS);
• Методы с использованием аппроксимации Гессиана.

II. Методы условной оптимизации (оптимизация с ограничениями):

• Методы преобразования:
  • Метод штрафных функций (penalty methods);
  • Метод барьерных функций (barrier methods).
• Методы прямого поиска направлений:
  • Метод возможных направлений.
• Методы на основе условий оптимальности:
  • Методы Каруша-Куна-Таккера (KKT-условия);
  • Метод множителей Лагранжа.
• Итерационные методы:
  • Последовательное квадратичное программирование (SQP);
  • Методы внутренних точек.

III. Методы глобальной оптимизации:

• Эвристические и метаэвристические методы:
  • Генетические алгоритмы;
  • Имитация отжига;
  • Поиск с запретами (tabu search).
• Детерминированные методы:
  • Ветвление и границы (branch and bound);
  • Алгоритмы глобальной оптимизации для задач со специальной структурой.

Литература

• Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.: Мир, 1982.
• Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. — М.: Мир, 1972.
• Химмельблау Д. Прикладное нелинейное программирование. — М.: Мир, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

См. также

• Исследование операций
• Оптимизация
• Линейное программирование
• Выпуклое программирование
• Целевая функция
• Ограничения
• Область допустимых решений