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

Нелинейное программирование является частным случаем математического программирования и подразумевает нелинейную форму целевой функции или ограничения. Задачу, решаемую данным методом, можно сформулировать в виде задачи поиска оптимального значения некой целевой функции при выполнении условий, где — параметры, — ограничения, n — количество параметров, s — количество ограничений.

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

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