Каноническая форма записи и условия оптимальности решения для усредненной задачи нелинейного программирования

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

Приведем несколько постановок усредненных задач, отличающихся от рассмотренной выше.

1. Задача о максимуме функции от среднего значения аргумента:

Здесь D — множество допустимых решений исходной задачи нелинейного программирования, задаваемое условиямиДх) = 0, а х — среднее значение вектора х на множестве D.

Так как множество значений х, удовлетворяющих этим условиям, представляет собой выпуклую оболочку множества D, то задача (3.19) эквивалентна задаче НП, но на множестве значений аргумента, совпадающим с выпуклой оболочкой CoD множества D:

2. Задача о максимуме среднего значения функции при связях, наложенных на среднее значение аргумента:

или в более полной записи:

3. Задача о максимуме функции от среднего значения х при усреднненых связях:

Каждая из перечисленных задач является расширением по отношению к задаче нелинейного программирования, а искомым их решением является распределение р (х).

Доказывать условия оптимальности для каждого варианта постановки усредненной задачи нет смысла. Значительно удобнее получить условия оптимальности для некоторой канонической формы усредненной задачи и пользоваться ими в каждом конкретном случае, записав задачу в этой форме^[1].

При получении условий оптимальности требуется ответить на два вопроса:

• 1) всегда ли оптимальное распределение, являющееся одной из составляющих решения усредненной задачи, сосредоточено в конечном числе базовых точек?
• 2) если да, то каково предельное число этих точек?

Приведенные ниже необходимые условия оптимальности дают положительный ответ на первый вопрос и позволяют найти предельное число базовых точек.

Обозначим через у вектор детерминированных переменных, а через х вектор рандомизированных переменных. Для первого из них требуется найти оптимальное значение, а для второго — оптимальную меру. Запишем каноническую форму усредненной задачи:

при условиях.

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

Обозначим через к размерность вектора х, а через п размерность вектор-функции/. Функцию F предполагают непрерывно дифференцируемой по всем переменным, а / — непрерывной по х и непрерывно дифференцируемой по у.

Доказано^[2], что оптимальная мера р" (х), определенная на множестве V# сосредоточена не более чем в L + 1 базовых точках, причем L = п + к.

Таким образом,.

Поэтому на оптимальном решении а условия (3.22) примут форму.

С учетом этих выражений задача (3.21), (3.22) становится обычной задачей НП относительно у_г, У, х¹. Условия теоремы Куна — Таккера сводятся к стационарности по х¹, у и неулучшаемости по у_г функции Лагранжа этой задачи (решение предполагаем невырожденным, так что Х₀ = 1):

Для записи условий оптимальности введем обозначения:

В этих обозначениях условия неулучшаемости R по у₁ запишутся как требование максимума по х е V_x в точках х¹ выражения.

так что.

условия стационарности Л по у имеют вид.

Требование максимума С (х) вместе с уравнениями (3.25), условиями (3.22) и условиями дополняющей нежесткости.

позволяют найти решение у_г*, у*,х¹.

Для конкретной постановки усредненной задачи используют следующий алгоритм действий.

• 1. Записывают условия задачи в канонической форме (3.21), (3.22).
• 2. Выделяют рандомизированные и детерминированные переменные.
• 3. Подсчитывают общее число L усреднений, равное суммарной размерности вектора рандомизированных переменных и размерности вектора усредняемых функций.
• 4. Формируют функции ЯиСи подставляют их в выражения (3.24) — (3.26).

Например, в задаче (3.20).

Величина L равна к, а функция.

В (3.24) а₀ = Л₀ = 1, a_v = 0 при v > 0, а

В базовых точках х¹, число которых не превышает к + 1, выражение.

максимально, и условия (3.22), имеющие вид выполнены.

• [1] Цирлин А. М. Задачи и методы усредненной оптимизации // Труды Математического института имени В. А. Стеклова. 2008. Т. 261. С. 1—17.
• [2] Там же.