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

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

Однако следует заметить, что подавляющее большинство разработанных точных и приближенных методов относится к системам с непрерывным временем. Для общих систем с дискретным временем, в особенности нелинейных, их арсенал оказывается значительно беднее. Основная причина такого положения – отсутствие в общем случае дискретного аналога принципа максимума Понтрягина для непрерывных систем, с которым долгое время связывались многие теоретические работы в области оптимального управления, основанные на методе вариаций и необходимых условиях оптимальности. Об этом, в частности, свидетельствуют, известные работы по дискретным системам [1-3].

Дискретные модели привлекали внимание исследователей главным образом возможностью применения методов нелинейного программирования к решению задач оптимального управления, в том числе – непрерывных с помощью частичной или полной дискретизации задачи по управлению и состоянию [1-5].

Хотя изучение неоднородных управляемых систем [6-10] началось еще с 70-х годов прошлого века, речь в основном идет о непрерывных системах. Дискретные неоднородные системы практически не изучены.

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

Один из возможных подходов состоит в обобщении для них достаточных условий оптимальности Кротова [11]. За основу взята абстрактная динамическая система как многошаговая, операторы которой на разных шагах допускают различную интерпретацию [12]. В [6, 13, 14] предложена и развита математическая модель дискретно-непрерывной системы (ДНС) в виде конкретизации указанной абстрактной модели [12], применимая для широкого класса задач управления неоднородными процесса- ми, и для нее получен аналог достаточных условий Кротова для непрерывных и дискретных систем. При таком подходе строится иерархическая модель, в которой нижний уровень представляет собой описания однородных процессов на отдельных этапах, а верхний уровень связывает эти описания в единый процесс и управляет функционированием всей системы в целом. В различных задачах управления, в частности в задачах оптимизации, оба уровня рассматриваются во взаимодействии.

В данной работе рассматривается модель, в которой, и на нижнем уровне, действуют дискретные управляемые системы (НДС) [14]. Такие системы могут рассматриваться как самостоятельные «дискретнодискретные», так и в качестве вспомогательных для ДНС с учетом естественной дискретизации непрерывных подсистем в реальных вычислениях.

Для неоднородных дискретных систем (НДС) строится метод локального улучшения управления. В основу построений положены достаточные условия оптимальности типа Кротова, представленные далее, и принцип локализации [15]. Рассматривается иллюстративный пример.

1. Неоднородные дискретные процессы и основные конструкции

Рассмотрим подробнее важное приложение иерархического принципа как прямой аналог динамической ДНС – двухуровневую модель, в которой нижний уровень составляют дискретные динамические системы однородной структуры. На верхнем уровне фигурирует дискретная модель общего вида

X ( k + 1) = f ( k , x ( k), u ( k )),

k e K = {kT,kT +1,...,kF},  u e U(k,x), где k – номер шага (этапа), x и u – соответственно переменные состояния и управления произвольной природы (возможно различной) для различных k , U(k, x) – заданное при каждом k и x множество.

На некотором подмножестве K'c K, kF £ K', u(k) интерпретируется как пара (uv(k),md (k)) , где md (k) - процесс (xd(k,t),ud (k,t)) , t e T(k,z(k)), md (k) e Dd (k, z(k)), а Dd - множество допустимых процес- сов md , удовлетворяющих системе xd (k, t +1) = f d (k, z, t, xd (k, t), ud (k, t)), t G T = {t7 (z), ti (z)+ 1,...,tF (z)}

x^d g X ^d ( k , z , t ),    u^d g U ^d ( k , z , t , x^d ) , z = ( k , x , u^v ) .

Здесь Xd (k, z, t), Ud (k, z, t, xd) - заданные при каждом t, z и xd множе- ства.

Оператор правой части (1) сводится к следующему:

f ( k , x , u ) = 9 ( z , Y^d ( z ) ) , Y d = ( t i , x d , t F , x F ) e Г ^d ( k , z ),

Г ^d ( z ) = Y d : t i = t ( k , z ), t F = 9(k , z ), x d = ^(k , z ), x F е Г F ( k , z )}.

На множестве D процессов m = (x (k), u (k), xd (k, t), ud (k, t)), удовлетворяющих (1), (2), рассматривается задача оптимального управления о минимизации концевого функционала I = F(x(kF)) при фиксированных kI = 0, kF, x(kI) и дополнительных ограничениях x(k) е X(k).

Для решения этой задачи вводится множество E процессов m , где исключены дискретные цепочки, и обобщенный лагранжиан по аналогии с лагранжианом для ДНС [13, 14]:

L = G ( x ( k_F ) ) - ^ R ( k , x ( k ), u ( k )) + K \ K ‘ \ k_F

+ 2 ( G^d ( z ) - E t ( z )\ t_F R d ( z , t , x^d ( k , t ), u^d ( k , t )) ) ,

K '

G ( x ) = F ( x ) + ф ( k F , x ) - ф ( k i , x ( k i ) ) ,

R ( k , x , u ) = ф ( k + 1, f ( k , x , u ) ) - ф ( k , x ) , G d ( k , z , y^d ) = - Ф ( k + 1, 9 ( k , z , y^d ) ) + ф ( k , x ( k ) ) + + Ф^d ( k , z , t F , x F ) - ф^d ( k , z , t i , x l ) ,

R d ( k , z , t , x^d , u^d ) = ф ¹ ( k , z , t + 1, f^d ( k , z , t , x^d , u^d ) ) - ф ¹ ( k , z , t , x^d ), ц^а ( k , z , t ) = sup { R^d ( k , z , t , x^d , u^d ) : x^d е X ^d ( k , z , t ), u^d е U ^d ( k , z , t , x^d ) }, l^d ( k , z ) = inf { G^d ( k , z , Y^d ) :( Y^d ) е r d ( k , z ), x^d е X ^d ( k , z , t F )}.

^ ⁽ k ) =

sup{R (k, x, u): x е X(k), u е U (k, x)}, t е K \ K' ' - inf{/d (z):x е X (k), uv е Uv (k, x)}, k е K', l = inf{G (x): x е Г n X (kF)}.

Здесь ф ( k , x ) - произвольный функционал, ^^d ( k , z , t , x d ) - произвольное параметрическое семейство функционалов (с параметрами k , z ).

Легко убедиться, что L(m) = I(m) при m е D, т.е. при выполнении отброшенных связей L(m) совпадает с I(m) . Действительно, при m е D , как видно,

R = ф ( k + 1, x ( k + 1) ) - ф ( k , x ) ,

R d = ф ¹ ( k , z , t + 1, x^d ( t + 1)) - ф^а ( k , z , t , x^d ), L = F ( x ( k F )) + ^ ( ф ( k , x ) - ф ( k , x )) +

K \ K '

' ! Е Ф ( k,z.t , x ) - ф ( k,z,t . x )) .

K ' ( T ( k . z )                                         J

Отсюда непосредственно следуют теоремы, аналогичные теоремам для ДНС [13, 14].

Теорема 1. Для любого элемента m е D и любых ф. vd имеет место оценка

I ( m ) - inf I < А = I ( m ) - 1 .

Пусть имеются два процесса m I е D . m II е E и функции ф и v d такие.

что L

( m II ) < L ( m I ) = I ( m I )

,и m ^II

е D .

Тогда I ( m II ) < I ( m I ).

Теорема 2. Пусть имеются последовательность процессов { m s } с D и функционалы ϕ , ϕ ^d , такие что:

• 1)    R ( k . x s ( k ) . U s ( k ) ) ^ д ( k ) . к е K ;

• 2)    R d ( z s . t . x s ( t ) . u d ( t ) ) - / ( z s . t ) ^ 0. k е K ' . t е T ( Z s ) ;

• 3)    G d ( Z s . y d ) - 1 d ( Z s ) ^ 0. k е K ' ;

• 4)    G ( X s ( I f ) ) ^ 1 .

Тогда последовательность { m_s } – минимизирующая для I на D .

r

\

Ia = aI + (1 - a ) E |A u ( k )l2 +Z|A ud ( k. t )l2 .

^ K \ K ' \ k_F               K '

J

где ае[0.1]. Au = u - uI. Aud = ud - udI. При построении метода будем отталкиваться от задачи улучшения элемента. Задан элемент mI е D и требуется найти элемент mII е D. для которого справедливо неравенство: I (m II )< I (m I).

Согласно принципу расширения, будем решать задачу улучшения для функционала L _a . Имеем L _a ( m II ) - L _a ( m I ) < 0. Рассмотрим приращение функционала L _α ( m ) :

A L а «А G - E k \ k ' A R - E ( A G d - E A R d ),

K '

T ( k . z )

где A R = R TT A x + R T A u + ¹ A u ^T R A u , A G = G „ T A x , A G d = G dT A x + G d T A x^d d , x        u                uu               x                 x           d F

2                                                x_F

A R^d = R d ^T A x + R d T A x^d + R d T A u^d + ¹ A u^{d T} R d A Uu^d .    Здесь функции

• ^x         x         u        2        uu

• G , G^d , R , R^d выписаны для функционала I _α .

Предположим, что матрицы R_uu и R_u^d d _u d отрицательно определены (этого всегда можно добиться за счет выбора параметра α [15]). Найдем A u , A u^d , доставляющие максимум выражениям для A R и A R^d . Нетрудно видеть, что A u = - ( R_uu ) ^{- 1} R_u , A u d =- ( Rd, d ) ^{- 1} Rd, . Для выполнения неравенства A L <  0 потребуем далее, чтобы A R , A G , A G , A R^d не зависели от A x , A x F , A x^d . Зададим функции ф, ф¹ в виде: ф ( k , x ) = у(k ) x , ф^а ( k , t , x , x d ) = y d ( z , t ) x d + Ax .

Тогда из сформулированных условий получим:

A u = - ( H „„ )^{- 1} H_u , y ( k_F ) = - aF_x , Уk ) = H_x , k e K \ K ' , И ^k ) = ^H x ⁺ £У ^{( k} , t i ^{)+ A ( k} , t i ) , ^ ( k , t F ) = H x d , A ( k , t F ) = H xf ,

У ( k , t ) = H d d , A ( k , t ) = H xd , A u d =- ( H du ) ^{- 1} H d d , k e K ' .

Здесь

H ( k , x , u,y ( k + 1 )) = у ^T ( k + 1 ) f ( k , x ( k ), u ( k )) - ( 1 - a ) A u |², k e K \ K ' \ k_F , H ( k , x,у ( k + 1 ), x d , x^d_F ) = у ^T ( k + 1 ) y ( k , x d , x F ), k e K ' ,

H^d ( k , t , x , x d , u d ,y^d ( k , t + 1 ) ) = y d ( k , t + 1 ) f d ( k , t , x , x d ( k , t ), u d ( k , t ) ) - ( 1 - a ) A u d ( k , t ) , a - коэффициент, a e [0,1].

3.    Итерационная процедура

На основе полученных соотношений можно сформулировать следующую итерационную процедуру на шаге s .

• 1.    «Слева направо» просчитывается НДС (1), (2) при u = u s ( к ), u d = u d ( к , t ) и заданных начальных условиях, получаются соответствующие траектории ( x_s ( k ), x_s^d ( k , t )) .

• 2.    «Справа налево» разрешается НДС относительно у ( к ) , y d ( к , t ) и λ ( k , t ).

• 3.    Находятся A u , A u d и новые управления u s _{+ 1}( к ) = u s ( к ) + А u , u d ₊ 1 ( к ) = u d ( к ) + А u d .

• 4.    Просчитывается «слева направо» исходная НДС (1), (2) при новых управлениях с заданными начальными условиями.

Процесс итераций заканчивается, когда | I s _{+ 1} - I s | ~ 0 с заданной точностью.

Имеет место следующее утверждение о сходимости.

Теорема 3. Пусть для НДС (1), (2) построена указанная итерационная процедура, и функционал I ограничен снизу. Тогда она генерирует улучшающую последовательность элементов { m s } е D , сходящуюся по функционалу, т.е. существует число I * , такое что I * <  I ( m s ), I ( m s ) ^ I * .

Доказательство. Доказательство следует непосредственно из свойства монотонности (по функционалу) рассмотренного оператора улучшения. Таким образом, получается монотонная числовая последовательность

{ I s } = { I ( m s )} , I s + 1 <  I s , ограниченная снизу, которая по известной теореме анализа сходится к некоторому пределу: I_s ^ I * . Теорема доказана.

Пример. Проиллюстрируем один шаг метода на примере. Пусть задана неоднородная дискретная управляемая система:

x d ( l + 1 ) = x d ( t ) u^d ( t ) - ( u^d ( t ) ) 2 , x d ( t + 1 ) = x d ( t ), X ( 0 ) = x d ( 0 ) = 1, t = 0,1,2; x 1 ( t + 1 ) = x d ( t> d ( t ) - (u d ( t ) ) 2 , t = 3,4;

I = x d ( 5 ) ^ min.

Нетрудно видеть, что K = 0,1,2. Поскольку роль связующей переменной на двух рассматриваемых этапах играет x ₁ ^d , то в терминах этой переменной легко записать процесс верхнего уровня: x ( 0 ) = x d ( 0,0 ) , x ( 1 ) = x d ( 0,3 ) = 9, x d ( 1,4 ) = x ( 1 ) = ^, x ( 2 ) = x d ( 1,5 ) . Тогда I = x ( 2 ) . Основные конструкции принимают вид:

H ( 0, t , v 2 ( 0, t + 1 ) v 2 ( 0, t + 1 ), x 2 , x 2d , u² ) =

= v 1 ( 0, t +1( x d ₂ ( 0, t У ( 0, t ) - ( u² ( 0, t ) ) ² ) +

+ v² ( 0, t + 1 ) x d ( 0, t ) - ( 1 - a ) ( a u² ( 0, t ) ) 2 ;

H ( 1, t , V 1 ² ( 1, t + 1 ), x 2 , u 2 ) =

= v 2 ( 1, t + 1( x 2 ( 1, t ) u 2 ( 1, t ) - ( u 2 ( 1, t ) ) ² ) - ( 1 - a ) ( a u 2 ( 1, t ) ) ²;

H ( k , v ( k + 1 ) , x ) = v ( k + 1 ) x ² ( k , t_F );

v(k) = v(k +1), k = 1, v(2) = -aFx =-a;

v1 (0,t) = v2(0,t +1), v2 (0,3) = v(1) = -a,

V 2 ( 0, t ) = v 2 ( 0, t + 1 ) u² ( 0, t ), v 2 ( 0,3 ) = 0;

v 1 ( 1, t ) = v 1 ( 1, t + 1 ) u² ( 1, t ), v 2 ( 1,5 ) = v ( 2 ) = - a .

Приращения управлений на текущем приближении определяются по формулам:

A u ² ( 0, t ) = - ( 2 ( 2 a - 2 - v 2 ( 0, t + 1 ) )) - 1 v 2 ( 0, t + 1 ) ( x 2 ( 0, t ) - 2 u ² ( 0, t ) ),

A u 2 ( 1, t ) = - ( 2 ( 2 a - 2 - v 2 ( 1, t + 1 ) )) - ' v 2 ( 1, t + 1 ) ( x 2 ( 1, t ) - 2 u 2 ( 1, t )J.

Поскольку уравнения нижнего уровня не зависят от переменной x верхнего уровня, то Л ( k , t ) = 0.

В качестве начального приближения были выбраны значения u² ( 0, t ) = 0.1, u² ( 1, t ) = 1 , при этом 1 ¹ =- 2.001 . Расчеты на шаге проводились для значений a = 0.05,0.1,0.4 . В табл. 1 отражены результаты, полученные после выполнения одного шага алгоритма, которые подтверждают работоспособность предложенного алгоритма.

α	0.05	0.1	0.4
I 2	- 2.1817	- 2.4062	- 7.0191

Таблица 1. Значения функционала I при разных значениях α .

Заключение

Таким образом, в работе приведена иерархическая модель неоднородной дискретной системы (НДС), для которой поставлена задача оптимального управления и сформулированы достаточные условия оптимальности типа Кротова. На основе этих условий, принципах расширения и локализации получен метод локального улучшения. Доказана теорема о сходимости метода по функционалу. Рассмотрен иллюстративный пример.