Автоматика и телемеханика, 2024, № 11

Учредители журнала:
Отделение энергетики, машиностроения, механики и процессов управления РАН,
Институт проблем управления им. В.А. Трапезникова РАН (ИПУ РАН),
Институт проблем передачи информации им. А.А. Харкевича РАН (ИППИ РАН)
Главный редактор:
Галяев А.А.
Заместители главного редактора:
Соболевский А.Н., Рубинович Е.Я., Хлебников М.В.
Ответственный секретарь:
Родионов И.В.
Редакционный совет:
Васильев С.Н., Желтов С.Ю., Каляев И.А., Кулешов А.П., Куржанский А.Б.,
Мартынюк А.А. (Украина), Пешехонов В.Г., Попков Ю.С.,
Федосов Е.А., Черноусько Ф.Л.
Редакционная коллегия:
Алескеров Ф.Т., Бахтадзе Н.Н., Бобцов А.А., Виноградов Д.В., Вишневский В.М.,
Воронцов К.В., Граничин О.Н., Губко М.В., Каравай М.Ф., Кибзун А.И.,
Краснова С.А., Крищенко А.П., Кузнецов Н.В., Кузнецов О.П., Кушнер А.Г.,
Лазарев А.А., Ляхов А.И., Маликов А.И., Матасов А.И., Меерков С.М. (США),
Миллер Б.М., Михальский А.И., Мунасыпов Р.А., Назин А.В.,
Немировский А.С. (США), Новиков Д.А., Олейников А.Я., Пакшин П.В.,
Пальчунов Д.Е., Поляков А.Е. (Франция), Рапопорт Л.Б., Рублев И.В.,
Степанов О.А., Уткин В.И. (США), Фрадков А.Л., Цыбаков А.Б. (Франция),
Чеботарев П.Ю., Щербаков П.С.
Адрес редакции: 117997, Москва, Профсоюзная ул., 65
Тел./факс: 8 (495) 198-17-20, доб. 1443
Электронная почта: redacsia@ipu.ru
Зав. редакцией Е.А. Мартехина
Москва
ФГБУ «Издательство «Наука»
c
⃝Российская академия наук, 2024
c
⃝Редколлегия журнала «Автоматика и телемеханика» (составитель), 2024

Автоматика и телемеханика, №11, 2024
Линейные системы
c
⃝2024 г.
Д.Н. ИБРАГИМОВ, канд. физ.-мат. наук (rikk.dan@gmail.com),
К.А. ЦАРЬКОВ, канд. физ.-мат. наук (k6472@mail.ru)
(Московский авиационный институт
(национальный исследовательский университет);
Институт проблем управления им. В.А. Трапезникова РАН, Москва)
ОБ ОДНОМ ПОДХОДЕ К РЕШЕНИЮ ЗАДАЧИ БЫСТРОДЕЙСТВИЯ
ДЛЯ ЛИНЕЙНЫХ СИСТЕМ С ДИСКРЕТНЫМ ВРЕМЕНЕМ
НА ОСНОВЕ МЕТОДА КРОТОВА1
Разработан метод исследования задачи быстродействия для линейной
дискретной системы, позволяющий в общем случае улучшать известные
верхние оценки времени быстродействия и находить гарантирующие процессы управления. Получены достаточные условия, при которых имеет
место сходимость к оптимальному решению в задаче. Метод реализован
в виде эффективного численного алгоритма.
Ключевые слова: задача быстродействия, линейные дискретные системы,
последовательные глобальные улучшения.
DOI: 10.31857/S0005231024110013, EDN: YMLONE
1. Введение
Задача быстродействия известна достаточно давно как задача оптимального управления, в которой роль функционала качества играет время, затрачиваемое системой на достижение некоторого заданного терминального
состояния [1–3]. При рассмотрении систем с непрерывным временем данная
задача естественным образом вкладывается в общую проблематику классической теории оптимального управления. Так, в случае линейных непрерывных
систем применение принципа максимума Понтрягина [1] гарантирует получение решения задачи в виде релейной функции управления.
Системы с дискретным временем имеют в этом смысле ряд фундаментальных отличий [4–6]. Если б´
ольшую часть задач теории оптимального управления дискретными системами удается решить посредством дискретного принципа максимума [6, 7] и/или метода динамического программирования [8], то
для решения задачи быстродействия эти подходы оказываются неприменимы даже при наличии ограничений на линейную структуру рассматриваемой
1 Теорема 1 доказана Д.Н. Ибрагимовым за счет средств проекта Российского научного
фонда №25-21-00018 https://rscf.ru/project/25-21-00018 в МАИ (НИУ). Теоремы 2 и 3 доказаны К.А. Царьковым за счет средств проекта Российского научного фонда №22-11-00042
https://rscf.ru/project/22-11-00042 в ИПУ РАН.
3

системы. Основными причинами здесь являются нерегулярность экстремума
для почти всех начальных состояний, неединственность оптимальной траектории и дискретный характер функционала качества [9, 10]. Использование
многих современных результатов теории оптимального управления дискретными системами [11, 12] по отношению к указанной задаче также оказывается некорректным, а известные работы, касающиеся непосредственно задачи
быстродействия для систем с дискретным временем, охватывают только ряд
частных случаев [13, 14]. С практической точки зрения актуальным является
получение результатов, которые могут быть использованы в случае линейной
системы произвольной размерности с выпуклым множеством геометрических
ограничений на управление. При рассмотрении таких систем результаты упомянутых выше работ либо труднореализуемы в вычислительном плане, либо
вовсе применимы лишь при существенных дополнительных предположениях.
В настоящей статье разрабатывается эффективный численный алгоритм
поиска оптимального по быстродействию управления для линейных дискретных систем. Одной из наиболее известных и хорошо зарекомендовавших себя
численных схем решения различных линейных задач оптимального управления является метод Кротова [15, 16]. В его основе лежат разработанные
В.Ф. Кротовым, В.И. Гурманом и М.М. Хрусталевым достаточные условия
глобальной оптимальности [17] и принцип расширения экстремальных задач [18]. Ряд работ также посвящен реализации этого метода в случае дискретных и дискретно-непрерывных управляемых систем, см. [19, 20]. Метод
Кротова представляет собой итерационный процесс построения последовательных улучшений некоторого выбранного заранее управления заданной
динамической системой. Важнейшей особенностью метода является его нелокальность. Последнее означает, что в процессе применения итераций новые
управления не обязаны быть близки к найденным на предыдущих шагах ни
в смысле какого-либо расстояния в пространстве допустимых управлений,
ни в смысле значений оптимизируемого функционала качества. В случае линейных систем эта особенность проявляется наиболее явно, поскольку зачастую оптимальное управление удается определить уже за одну первую итерацию применения метода Кротова, исходя из любого начального приближения [19, 21].
В данной работе метод Кротова применяется для поиска оптимального
по быстродействию управления при известных оценках на время быстродействия. Для построения оценок предлагается использовать несколько альтернативных подходов. В общем случае в этих целях могут быть использованы
результаты работ [9, 10, 22], хотя во многих ситуациях их вычислительная
сложность оказывается значительной. Поэтому в разделе 3 предлагается новый подход к построению оценок времени быстродействия для случая, когда
матрица рассматриваемой линейной системы является диагонализируемой.
После того как указанные оценки построены, возможно осуществить переход
к задаче с фиксированным временем функционирования системы. Этот переход подробно описан в разделе 4. Затем к полученной задаче применяется
4

метод Кротова (раздел 5). В разделе 6 сформулирован общий численный алгоритм исследования задачи быстродействия. Раздел 7 содержит ряд примеров, иллюстрирующих эффективность и особенности применения алгоритма
при решении конкретных задач.
В сравнении с предыдущими работами одного из авторов [9, 10, 22] не
предполагается получение аналитических условий оптимальности процесса
управления в задаче быстродействия. Вместо этого предлагается конструкция численной процедуры, позволяющей в ряде случаев приближенно находить оптимальные по быстродействию процессы. В сравнении с [22], где предлагалось построение двусторонних оценок времени быстродействия на основе
геометрических методов, оценки в этой статье строятся аналитически, но для
более узкого класса систем. Полностью новой является идея использования
метода глобальных улучшений Кротова при исследовании задачи быстродействия в дискретном времени. До этого метод Кротова применялся одним из
авторов при исследовании некоторых задач оптимального управления непрерывными системами [23].
В рамках настоящей работы ограничимся рассмотрением стационарных
линейных дискретных систем с невырожденной матрицей и выпуклым компактным множеством геометрических ограничений на управление. Условие
невырожденности используется для обоснования сходимости предлагаемой
итерационной процедуры. Условие стационарности несущественно и принято
для простоты.
2. Постановка задачи и общая идея решения
Рассмотрим линейную стационарную систему с дискретным временем
x(k + 1) = Ax(k) + u(k),
k ∈N ∪{0} = {0, 1, 2, . . .},
(1)
где x(k) ∈Rn – состояние системы, u(k) ∈U – управление, U – выпуклое
компактное множество в Rn такое, что 0 ∈intU, A ∈Rn×n – заданная невырожденная матрица (det A ̸= 0). Начальное условие для системы (1) фиксировано:
x(0) = x0 ∈Rn.
(2)
Требуется вычислить минимальное число шагов Nmin, за которое возможно перевести систему (1) из заданного начального состояния x0 в начало координат и построить оптимальный процесс {x∗(k), u∗(k −1)}Nmin
k=1 , удовлетворяющий условию x∗(Nmin) = 0. Число Nmin будем далее называть временем
быстродействия системы (1) с начальным условием (2) и будем предполагать,
что поставленная задача разрешима, т.е. Nmin < ∞.
Исследование задачи будем проводить в два обособленных этапа. Дадим
сперва их краткое описание.
5

На первом этапе производится оценка времени быстродействия Nmin.
В некоторых ситуациях Nmin возможно вычислить точно, но в общем случае предполагается построение двусторонней оценки
Nmin ⩽Nmin ⩽Nmin,
(3)
где равенство Nmin = Nmin не исключается. Для этой цели могут быть использованы теоретические результаты из [9, 10] и алгоритмические подходы из [22]. В следующем разделе предлагается новый подход к построению
оценки (3) в том случае, когда матрица A в системе (1) имеет n линейно
независимых собственных векторов.
На втором этапе решается задача оптимального управления при фиксированном времени N функционирования системы (1)–(2) относительно функционала ∥x(N)∥2 квадрата евклидовой нормы вектора x(N), где N принимает
значения Nmin, . . . , Nmin. Наименьшее N, при котором минимальное значение
∥x∗(N)∥2 равно нулю, дает время быстродействия Nmin = N, а соответствующее {x∗(k), u∗(k −1)}N
k=1 представляет собой искомый оптимальный процесс.
Метод поиска оптимального процесса сформулирован и обоснован в разделах 4 и 5. Раздел 6 посвящен совместной алгоритмической реализации описанных этапов.
3. Оценка времени быстродействия
Как продемонстрировано в [9, 10, 22], вычисление величины Nmin может
быть сведено к построению класса множеств 0-управляемости {Ξ(N)}∞
N=0.
Здесь Ξ(N) ⊂Rn – множество тех начальных состояний, из которых систему (1) возможно перевести в начало координат за N шагов, т.е.
Ξ(N) :=

{ξ ∈Rn | ∃u(0), . . . , u(N −1) ∈U : x(N) = 0},
N ∈N,
{0},
N = 0,
(4)
где через x(N) обозначено решение системы (1) при x(0) = ξ.
Поскольку задача быстродействия для заданного начального состояния (2)
предполагается разрешимой, то верно включение
x0 ∈
N=0
Ξ(N).
∞

Поэтому с учетом (4) имеет место
Nmin = min{N ∈N ∪{0}: x0 ∈Ξ(N)}.
(5)
Процесс построения {Ξ(N)}∞
N=0 является весьма трудоемкой процедурой, что
обусловлено следующим представлением множеств 0-управляемости.
6

Л е м м а 1 [9, лемма 1]. Пусть последовательность {Ξ(N)}∞
N=0 определяется согласно (4) и det A ̸= 0. Тогда для всех N ∈N верно соотношение
Ξ(N) = −
k=1

A−kU

,
N

где символ суммы означает сложение множеств по Минковскому.
Операция сложения множеств, как правило, труднореализуема с вычислительной точки зрения. Пусть, к примеру, U представляет собой многогранник
в Rn. Тогда каждое множество Ξ(N) также является многогранником [24,
следствие 19.3.2] и описательная сложность многогранников Ξ(N) (т.е. число
их вершин) растет экспоненциально по N [25, теорема 4.1.2].
Однако при некоторых дополнительных предположениях относительно
матрицы A и множества U возможно вычислить двустороннюю априорную
оценку Nmin без необходимости построения последовательности {Ξ(N)}∞
N=0
явным образом. Ниже рассматривается один из таких случаев.
Введем вспомогательные обозначения. Пусть umax > 0 и λ ̸= 0 – некоторые
действительные числа. Рассмотрим отображение F(·; umax, λ): R →[0; +∞),
заданное в виде
|α|
umax
,
|λ| = 1,
(6)
F(α; umax, λ) =
⎧
⎪
⎪
⎪
⎨
umax (|λ| −1)

−
ln

1 −
|α|
ln |λ|
,
|λ| ̸= 1.
⎪
⎪
⎪
⎩
Для произвольного ϕ ∈R через Aϕ ∈R2×2 обозначим матрицу поворота

,
Aϕ =
 cos ϕ
sin ϕ
−sin ϕ cos ϕ
i=1
Vi := V1 × . . . × Vm.
а через BR – замкнутый шар радиуса R с центром в нуле в R2. Также введем
обозначение для m-арного декартова произведения произвольных множеств
V1, . . . , Vm:
m


Л е м м а 2. Пусть в системе (1) выполнено условие Nmin < ∞, найдутся
числа λ1, . . . , λn1 ̸= 0, r1, . . . , rn2 > 0, ϕ1, . . . , ϕn2 ∈R такие, что
⎛
⎞
A =
,
λ1
. . .
0
...
λn1
.
.
.
r1Aϕ1
.
.
.
...
0
. . .
rn2Aϕn2
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
7

и числа u1,max, . . . , un1,max, R1,max, . . . , Rn2,max > 0 такие, что
U =
i=1
[−ui,max; ui,max] ×
j=1
BRj,max,
n1


n2


где n1, n2 ⩾0 и n1 + 2n2 = n.
Тогда включение x0 = (x0,1, . . . , x0,n)T ∈Ξ(N) справедливо в том и только
том случае, когда верно неравенство
x2
0,n1+2j−1 +x2
0,n1+2j; Rj,max, rj

.
N ⩾max

max
i=1,n1
F(x0,i; ui,max, λi); max
j=1,n2
F

Для удобства читателя доказательства утверждений из этого и последующих разделов отнесены в Приложение.
Отметим, что в рамках леммы 2 допустимы значения n2 = 0 или n1 = 0.
В этом случае в матрице A соответствующие блоки отсутствуют, а все ее
собственные значения являются либо действительными, либо существенно
комплексными.
С л е д с т в и е 1. При выполнении предположений леммы 2 в силу (5) имеет место точное равенство
Nmin =

max

max
i=1,n1
F(x0,i; ui,max, λi);
max
j=1,n2
F

x2
0,n1+2j−1 + x2
0,n1+2j; Rj,max, rj

,
где ⌈α⌉означает минимальное целое число не меньшее, чем α:
⌈α⌉:= min{k ∈Z: α ⩽k},
α ∈R.
Результат следствия 1 применим только к узкому классу систем (A, U),
описываемых условиями леммы 2. Но его можно использовать для получения двусторонних оценок времени быстродействия в случае произвольной
диагонализируемой матрицы A и выпуклого множества U. В этих целях предлагается рассмотреть вспомогательные системы вида (1), удовлетворяющие
условиям леммы 2, и воспользоваться следующим утверждением.
Л е м м а 3. Пусть справедливо включение U ⊂U ⊂U, где U, U, U ⊂Rn –
выпуклые и компактные множества, содержащие 0, задача быстродействия для x0 ∈Rn разрешима для систем (A, U), (A, U), (A, U), а величины
Nmin, Nmin, Nmin – оптимальные значения критерия в задаче быстродействия для данных систем соответственно. Тогда
Nmin ⩽Nmin ⩽Nmin.
8

Известно, что любая матрица A ∈Rn×n, обладающая n линейно независимыми собственными векторами, может быть приведена к виду, представленному в лемме 2, при помощи преобразования подобия [26, теорема 3.4.5].
Столбцы матрицы данного преобразования S ∈Rn×n представляют собой либо собственные векторы для действительных собственных значений, либо их
мнимые и действительные части для комплексных собственных значений.
Аналогичное линейное преобразование можно применить ко всей системе
(A, U) в целом, перейдя к эквивалентной системе (S−1AS, S−1U) так, как
это продемонстрировано в [27]. А именно, справедлив следующий результат.
Л е м м а 4
[27, лемма 2]. Пусть S ∈Rn×n, det S ̸= 0, (A, U) – система
вида (1), через {˜
Ξ(N)}∞
N=0 обозначен класс множеств 0-управляемости системы (S−1AS, S−1U). Тогда
Ξ(N) = S˜
Ξ(N),
N ∈N ∪{0}.
В рамках рассматриваемой задачи множество S−1U может быть оценено
сверху и снизу множествами U, U ⊂Rn, удовлетворяющими условиям леммы 2. В сочетании с леммой 3 это приводит к искомым оценкам величины Nmin в исходной задаче быстродействия. Более точно, имеет место следующее.
Т е о р е м а 1. Пусть в системе (1) для заданного начального состояния
x0 ∈Rn верно, что Nmin < ∞, матрица A ∈Rn×n имеет n линейно независимых собственных векторов, det A ̸= 0, S ∈Rn×n – матрица перехода в
вещественный жорданов базис матрицы A:
⎛
⎞
.
S−1AS = Λ =
λ1
. . .
0
...
λn1
.
.
.
r1Aϕ1
.
.
.
...
0
. . .
rn2Aϕn2
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
Тогда справедлива следующая оценка Nmin:

max

max
i=1,n1
F(y0,i; u′′
i,max, λi);
max
j=1,n2
F

y2
0,n1+2j−1 + y2
0,n1+2j; R′′
j,max, rj

⩽Nmin ⩽
⩽

max

max
i=1,n1
F(y0,i; u′
i,max, λi);
max
j=1,n2
F

y2
0,n1+2j−1 + y2
0,n1+2j; R′
j,max, rj

,
9