Автоматика и телемеханика, № 8, 2023

Нелинейные системы

(Институт программных систем им. А.К. Айламазяна РАН,

Переславль-Залесский)

ОБОБЩЕНИЕ ТЕОРЕМЫ КАРАТЕОДОРИ

И ПРИНЦИП МАКСИМУМА В УСРЕДНЕННЫХ ЗАДАЧАХ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ¹

Рассмотрена связь между усреднением функций по времени и ее усред-

нением по множеству значений искомых переменных. Исследованы зада-

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

функций или функции от средних значений переменных. Показано, что

условия оптимальности этих задач имеют форму принципа максимума,

а их оптимальное решение во временной области — кусочно-постоянная

функция. Доказано обобщение теоремы Каратеодори о выпуклых оболоч-

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

программирования с усреднением по части переменных и функциями, за-

висящими от средних значений переменных.

Ключевые слова: усредненные ограничения, скользящие режимы, выпук-

лые оболочки функций, функция достижимости, принцип максимума в

усредненных задачах.

DOI: 10.31857/S0005231023080044, EDN: HBDMDH

1. Введение

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

ничений усредненно зависят от всех или от части переменных. Такие задачи

возникают, когда в технологических процессах некоторые подлежащие выбо-

ру переменные должны быть неизменны (конструктивные параметры), а дру-

гие могут изменяться во времени, причем наличие устройств, сглаживающих

колебания, например емкостей, приводит к усредненному влиянию этих изме-

нений [1]. Такие задачи возникают при оптимальном управлении макросисте-

мами (системами, состоящими из множества индивидуально не управляемых

элементов), в которых можно управлять только средними по множеству этих

элементов показателями. Все подобные задачи называют задачами усреднен-

ной оптимизации.

В системах, у которых множество допустимых управлений невыпукло,

в частности в релейных системах, оптимальным решением часто оказывается

¹ Работа выполнена при финансовой поддержке Российского научного фонда (проект

20-61-46013).

скользящий режим, в котором изменение состояния объекта усредненно за-

висит от сколь угодно часто переключающегося управления [2-5]. Усреднен-

ные задачи возникают также как вспомогательные оценочные при оптимиза-

ции циклических режимов, когда введение усреднения расширяет множество

допустимых решений и упрощает решение, позволяя получить оценку эф-

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

Значение такой оценочной задачи заведомо «не хуже», чем значение исход-

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

оптимального решения исходной. Для определенности будем рассматривать

задачи на максимум критерия оптимальности.

В первом разделе данной работы обсудим связь между усреднением функ-

ций, аргумент которых изменяется во времени, по множеству значений этого

аргумента и по времени и определим, что является искомым решением усред-

ненной задачи и как это решение может быть реализовано.

Во втором разделе сформулируем теорему об условиях оптимальности за-

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

и ограничений и дадим ее доказательство, базирующееся на теореме Кара-

теодори о выпуклых оболочках функций.

В третьем разделе рассмотрим возможные обобщения доказанной тео-

ремы.

2. О связи между усреднением по времени

и усреднением по множеству

Среднее значение непрерывной скалярной функции f(x(t)), t ∈ [0, τ],

x ∈ V ⊂ Rⁿ может быть вычислено по времени как

∫

(1)

f_t(x) =

f (x(t))dt

либо по множеству как

∫

(2)

f_p(x) =

f (x)p(x)dx.

Функцию p(x) называют плотностью распределения. В том случае, когда

x(t) — случайная функция, p(x) — плотность распределения случайной вели-

чины. Она неотрицательна, и ее интеграл на V равен единице. В частности,

множество V может быть паралелепипедом в Rⁿ. В нашем случае x(t) —

детерминированная функция, поэтому остановимся подробнее на свойствах

p(x) такой, чтобы результаты усреднения по формулам (1) и (2) были одина-

ковы.

Будем считать переменную x скалярной, множество V здесь и ниже огра-

ниченным и замкнутым и введем функцию θ(x₀), x₀ ∈ V , равную суммар-

ной продолжительности тех интервалов времени t, для которых x(t) ≤ x₀.

Очевидно, что эта функция не превосходит τ. Через P (x₀) обозначим отно-

шениеθ(x0)_τ , т.е. долю интервала [0, τ], для которой x(t) ≤ x₀. Эта функция

монотонно растет с ростом x₀, изменяясь от нуля до единицы. Она аналогич-

на функции распределения случайной величины.

Плотность распределения равна

dP (x₀)

1 dθ(x₀)

(3)

p(x₀) =

∑



dx₀

τ dx₀

 dxν



xν=x0

Интервал θ увеличивается с ростом x₀ при любом знаке производной при тех

значениях x_ν функции x(t), в которых она равна x₀.

Если при некотором значении x₀ функция x(t) постоянна в течение до-

ли γ от интервала [0, τ], то функция P (x₀) испытывает в этой точке скачок

величиной γ, а плотность распределения в ней равна γδ(x - x₀).

Примеры

1. Линейные функции. Пусть x(t) =^htτ . Тогда по формуле (3) получим

p(x) =1h = const. Та же плотность распределения соответствует и всем тре-

угольникам с основанием [0, τ] и высотой h.

2. Кусочно-постоянные функции. Эти функции принимают дискретные

значения x_i, каждое в течение доли γ_i от интервала [0, τ]. Любой такой функ-

ции по формуле (3) соответствует плотность распределения

∑

(4)

p(x₀) =

γ_iδ(x - x_i), γ_i > 0,

γ_i

= 1.

Порядок, в котором кусочно-постоянная функция принимает то или иное из

возможных значений, роли не играет.

Из этих примеров видно, что каждой функции x(t) соответствует плот-

ность распределения ее значений p(x), определенная на V , а каждой плот-

ности распределения соответствует сколь угодно много функций x(t), для

которых f_p(x) = f_t(x). Исключением является плотность распределения ви-

да p(x) = δ(x - x₁). В этом случае соответствующая ей функция равна

x(t) = x₁ = const на всем интервале [0, τ], и она единственна.

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

от двух, переменных x₁(t) и x₂(t). В этом случае функция P (x⁰) распределе-

ния значений вектора x представляет собой долю интервала [0, τ], для кото-

рой выполнено два неравенства: x₁(t) ≤ x⁰¹ и x₂(t) ≤ x⁰². Эта функция моно-

тонно растет с ростом каждого из аргументов, когда первая из составляющих

вектора x⁰ максимальна (p₁(x₁) = 1), она равна P (x⁰²), а ее производная рав-

на плотности распределения p(x^max1, x₂) = p₂(x₂), аналогично в случае, когда

x₂ = x^max2, p(x^max2,x₁) = p₁(x₁). Функции x₁(t) и x₂(t) не зависимы друг от

друга, так что p(x₁, x₂) = p₁(x₁)p₂(x₂).

Искомым решением задачи усредненной оптимизации является плотность

распределения p^∗(x) вектора x на множестве V его допустимых значений.

Для реализации этого решения во времени нужно найти одну из возмож-

ных функций x(t), имеющих распределение p^∗(x). Решение этой последней

задачи существенно облегчается особенностями оптимальных решений p^∗(x),

доказанными в следующем разделе.

3. Об оптимальном решении задач усредненной оптимизации

Будем обозначать операцию усреднения чертой, прoведенной над усред-

няемой функцией или вектором. Так,

∫

x = xp(x)dx, f(x) = f(x)p(x)dx.

Простейшей задачей усредненной оптимизации является задача о макси-

муме среднего значения скалярной функции f(x) при заданном среднем зна-

чении ее аргумента:

∕

(5)

f (x) → max x = x₀, x ∈ V ⊂ Rⁿ.

Или в более подробной записи

∫

∕∫

∫

(6)

f (x)p(x)dx → max

xp(x)dx = x₀, p(x) ≥ 0,

p(x)dx = 1.

Искомой в этой задаче является p(x) (плотность распределения вектора ис-

комых переменных). Эта функция неотрицательна, и интеграл от нее на мно-

жестве V равен единице.

4. Теорема Каратеодори о выпуклых оболочках функций

Теорема Каратеодори [3, 4, 6] о выпуклых оболочках множеств утвержда-

ет, что любой элемент выпуклой оболочки CoD компактного множества D

в евклидовом пространстве размерности n может быть представлен как эле-

мент симплекса, имеющего не более чем n + 1 вершину (базовые точки), каж-

дая их которых принадлежит D.

В частности, множеством D может быть подграфик фунции f(x). Выпук-

лой оболочкой функции называют выпуклую оболочку подграфика. Функ-

ция, зависящая от n переменных, представляет собой границу множества в

пространстве Rn+1, имеющую размерность n. Базовые точки заведомо ле-

жат на этой границе, а значит, их число не превышает n + 1. Ниже будем

называть теорему Каратеодори теоремой о выпуклых оболочках функций.

Ордината выпуклой оболочки функции f₀(x) в точке x₀, принадлежащей

выпуклой оболочке множества определения фунции, является значением за-

дачи

^∕ x_i = xi0, i = 1,n,

(7)

f₀(x) → max

p(x)

x∈V ⊂Rⁿ,

где V -компакт.

Согласно теореме Каратеодори оптимальное решение этой задачи имеет

вид

∑

p^∗(x) =

γ_jδ(x - x^j), γ_j ≥ 0,

γ_j = 1.

j=0

i=0

То есть оптимальное распределение сосредоточено не более чем в (n + 1)-й

базовых точках.

Этот факт позволяет переписать задачу (7) как задачу нелинейного про-

граммирования (НП)

∑

γ_jx^j = x₀,

∑

(8)

γ_jf₀(xj) → maxj=0

∑

j=0

x^j ∈ V ⊂ R^m,

γ_j = 1, γ_j ≥ 0,

j=0

переменными в которой являются базовые векторы x^j и вектор весовых коэф-

фициентов γ, и воспользоваться для ее решения теоремой Куна-Таккера [7]:

Если y^∗ является решением задачи нелинейного программирования

∕

(9)

f (y) → max ϕ_i(y) ≤ 0, y_j

≥ 0, i = 1, . . . , m, j = 1, . . . , n,

то найдется такой ненулевой вектор множителей

λ = λ₀,...,λ_m (λ₀ равно нулю или единице, λ_i ≤ 0 при i > 0),

что для функции Лагранжа

∑

R = λ₀f(y) + λ_iϕ_i(y)

i=1

справедливы условия:

⁽∂R⁾

(10)

= 0, если y^∗j > 0;

≤ 0, если y^∗j

= 0;

∂yjy=y∗

(11)

λ_i = 0, если ϕ_i(y^∗) < 0; λ_i ≤ 0, если ϕ_i(y^∗

) = 0.

Для задачи (8) функция Лагранжа имеет вид

[

]

∑

(12)

R = γ_j f₀(x^j) + λ_ix^ji - Λ

j=0

i=1

где Λ — множитель Лагранжа, соответствующий условию равенства суммы

весовых коэффициентов единице.

Условия Куна-Таккера по весовым коэффициентам приводят к требова-

ниям:

∑

(13)

R⁰(x_j,λ) = f₀(x^j) +

λ_ix^ji < Λ, если γ_j

= 0,

i=1

∑

R⁰(x_j,λ) = f₀(x^j) +

λ_ix^ji = Λ, если γ_j > 0, j = 0,... ,n + 1.

i=1

Здесь R⁰ - функция Лагранжа задачи (8) при отсутствии в ней усреднения.

Далее такую задачу будем называть исходной.

Таким образом: Для всех базовых значений x, входящих в оптимальное

решение задачи о выпуклой оболочке функции f₀ с ненулевым весом, функция

Лагранжа исходной задачи максимальна. Число таких точек не превышает

n + 1.

5. Задача с усреднением связей, обобщение теоремы Каратеодори

В задаче НП с усреднением функций, определяющих связи между пере-

менными, требуется достичь максимума среднего значения функции f₀(x)

на множестве V допустимых значений x при условии, что среднее значение

вектор-функции f(x) = (f₁(x), . . . , f_i(x), . . . , f_m(x)) равно нулю. Формально

∕

(14)

f₀(x) → max f_i(x) = 0, i = 1,... ,m, x ∈ V ∈ Rⁿ.

Теорема 1.

1. Оптимальная плотность распределения в задаче (14) имеет вид

∑

(15)

p^∗(x) =

γ_jδ(x - x^j), γ_j ≥ 0,

γ_j

= 1.

j=0

2. Найдется такой ненулевой вектор

λ = λ₀,...,λ_i,...,λ_m, λ₀ = (0;1),

что в каждой базовой точке x^j функция Лагранжа исходной задачи

∑

(16)

R= λ_if_i(x)

i=0

максимальна по x ∈ V .

Доказательство. Для доказательства этого утверждения введем по-

нятие функции достижимости задачи (14):

∕

(17)

f∗0(C) = maxf₀(x) f_k(x) = C_k

k = 1,...,m, x ∈ V.

Эта функция задана алгоритмически на множестве

V_c = {C ∈ R^m : f(x) = C,x ∈ V ⊂ Rⁿ} .

Она может быть негладкой и полунепрерывной сверху.

Справедливо

Утверждение. Для тех значений x, для которых f(x) = C, p^∗(x) за-

ведомо равна нулю, если f₀(x) = f∗0(C).

Таким образом, в решение усредненной задачи могут входить с ненулевым

весом только те значения x = x^∗(C), для которых величина f₀(x) совпадает

с ординатой функции достижимости. Если бы это утверждение было не вер-

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

значение f₀(x) увеличилось.

Так как для каждого C величина f₀ совпадает с ординатой функции до-

стижимости, задачу (14) можно переписать в форме

∕

(18)

f∗0(C) → max C_k = 0, k = 1,... ,m, C ∈ V_c ⊂ R^m.

Это задача об ординате выпуклой оболочки функции достижимости в нуле.

В соответствии с теоремой Каратеодори ее оптимальное решение равно

∑

(19)

p^∗(C) =

γ_jδ(C - C^j), γ_j ≥ 0,

γ_j

= 1.

j=0

Так как каждому базовому значению C^j соответствует значение x^j∗(C^j ), то

оптимальная плотность распределения в задаче (14) имеет вид (15). Первое

утверждение теоремы 1 доказано.

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

доказательство для задачи об ординате выпуклой оболочки функции с той

разницей, что функция Лагранжа неусредненной задачи имеет форму (16).

Подчеркнем, что число базовых точек не зависит от размерности вектора x,

а определяется размерностью m вектор-функции f.

Отметим, что здесь и ниже условия в форме принципа максимума не тре-

буют от функций, определяющих усредненную задачу, гладкости по x, мно-

жество V может быть неодносвязным [8-10].

Пример 1. Рассмотрим систему, состоящую из электродвигателя, вра-

щаемого им насоса и емкости, на рис. 1,а. Двигатель потребляет мощность n,

от которой зависит производительность насоса g. Зависимость g(n) показа-

на на рис. 1,б . Требуется найти режим, для которого при заданной сред-

ней затрачиваемой мощности n средняя производительность g максимальна.

Это задача об ординате выпуклой оболочки функции g(n) в точке n. Число

базовых точек равно двум, одна из них — начало координат, а вторая, n¹,

определена условием, что функция Лагранжа R = g(n) + λn в ней достигает

g(n)

n¹

Рис. 1. Система, состоящая из насоса и сглаживающей емкости (а);

зависимость расхода от затрачиваемой мощности (б).

максимума (такого же, как при n = 0). Исключая λ из условий максимума

функции Лагранжа и требования, чтобы этот максимум был равен нулю,

приходим к уравнению для n¹:

g(n)

dg(n)

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

каждого из них мощность насоса принимает значение ноль и n¹, причем доля

от интервала τ, для которой n = n¹, равна 1 -nn1 . Максимальное значение

интервала τ определяется величиной емкости G, оно равно

τ_max =

g(n¹)

Значение задачи равно

(

)

g^∗ = g(n¹)

n¹

Оно от G не зависит, и при стремлении емкости к нулю оптимальным реше-

нием становится скользящий режим.

6. Обобщения усредненной задачи НП

6.1. Усредненная задача с детерминированными переменными

Как указывалось во введении, в усредненных задачах может быть два типа

переменных — рандомизированные и детерминированные. По переменным

второго вида усреднение отсутствует. Рассмотрим задачу НП, в которой по

части переменных усреднение отсутствует.

Задача с усреднением по части переменных примет форму:

∕

(20)

f₀(x,y) → max f_j(x,y) = 0, x ∈ V ⊂ Rⁿ, y ∈ V_y ⊂ R^K

, j = 1,...,m,

функции f₀, . . . , f_m непрерывны и непрерывно дифференцируемы по сово-

купности аргументов, черта соответствует усреднению по x ∈ V , множества

V и V_y замкнуты и ограниченны.

Для любого y эта задача является усредненной задачей нелинейного про-

граммирования (14), а следовательно, в силу теоремы оптимальная плотность

распределения x сосредоточена не более, чем в (m + 1)-й базовых точках, так

∑_m

что p^∗(x) =

γ_jδ(x - x^j) и найдется такой ненулевой вектор λ, что в каж-

дой из этих точек функция Лагранжа исходной задачи

∑

(21)

R = λ_jf_j(x,y), x ∈ V ⊂ Rⁿ, y ∈ V_y ⊂ R^K

j=0

максимальна по x.

Функция Лагранжа задачи (20), в которой плотность распределения x рав-

на p^∗(x), имеет вид

∑

(22)

R^∗ = λ_j γ_if_j(xⁱ,y), xⁱ ∈ V ⊂ Rⁿ, y ∈ V_y ⊂ R^K.

j=0

i=0

Для любой плотности распределения p(x) рандомизированных перемен-

ных задача (20) представляет собой задачу нелинейного программирования и

согласно теореме Куна-Таккера найдется такой ненулевой вектор λ с соcтав-

ляющими λ₀ = (0; 1), λ_j , j = 1, . . . , m, что для функции (21) на оптимальном

решении выполнены условия локальной неулучшаемости по y

∂R^∗

(23)

δy_l

≤ 0, l = 1, . . . , K.

∂y_l

Здесь δy_l - допустимая вариация y_l.

Задача нелинейного программирования с усреднением по части перемен-

ных имеет много общего с задачей оптимального управления со связями в

форме дифференциальных уравнений. Там управляющие воздействия вхо-

дят в задачу так, что их сколь угодно быстрые изменения усредняются в

окрестности каждого момента времени, чего нельзя сказать о фазовых коор-

динатах. Именно поэтому условия в форме принципа максимума Понтрягина

справедливы для управляющих воздействий.

6.2. Задача, содержащая функции от средних значений переменных

Эта задача имеет вид

∕

(24)

f₀(x,x_l) → max f_j(x,x_l) = 0, x ∈ V ⊂ Rⁿ, l = 1,..., K ≤ n.

Введем обозначение: y_l = x_l. Переменная y_l принадлежит выпуклой обо-

лочке CoVxl множества допустимых значений x_l. С учетом введенных обо-

значений задачу (24) можно переписать в форме

∕

f₀(x,y) → max f_j(x,y) = 0, x_l -y_l = 0, x∈ V ⊂ Rⁿ, y_l ∈ CoV_x

(25)

⊂R^K.

При записи в такой форме задача (25) отличается от задачи (20) только до-

полнительными усредненными условиями x_l - y_l = 0. Функция Лагранжа ис-

ходной задачи примет форму

∑

(26)

R = λ_jf_j(x,y) + λ_l(x_l - y_l), x ∈ V ⊂ Rⁿ, y_l ∈ CoV_x

j=0

l=1

Из условий оптимальности (21), (23) следует, что максимальное число ба-

зовых значений x в задаче (24) равно m + K + 1 и что найдется такой нену-

левой вектор λ, что в каждой из базовых точек функция R, фигурирующая

в (26), достигает на оптимальном решении максимума по x, а по y функ-

ция (22) локально неулучшаема.

При решении усредненных задач выражают множители Лагранжа через

базовые значения x^j и y из условия максимума функции Лагранжа по x и ра-

венства этих максимумов друг другу и записывают условия неулучшаемости

по y. После этого из усредненных условий находят весовые коэффициенты

для каждой из базовых точек с учетом того, что сумма этих весовых коэф-

фициентов равна единице.

Пример 2. В качестве иллюстративного примера рассмотрим задачу

)

∕(

(27)

(x - x)² → min

= 1, x = -1; 0; 1.

x+x

Функция Лагранжа для этой задачи равна

(

)

(28)

L = (x - y)² + λ

+ μ(y - x).

x+y-1

Число усредненных условий равно двум, значит, все три допустимых значе-

ния x являются базовыми, и неопределенные множители надо выбрать так,

чтобы максимум функции L^∗ был в этих точках одинаков, что приводит к

условиям:

(

)

(

)

(29)

L^∗ = (1 + y)² + λ

-1

- μ(1 + y) = y² + λ

-1

− μy =

y-1

(

)

= (1 - y)² + λ

-1

+ μ(1 - y).

y+1

Откуда

y(2y - 1)

(30)

λ=

(1 - y - 2y²), μ =

2+y

После подстановки этих выражений в L^∗ и дифференцирования получивше-

гося выражения по y приходим к уравнению

(31)

3y³ + 17y²

+ 20y - 10 = 0.

С точностью до второго знака после запятой, y = 0,37. Весовые множите-

ли γ₁, γ₂, γ₃ для x = -1, x = 0, x = 1 соответственно можно теперь найти из

условий

∑

(32)

γ_i = 1,

γ_ix_i = 0,37,

= 1.

γ_i x_i + 0,37

i=1

Получим γ₁ = 0,155, γ₂ = 0,320, γ₃ = 0,525.

7. Заключение

Рассмотрены различные постановки задач НП с усреднением. Показано,

что с введением понятия о функции достижимости задачи НП задачи, содер-

жащие усреднение функций от вектора рандомизированных переменных x,

могут быть сведены к экстремальным задачам о выпуклых оболочках мно-

жеств и функций. Оптимальное распределение во всех этих задачах сосредо-

точено в дискретных «базовых» точках компактного множества V допусти-

мых значений x. Доказан принцип максимума для таких задач. Показано,

что число базовых точек не превышает числа усредненных условий в задаче

более чем на единицу. Критерий и ограничения усредненных задач нелиней-

ного программирования могут зависеть от времени. Если эти зависимости

непрерывны, то приведенные выше условия оптимальности справедливы для

каждого момента времени и определяют изменение во времени координат ба-

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

ветствующий оптимальному решению, доставляет минимум максимальному

по искомым переменным значению максимизируемой функции, что служит

основой для вычислительных алгоритмов.

СПИСОК ЛИТЕРАТУРЫ

1. Цирлин А.М. Оптимальные циклы и циклические режимы. М.: Энергоатомиз-

дат, 1983.

2. Розоноэр Л.И. Принцип максимума Л.С. Понтрягина в теории оптимальных

процессов // АиТ. 1959. № 10-12.

3. Юдин Д.Б. Математические методы управления в условиях неполной информа-

ции. М.: Советское радио, 1974.

4. Янг Л. Лекции по вариационному исчислению и теории оптимального управле-

ния. М.: Мир, 1977.

5. Цирлин А.М. Оптимизация в среднем и скользящие режимы в задачах оп-

тимального управления // Изв. АН СССР. Техн. кибернетика. 1974. № 2.

С. 143-151.

6. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого ана-

лиза. М.: Физматлит, 2004. 416 с. ISBN 5-9221-0499-3

7. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир 1975.

8. Афанасьев А.П., Дикусар В.В., Милютин А.А., Чуканов С.А. Необходимое

условие в оптимальном управлении. М.: Наука, 1990.

9. Дубовицкий А.Я., Милютин А.А. Теория принципа максимума. Методы теории

экстремальных задач в экономике. М.: Наука, 1981.

10. Цирлин А.М. Условия оптимальности скользящих режимов и принцип макси-

мума для задачи со скалярным аргументом // АиТ. 2009. № 5. С. 106-121.

Статья представлена к публикации членом редколлегии П.С. Щербаковым.

Поступила в редакцию 09.06.2022

После доработки 07.03.2023

Принята к публикации 09.06.2023