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

УДК 517.977

doi: 10.18101/2304-5728-2016-1-27-37

© И. В. Расина, И. С. Гусева, О. В. Фесько, О. В. Усенко

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

При изучении неоднородных управляемых систем различными школами и направлениями основной упор сделан на непрерывные системы с изменяющейся во времени структурой. Для них получены необходимые и достаточные условия, а также итерационные процедуры. Один из подходов состоит в обобщении на такие системы достаточных условий оптимальности Кротова. На этой основе построена иерархическая модель неоднородной управляемой структуры, в которой нижний уровень представляет собой описания однородных процессов на отдельных этапах, а верхний уровень связывает эти описания в единый процесс и управляет функционированием всей системы в целом. В различных задачах управления, в частности в задачах оптимизации, оба уровня рассматриваются во взаимодействии.

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

Ключевые слова: оптимальное управление, дискретные системы, приближенные методы улучшения управления.

© I. V. Rasina, I. S. Guseva, O. V. Fesko, O. V. Usenko

Method of control local improvement for non-homogeneous discrete systems

In studying of non-homogeneous control systems by different schools the main attention is paid to continuous systems with time-varying structure. The necessary and sufficient conditions, as well as iterative procedures have been obtained for them. One of the approaches is to generalize the sufficient conditions for optimality of Krotov type on such systems. On this basis a non-homogeneous hierarchical model of controlled structure have been developed in which the lower level is a description of similar processes at different stages,

:Работа выполнена при финансовой поддержке РФФИ, проекты № 15-01-01915-а, № 15-01-01923-а, № 15-07-09091-а, № 15-01-03680-а; МОН РФ, проект № 3808

and the upper level connects these descriptions into a single process, and controls the functioning of the system in whole. In various control problems, in particular in optimization problems, both levels are considered in interaction.

We have considered the class of non-homogeneous discrete systems for which both levels are discrete. These systems are prevalent in practice and can be obtained from the process of continuous systems digitalization for solution of optimization problems using iterative methods. We have formulated the sufficient conditions of optimality of Krotov type for this class of systems. These conditions and the principle of localization are used to construct improvement method. The article contains illustrative examples.

Keywords: optimal control, discrete systems, approximate methods of control improvement.

Введение

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

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

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

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

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

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

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

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

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

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

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

х(к +1) = f (к, х(к), и(к)),

к е К = {к,,к1 +1,...,кр}, и е и(к,х),

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

На некотором подмножестве К 'с К, кр £ К', и(к) интерпретируется как пара {иу (к), т4 (к)) , где т4 (к) — процесс {х4 {к, t),и4 {к, t)) , т

t е Т{к, z{k)), т4 {к)е Dd {к, 2{к)), а Dd — множество допустимых процес-ющих системе

xd {к, t +1) = fd {к, ^ t, х4 {к, t), иd {к, t))

сов тd , удовлетворяющих системе

t е Т = {^ ^),^ ^)+1,...,tр ^)};

р )}

4 '

xd е Х4 (к, z, t), и4 е Ud {к, z, t, хd ), z = {к, х, иу ).

Здесь X4 (к, z, t), и4 {к, z, t, х4 ) — заданные при каждом t, z и х4 множества.

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

f {к, х, и ) = в{ z,уd ), у4 , х4, tр, хр )е Г4 (к, z),

rd (z) = [yd : tJ =r(k, z), tF = 5(k, z), xd = £(k, z), xdF e Г^ (k,z)}. На множестве D процессов

га = ( x(k), u(k), xd (k, t), ud (k, t) ),

удовлетворяющих (1), (2), рассматривается задача оптимального управления о минимизации концевого функционала I = F(x(kF)) при фиксированных kj = 0, kF, x(kJ) и дополнительных ограничениях x(k) e X(k).

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

L = G (x (kF ))- £ R(k, x(k), u (k)) +

K\K'\kF

+X (Gd (z) - ZT(z)\tF Rd (z, t, xd (k, t), ud (k, t))),

K'

G (x) = F (x) + p (kF, x) - (p(kj, x (kj )), R (k, x, u) = p(k +1, f (k, x, u)) - p(k, x), Gd (k, z,yd ) = -p(k + 1,в (k, z, yd )) + p (k, x (k)) + +pd (k, z, tF, xdF )-pd (k, z, tj, xf ), Rd (k, z, t, xd, ud ) = pd (k, z, t +1, fd (k, z, t, xd, ud)) - pd (k, z, t, xd), jud (k, z, t) = sup {Rd (k, z, t,xd,ud ): xd e Xd (k, z, t),ud e Ud (k, z, t, xd )}, ld (k, z) = inf {Gd (k, z, yd ) :(yd) e rd (k, z), xd e Xd (k, z, tF)}.

[sup{R (k, x,u): x e X(k), u e U (k, x)}, t e K \ K' [ -inf{ld (z) :x e X(k), uv e Uv (k, x)}, k e K',

l = inf{G (x): x e Г n X (kF )}. Здесь p (k, x) — произвольный функционал, pd (k, z, t, xd ) - произвольное

параметрическое семейство функционалов (с параметрами k , z).

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

R = p(k + 1, x(k +1)) - p (k, x), Rd = pd (k, z, t +1, xd (t +1)) - pd (k, z, t, xd), L = F (x(kF )) + X (p(k, x) - p(k, x)) +

K\K'

u( k ) = •

+ Х| Х*к,г,^)-*

к' ^т

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

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

I(т) - МI <А = I(т) -1.

Б

Пусть имеются два процесса т1 е Б, т11 е Е и функции * и * такие, что L (т11 )< L ( т1 ) = I (т1) ,и т11 е Б . Тогда I(т11) < I(т1).

Теорема 2. Пусть имеются последовательность процессов {т,} с Б и функционалы *, *, такие что:

1) R(к,х, (к),^ (кц(к), к е К;

2) Rd (г,, ^ хЙ (t), иЙ (t))-/ (г, ,t)^ 0, к е К', t е Т (г,);

3) Gd ( 2,)-Iй (2, 0, к е К';

4) а (х, (^ I.

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

2. Метод улучшения

Предположим, что ограничения на переменные состояния и управления отсутствуют: Х(к) =  т(к) , Xй (г, 0 =  п(к) , и(к) =  1 (к), (г, t) =  г(к), tI (к), tF (к) - фиксированы, хЙ = £ (к, х), к1 , х1 и кр -

заданы, е  п(к), г = (к, х).

Воспользуемся для построений принципами расширения и локализации [11, 15]. Сформулируем вспомогательный функционал, который зададим в виде:

( \

ч K\K'\kF К'

где а е [0,1], Аи = и - и1, АиЙ = - ил. При построении метода будем отталкиваться от задачи улучшения элемента. Задан элемент т1 е Б и требуется найти элемент т11 е Б, для которого справедливо неравенство: I (т11 )< I (т1).

Согласно принципу расширения, будем решать задачу улучшения для функционала La. Имеем Ьа (т11)-Ьа (т1 )<0. Рассмотрим приращение функционала La (т):

«AG-2к\К'АЯ(АО4 - 2 ),

К' Т

где AR = ЯхтАх + Я^Аи + - Аи тRml Аи, АО = вТАх, Ав4 = Ах + ваТ АхР,

х и г\ ии 7 х 7 X Р 7

2 хр

АЯ4 = ЯхаТАх + ЯаТАхй + Я^ТАи4 + -АиатлАий. Здесь функции

х ха иа 2 """"

в, в4, Я, Я4 выписаны для функционала 1а .

Предположим, что матрицы Яии и Я' ^ ^ отрицательно определены (этого всегда можно добиться за счет выбора параметра а [15]). Найдем Аи, Аий , доставляющие максимум выражениям для АЯ и АЯ4 . Нетрудно видеть, что Аи =-(Яии )-1 Яи, Аил = -(Я^ыиы )-1 Я^ . Для выполнения неравенства AL < 0 потребуем далее, чтобы АЯ, АО, АО, АЯ4 не зависели от Ах, Ахр, Ах4. Зададим функции р, р4 в виде: (р(к, х) = у (к)х, р4 (к, t, х, х4 ) = у4 (г, t)х4 + Хх.

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

Аи = -(Иии )-1 Ии, у(кр ) = -аРх, у(к) = Их, к е К \ К', у(к ) = Их + (к, t1)+Х(к, t1), (к, tр) = И^, Х(к, tр) = ИХг,

у 4 (к,t) = И^, Х(к, t) = Илх ,

Аи4 = -(и^ )-1 Ийл, к е К'.

\ иаиа ' иа

Здесь

И (к, х, и,у (к +1)) = у т (к + l)f (к, х(к), и(к)) - (1 - а ) Аи|2, к е К \ К' \ кр, И (к, х, у (к +1), хр, хр) = ут (к + 1)б(к, хр, хр) к е К', И 4 (к, ^ х, хр, и4, у 4 (к, t +1)) = у л (к, t +1)/ (к, t, х, хр (к, t), ий (к, t ))-

-(1 -а)|Аи4 (к, t)2,

а - коэффициент, а е [0,1].

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

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

1. «Слева направо» просчитывается НДС (1), (2) при и = и, (к),

и1 = иЙ (к, t) и заданных начальных условиях, получаются соответствующие траектории (х, (к), х1, (к, t)).

2. «Справа налево» разрешается НДС относительно у(к), у1 (к, t) и Л(к, 0.

3. Находятся Au, Aud и новые управления us+1(k) = us (k) + Au,

uf+1(k) = ud (k) + Aud.

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

Процесс итераций заканчивается, когда | Is+1 - Is 0 с заданной точностью.

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

функционалу, т.е. существует число I*, такое что I* <I(ms), I(ms) ^I*.

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

{Is}={/(ms)}, Is+i <Is, ограниченная снизу, которая по известной теореме анализа сходится к некоторому пределу: Is ^ I». Теорема доказана.

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

xd (t +1) = xd2 (t)u d (t) - (ud (t))2, x2d (t +1) = xd1 (t), xd (ö) = xd2 (ü) = 1, t = 0,1,2;

xd (t +1) = x\ (tU (t) - (ud (t))2, t = 3,4;

I = xd (5) ^ min.

Нетрудно видеть, что K = 0,1,2. Поскольку роль связующей переменной на двух рассматриваемых этапах играет xjd, то в терминах этой переменной легко записать процесс верхнего уровня: x(ü) = xjd (0,ü),

x(1) = xd (0,3) = в, xd (1,4) = x(1) = x(2) = xd(1,5) . Тогда I = x(2) . Основные конструкции принимают вид:

И4(0,t,у!1 (0,t +1),у2,(0,t +1),хр ,х24,ий)=

= ур (0,t + (0, t)и 4 (0, t) - (и 4 (0, t))2 ) +

+ у24 (0, t + 1)х\(0, t) - (1 - а)(ам4 (0, t))2;

И 4 (1, t,у1d (1, t +1), хр, ир ) =

= ур (1, t + (1, tи (1, t) - (ир (1, t))2 ) - (1 - а)(АМ14 (1, t))2;

И (к, у (к +1), х) = у (к + 1)х\ (к, tF); у (к ) = у(к +1), к = 1, у(2) = -аРх =-а; у1 (0, t) = ур (0, t +1), у? (0,3) = у (1) = -а, у24 (0, t) = ур (0, t + 1)и 4 (0, t), у24 (0,3) = 0;

у^ (1, t) = ур (1, t + (1, t), ур (1,5) = у(2) = -а. Приращения управлений на текущем приближении определяются по формулам:

Аи 4

Аир (1, t) = -(2(2а - 2 - у14 (1, t +1)))-1 ур (1, t + 1)(хр (1, t) - 2ир (1, t)) Поскольку уравнения нижнего уровня не зависят от переменной х верхнего уровня, то Х(к, t ) = 0.

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

а 0.05 0.1 0.4

12 - 2.1817 - 2.4062 - 7.0191

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

Заключение

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

Литература

1. Пропой А. И. О принципе максимума для дискретных систем управления // Автомат. и телемех. — 1965. — Т. 26. — № 7. — С. 1177-

1187.

2. Пропой А. И. Элементы теории оптимальных дискретных процессов. — М.: Наука, 1973. — 256 с.

3. Болтянский В. Г. Оптимальное управление дискретными системами.— М.: Наука, 1973. — 448 с.

4. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982. — 432 с.

5. Горбунов В. К. О сведении задач оптимального управления к конечномерным // Журнал выч. мат. и мат. физ. — 1978. — Т. 18. — № 5. — С.1083-1095.

6. Гурман В. И. К теории оптимальных дискретных процессов // Автомат. и телемех.— 1973. — № 6. — С. 53-58.

7. Васильев С. Н. Теория и применение логико-управляемых систем // Труды. 2-я Международная конференция «Идентификация систем и задачи управления» (SICPRO'03). — 2003. — С. 23-52.

8. Бортаковский А. С. Достаточные условия оптимальности управления детерминированными логико-динамическими системами // Информатика.— Вып. 2-3.— Сер. Автоматизация проектирования. — М.: ВНИИМИ — 1992. — С. 72-79.

9. Миллер Б. М., Рубинович Е. Я. Оптимизация динамических систем с импульсными управлениями. — М.: Наука, 2005.

10. Lygeros J. Lecture Notes on Hybrid Systems. — Cambridge: University of Cambridge, 2003.

11. Кротов В.Ф., Гурман В.И. Методы и задачи оптимального управления. — М.: Наука, 1973. — 448 с.

12. Кротов В. Ф. Достаточные условия оптимальности для дискретных управляемых систем // ДАН СССР.— 1967. — Т. 172. — № 1. — С. 18-21.

13. Гурман В. И., Расина И. В. Дискретно-непрерывные представления импульсных решений управляемых систем // Автомат. и телемех. — 2012. — № 8. — С. 16-29.

14. Расина И. В. Иерархические модели управления системами неоднородной структуры. — М.: ФИЗМАТЛИТ, 2014.

15. Гурман В. И., Расина И. В. О практических приложениях достаточных условий сильного относительного минимума // Автомат. и телемех.— 1979. — № 10. — С. 12-18.

References

1. Propoi A. I. O printsipe maksimuma dlya diskretnykh sistem upravleniya About Maximum Principle for Discrete Control Systems]. Avtomatika i tele-mekhanika - Automation and Telecontrol. 1965. V. 26. No. 7. Pp. 1177-1187.

2. Propoi A. I. Elementy teorii optimal'nykh diskretnykh protsessov [Elements of the Theory of Optimal Discrete Processes]. Moscow: Nauka Publ., 1973.256 p.

3. Boltyanskii V. G. Optimal'noe upravlenie diskretnymi sistemami [Optimal Control of Discrete Systems]. Moscow: Nauka Publ., 1973. 448 p.

4. Evtushenko Yu. G. Metody resheniya ekstremal'nykh zadach i ikh pri-menenie v sistemakh optimizatsii [Methods for Solving Extreme Problems and Their Use in Optimization Systems]. Moscow: Nauka Publ., 1982. 432 p.

5. Gorbunov V. K. O svedenii zadach optimal'nogo upravleniya k ko-nechnomernym [Reduction of Optimal Control Problems for Finite-Dimensional Ones]. Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki - Journal of Mathematics and Mathematical Physics. 1978. V. 18. No. 5. Pp. 1083-1095.

6. Gurman V. I. K teorii optimal'nykh diskretnykh protsessov [To the Theory of Optimal Discrete Processes]. Avtomatika i telemekhanika - Automation and Telecontrol. 1973. No. 6. Pp. 53-58.

7. Vasil'ev S. N. Teoriya i primenenie logiko-upravlyaemykh sistem [Theory and Application of Logic-Control Systems]. Identifikatsiya sistem i zadachi upravleniya - System Identification and Control Problems (SICPRO'03). Proc. 2nd Int. Conf. (SICPRO'03). 2003. Pp. 23-52.

8. Bortakovskii A. S. Dostatochnye usloviya optimal'nosti upravleniya de-terminirovannymi logiko-dinamicheskimi sistemami [The Sufficient Conditions for Optimal Control of Deterministic Logic-Dynamic Systems]. Informa-tika. V. 2-3. Ser. Avtomatizatsiya proektirovaniya - Computer Science. V. 2-3. Ser. Design Automation. 1992. Pp. 72-79.

9. Miller B. M., Rubinovich E. Ya. Optimizatsiya dinamicheskikh sistem s impul'snymi upravleniyami [Optimization of Dynamical Systems with Impulse Controls]. Moscow: Nauka Publ., 2005.

10. Lygeros J. Lecture Notes on Hybrid Systems. Cambridge: University of Cambridge, 2003.

11. Krotov V. F., Gurman V. I. Metody i zadachi optimal'nogo upravleniya [Methods and Problems of Optimal Control]. Moscow: Nauka Publ., 1973. 448 p.

12. Krotov V. F. Dostatochnye usloviya optimal'nosti dlya diskretnykh upravlyaemykh sistem [The Sufficient Conditions of Optimality for Discrete Control Systems]. Doklady Akademii nauk SSSR - Reports of the USSR Academy of Sciences. 1967. V. 172. No. 1. Pp. 18-21.

13. Gurman V. I., Rasina I. V. Diskretno-nepreryvnye predstavleniya im-pul'snykh reshenii upravlyaemykh sistem [Discrete-Continuous Presentation of Impulse Solutions]. Avtomatika i telemekhanika - Automation and Telecontrol. 2012. No. 8. Pp. 16-29.

14. Rasina I. V. Ierarkhicheskie modeli upravleniya sistemami neodnorod-noi struktury [Hierarchical Control Models of Systems Having Inhomogeneous Structure]. Moscow: Fizmatlit Publ., 2014.

15. Gurman V. I., Rasina I. V. O prakticheskikh prilozheniyakh dostatoch-nykh uslovii sil'nogo otnositel'nogo minimuma [About Practical Applications of the Sufficient Conditions for Strong Relative Minimum]. Avtomatika i telemekhanika - Automation and Telecontrol. 1979. No. 10. Pp. 12-18.

Расина Ирина Викторовна, доктор физико-математических наук, главный научный сотрудник Института программных систем им. А.К. Айла-мазяна РАН, e-mail: irinarasina@gmail.com.

Гусева Ирина Сергеевна, кандидат физико-математических наук, преподаватель Института математики и информатики БГУ, e-mail: ig_19@mail.ru

Фесько Олесь Владимирович, кандидат технических наук, н.с. Института программных систем им. А.К. Айламазяна РАН, e-mail: oles. fesko@hotmail. com.

Усенко Олег Валерьевич, старший преподаватель кафедры информатики и программной инженерии Сибирской академии права, экономики и управления, e-mail: o.v.usenko@gmail.com.

Irina V. Rasina, DSc in Physics and Mathematics, Senior Researcher, Institute of Program Systems, Russian Academy of Science.

Irina S. Guseva, PhD in Physics and Mathematics, Lecturer, Institute of Mathematics and Informatics, Buryat State University.

Oles V. Fesko, PhD, Research Scientist, Institute of Program Systems, Russian Academy of Science.

Oleg V. Usenko, Senior Teacher, Department of Informatics and Soft Engineering, Siberian Academy of Law, Economy and Management.