НЕЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
НЕЛИНЕ́ЙНОЕ ПРОГРАММИ́РОВАНИЕ, раздел математич. программирования, посвящённый теории и методам нахождения экстремумов нелинейных функций многих переменных при наличии дополнительных условий на эти переменные. Общая постановка задачи Н. п. состоит в следующем: максимизировать целевую функцию $f(x)$ при условиях$$g_i(x)⩾0,\; i=1,\:\dots,\: m;\\h_j(x)=0,\; j=1,\:\dots,\: k,$$где $x=(x_1,\dots, x_n)$. В соответствии с общей терминологией математич. программирования точка $x$, удовлетворяющая всем $m+k$ ограничениям задачи, называется допустимой или допустимым решением задачи Н. п. Допустимая точка, в которой $f$ принимает наибольшее значение по сравнению с др. допустимыми точками (близкими к данной), называется (локально) оптимальной или (локально) оптимальным решением. В зависимости от свойств функций $f, g_i, h_j$ в Н. п. выделяются разделы, среди которых – выпуклое программирование и квадратичное программирование ($f$ – квадратичная форма или сумма квадратичной и линейной форм, а $g_i, h_j$ – линейные функции).
Основой всех численных методов Н. п. являются условия оптимальности. Необходимые условия оптимальности первого порядка состоят в следующем. Если $x^*$ – локально оптимальная точка, то при выполнении некоторых дополнит. условий существуют такие числа (множители Лагранжа) $y^*_1,\:\dots,\: y^*_m$ и $z^*_1,\:\dots,\: z^*_k$, что все частные производные $𝜕L(x, y^*, z^*)/𝜕x_l$ функции Лагранжа$$L(x, y^*, z^*)=f(x) + \sum_{i=1}^{m}y^*_ig_i(x)+\sum_{j=1}^{k}z^*_jg_j(x)$$
задачи Н. п. обращаются в нуль при $x=x^*$, т. е.$$\frac {\partial L(x^*, y^*, z^*)}{\partial x_l}=0,\; l=1,\:\dots,\: n,$$причём , $i=1,\:\dots,\: m$. Это утверждение обобщает хорошо известное в математич. анализе необходимое условие экстремума для дифференцируемой функции $φ (t)$ одной переменной: $φ′ (t^*)= 0$, если $t^*$ – локально оптимальная точка. Необходимые (достаточные) условия оптимальности второго порядка для задачи Н. п. являются обобщениями аналогичных условий того, чтобы функция $φ(t)$ достигала в точке $t^*$ своего локального максимума: $φ′(t^*)=0,\: {φ}''(t^*)⩽0\: (φ′(t^*)=0,\: {φ}''(t^*)<0)$, они формулируются с помощью первых и вторых частных производных функций $f, g_i, h_j$.
Одним из наиболее распространённых методов Н. п. является метод штрафных функций. С его помощью задача Н. п. с ограничениями сводится к задаче Н. п. без ограничений путём формирования штрафной функции, образующейся из целевой функции вычитанием «штрафов» за нарушение ограничений. Чем выше штрафы, тем ближе задача максимизации штрафной функции к исходной задаче. Для оптимизации штрафной функции используются разл. методы безусловной максимизации (см. Безусловной минимизации методы; изменение знака целевой функции сводит задачу максимизации к задаче минимизации).
Методы Н. п. позволяют, как правило, получить точку, удовлетворяющую с определённой погрешностью тем или иным условиям оптимальности. Они приводят, вообще говоря, к локальному оптимуму (исключением являются задачи Н. п., в которых каждый локальный оптимум является оптимальной точкой, напр. задачи выпуклого программирования). Методы Н. п., которые гарантированно приводят к оптимальной точке в любой задаче Н. п., требуют просмотра весьма большого числа точек, а поэтому применимы лишь для задач Н. п. с малым числом переменных. Поэтому для реализации даже самых эффективных методов Н. п. необходимо применение высокопроизводительных ЭВМ.
Для решения задач Н. п. создан ряд пакетов программ. Эти пакеты содержат как оптимизационные модули, реализующие разл. методы Н. п., так и сервисные программы, облегчающие пользователю процесс общения с ЭВМ.