Алгоритмы принципа максимума для дискретных задач управления тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

/

/

ИНСТИТУТ МАТЕМАТИКИ И КИБЕРНЕТИКИ ЛИТОВСКОЙ АКАДЕМИИ НАУК

На правах рукописи

РЕГИНА НИЙОЛЕ ШИМЯЛЕНЕ

АЛГОРИТМЫ ПРИНЦИПА МАКСИМУМА ДЛЯ ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ

01.01.09 - математическая кибернетика

Научный руководитель - доктор физико-математических наук И.П. ЯЧЯУСКАС

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Вильнюс - 1993

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.........................................................................................3

ГЛАВА I. ДИСКРЕТНАЯ КВАДРАТИЧНАЯ ЗАДАНА

МНОГОШАГОВОЙ ОПТИМИЗАЦИИ................................17

1. Смешанные задачи........................................................17

2. Выпуклость в алгоритмах решения................................33

ГЛАВА II. ДИСКРЕТНЫЕ ПРОЦЕССЫ ОПТИМАЛЬНОГО

УПРАВЛЕНИЯ С ЗАПАЗДЫВАНИЕМ...............................45

1. Постановка задачи.........................................................45

2. Сведение задачи с запаздыванием к обыкновенной задаче дискретного управления.............47

3. Алгоритм приближенного решения................................49

ГЛАВА III. ОПТИМИЗАЦИЯ ИТЕРАЦИОННОГО ПРОЦЕССА

РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ...................................59

1. Формулировка задачи....................................................59

2. Монотонный алгоритм решения.....................................63

ЛИТЕРАТУРА....................................................................................77

ВВЕДЕНИЕ

Исследуется приложение принципа максимума для решения различных задач многошаговой оптимизации, когда множество решений либо дискретное, либо связное. Для решения этих задач разработаны новые методы типа динамического программирования и принципа максимума, которые рассматривались в работах [1] -[4], [9]-[16], [19]-[22], [53].

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

Приведём определение смешанной задачи. Исследуется дискретная задача оптимального управления

1 И }0 Т М им

л = а , л и ), х = а.

(2)

и е [и и Сг»))=ЫсЯт

Здесь X - П -вектор, ¿^ - Г-вектор, Ср (х)й заданные функции, - фиксированный /^-вектор, ^ /с ^ м + -заданные моменты времени^ к ~ О} • • • ; N~~ ОПРЕДЕЛЕНИЕ. Задачу оптимального управления

ГУ с л"-!.

вир

(4)

А

т т

г п ' ■ ■ -ч

V € V = (и X

К А I к I с ¿ = 1 с

с Со и (5)

назовем смешанной задачей, если удовлетворено условие

тахЭЛ\чЛл )=тахУ({и\ )

иси с инси 1 «>0 ■

где О О П. - выпуклая оболочка множества (у[ СХ ^

I/с/г; и =

к

Таким образом, если V* ( к = О, ... . N-4) .

К

оптимальное решение задачи (4) - (5), имеюущее вид

т т

А

то в оптимальном смешанном решении задачи (1) - (3) точка Ц, (¿) на А -ом шагу выбирается с вероятностью

С

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

Смешанные задачи используются для исследования особого управления. Смешанные решения позволяют уменьшить число вычислительных операций в случае особого управления.

Смешанные решения могут быть использованы в начальных итерациях монотонных алгоритмов вычислений.

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

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

Процессы оптимального управления (4) - (5) используются для исследований смешанных решений процессов (1) - (3). Эта методика применяется для исследований дискретных многошаговых процессов управления запасами. Рассматриваются задачи многошаговой оптимизации, описываемые рекуррентными уравнениями динамического программирования, а также дискретными процессами оптимального управления. В работе [6] исследуется связь между процессами динамического программирования и процессами оптимального управления. Эта связь часто используется. В последнее десятилетие исследуются задачи управления запасами, рассматриваемые в работах [26], [41] - [49]. Многошаговые задачи разных видов управления запасами аппроксимируются смешанными задачами. Классические методы оптимизации, дискретный и непрерывный принцип максимума применяются для исследований этих аппроксимаций. Классические оптимизационные методы эффектны в исследовании смешанных решений этих дискретных аппроксимаций.

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

1. Дискретная квадратичная задача многошаговой оптимизации.

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

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

Диссертация состоит из трех глав.

В первой главе рассматривается квадратичная задача управления с дискретным и со связным множеством управления:

Ы-1

г Т т

! х 0, X + и, Я, и. + , и ч-

и к ^к к к к к к к

к-О

т т 7

+ В X, + X, Р и, ] —^ /т?/>7 (1)

к к к к н у

ик

х = А х + А и , хл = а (2)

+ 4 к к а л > о >

и е и с о)

л

Если множество и дискретное, то её обозначим ип и рассмотрим случаи, когда = \ и (4). ....и (ПО) / С

^г д I ) ; J

С /? •

Здесь и. (¿) - заданные векторы ( £ - , , . /71 )

, ^-заданные

матрицы соответствующих размеров К1 X П ? П X Г? Г) X П^ Г X Г 4 * Г 4 X П ? П X Г.

ЕСЛИ = И, ^ - В, - /?А = /?

для всех ку ; 7 - нулевые матрицы, то

для задачи (1) - (3) в случае связного множества управления 1у1 получена смешанная задача [7].

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

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

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

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

N-1 г

к-О и ^ а

/ л

¿А

к-4 г

\ / 4>*(*>х1> ин-1 ^ * ^

ч

Здесь у*= ...; ?Нп), {им} = {и01..

^ (Ь^Х^ ^ (£; X ^ Ы-~) - заданные функции,

- /7 -вектор состояния, - А"-вектор управления,

Л ^

¿2. -заданный /7 -вектор, t - моменты времени.

К л

Эта задача сведена к обычной задаче дискретного управления:

УКе и с вг} к= 0} N-1.

К решению обычной задачи дискретного управления использован алгоритм дискретного принципа максимума.

Задача дискретного управления с запаздыванием по управлению поступила по заказу при решении частной задачи теории информации. Она обобщалась и в рассмотренном виде она является в некотором случае общей дискретной задачей оптимального управления с непрерывным временем и интегральными ограничениями, которая рассматривалась в работах [9], [25], [42], [50] - [52]. В данной работе эта задача аппроксимируется обычной задачей дискретного управления, к решению которой возможно применить упомянутую методику исследования оптимального управления.

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

П 2

т. (х^) -ГП1П}

¿^ Н и, ГО

к

X ^ = У - и, (-1) [7 у (лк) Д

к+4 к к / а /

'А-И к А / к /г

^ / ^

"л

и и (¿)*0 ¿=4,2,

к /г ^ ^

А = О ..

? ? 7

где

п

2

(х)= Ц /. Сх).

J Ь

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

Обычно для численного решения систем уравнений с числовыми неизвестными используются итерационные методы математического программирования незаботясь о скорости сходимости этих алгоритмов. Если итерационный процесс сходится медленно, то целесообразно использовать предлагаемый оптимизационный алгоритм. Кроме того, уменьшение числа шагов итераций ускоряет время вычислений при сложной функции ^^^ ■ Увеличение числа шагов предлагаемого алгоритма программу удлиняет незначительно, так как в некоторых шагах вычисление происходит по тем же самим формулам, например шаг 5, шаг 8 и

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

Проведём грубый сравнительный анализ сложности предлагаемых алгоритмов. Теорему о выпуклости функции целесообразно использовать в алгоритмах принципа максимума, в которых выбираются значения сопряженных переменных и критерий минимизируется по начальным значениям сопряженных переменных. Это прямой алгоритм принципа максимума, алгоритм приближения по граничным условиям, алгоритмы М.А. Крылова и Ф.Л. Черноусько, алгоритмы дополнительного шага и другие, если значения начальных сопряженных переменных устанавливаются не однозначно.

Необычная задача оптимизации дискретного управления с запаздыванием по управлению сводится к обычной задаче дискретного оптимального управления, к которой прилагаются все известные алгоритмы.

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

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

Основные результаты работы докладывались и обсуждались на ряде конференций Литовского математического общества, на II и III Всесоюзных школах "Понтрягинские чтения. Оптимальное управление. Геометрия и анализ" в Сибири, на 14-том Международном симпозиуме по математическому

программированию в Амстердаме, на Конференции по комбинаторной оптимизации С092 в университете Охфорда, на XIII Всемирной конференции по исследованию операций IFORS 93 в Лисабоне, на Конференции по комбинаторной оптимизации С094 в Амстердаме, на Международной конференции по исследованию операций в Берлине, на Третьем международном конгрессе по индустриальной и прикладной математике ICIAM 95 в Гамбурге, на Ежегодних встречах GAMM: GAMM 96 в Праге, GAMM 97 в Регенсбурге, GAMM 98 в Бремене, на Международном конгрессе математиков ЮМ 1998 в Берлине.

Результаты диссертации опубликованы в работах [26 - 49]. Диссертант приносит искреннюю благодарность академику Э.Й. Вилкасу, доктору физико-математических наук В.Б. Бистрицкасу, доктору физико-математических наук И.П. Ячяускасу за постановку задачи, постоянное внимание к работе и плодотворные обсуждения.

ГЛАВА I. ДИСКРЕТНАЯ КВАДРАТИЧНАЯ ЗАДАЧА

МНОГОШАГОВОЙ ОПТИМИЗАЦИИ

Исследуется квадратичная задача оптимального управления с дискретным и со связным множеством управления. Рассматриваются смешанные задачи, определенные в работе [7], для задачи оптимизации квадратичного управления.

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

1. Смешанные задачи

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

решений рассматриваемых дискретных аппроксимаций исходных задач.

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

2 + и^ик ) (1.1)

к=о иК

X = Ал ч- Ви Л х - а (1.2)

а-М л * ; о ?

ике и с (13)

где и /1 - неотрицательно определенные симметричные

матрицы размера /7 х /7 , /? и Ё) -матрицы

соответствующих размеров Г X г , /7 х Г ( ^ /7 -

вектор состояния, СС - заданный /7 -вектор, Ы. ~ Г ~

К

вектор управления

Смешанную задачу определяет следующая теорема. ТЕОРЕМА 1.1. Пусть матрицы

А и А-Е неособенные, и собственные значения матрицы А не равны единице при

а при Г) ~ А У О . Тогда задача оптимального

управления

N

г

[угЮС1уЮ + ит(1)Я*иШ +

0-х- * -1

+ утША и Ш -/■ ит($А п?/п) (1.4)

и а)

Ау&)+ у(0)= а? (1.5)

и Ш € с Со и (О + t < /V)

(1.6)

является смешанной задачей для задачи (1.1)- (1.3), где и - либо кусочно-постоянные, либо кусочно-непрерывные функции в интервалах

Здесь матрицы } у А ^ ? А у В

определяются формулами

А А,

А (А-Е?В}

х * т -1Т *

£ = / (А-а я (А-Е) А}

я*= Я + Ргор

*

* т *

где матрица

(А (А-£)-£)В.

ДОКАЗАТЕЛЬСТВО. Определим матрицы

А и В .

Для этой задачи они определяются аналогично работе [5]. Для этой цели запишем решение уравнения (1.5). Имеем, что

t

у(к)+ \е ¿гВиСиПм) к

к < t ^ к + , к = ¿7, ... , N-4.

Из теоремы 1 в работе [7] следует, что

Л

А

Здесь ( к ± $ 4 )

решения дифференциального уравнения (1.5) и разностного уравнения (1.2) соответственно при Ы. = ¿¿^

(к < ± < к + иК= ^н (ан 6

Подставляя выражения ¿^ (к ч- 4 ) из формулы (1.7) и ^ ^ + ^ из формулы (1.2) в выражение (1.8), имеем:

еАу(к) + / £ с1? Ви(к)

Ах + Вию

к = 0}

Отсюда получаем, что

А А

е - А,

А (к^-?) * е dT В = В.

>

Так как матрицы и А-В неособенные, и

собственные значения матрицы А не равны единице при

П > ^ , а при Н ~ "1 Л У О ( то имеем:

А = овл А

J

В*= о€пА ■ (А-Е)'в.

* * *

Теперь определим матрицы С( /? /4

/1*

и /1 . Из условий смешанной задачи, определенной в работе [7], имеем, что

к

+ иШ + и а) А2уШ ]оИ

7' а* к +

н

к

и1 Я

к к

Подставляя выражение

У

е

а а-м)

ч-

±

е ЫтЗи(к)

1

к

имеем:

к** ± г ~ 7 г / *

# ¡г!*

7

к

АС*-М) I / I А С*-?') * , л/ { ^

е + е ¿гВиСмУ

А

t

с

А

е

а а-к) i аа-м / г

у(к)+1е с/т Зи (к){ + и

к

А*а-м)

н/е у(м)!+

t

т

ЫгЗиСЮ/ \А,иа)+

а а-к)

а * ,,

+ 1е ¿гВаШ^ии

т т

А= О, N-4.

После элементарных вычислений интегралов получаем, что

А а-т) * , , *.-1 л а-^ -к

е с/гЗиМ = С-А) (Е-е )£>и(м)>

/-1 а* а-к) л *

= А Се -В) В и (к).

Подставляя полученное значение интеграла в вышестоящее соотношение и интегрируя, имеем:

к+л т

(

т

<

е

* . \ А

К

* ^ /(¿-к) # + / !д (е -Е)Зи(кШ\ Ю

к

г

к* 4

к^

* / Л

А а-к)

е

-г

* \ А (¿-к)

+ А (е -Е)Зи(кЫ^>+

к

к

к-^

+ I я"иа)са +

к К«

Ж

А

/(¿-к)

к+4

Т _ т

V \А "-ЮЗиС/сЩ и

к

к+4

и № оИ +

к

7".

+ 1 и(tí di А ■ le

л

+ // Се

/Л*-Л)

А

А*а-м)

■X

E)Bu(M)dí К

к

т л

7 Г * I *

(A-E)y(k)UlA (A (A-EhE)ßuMI №

с

А (А-Е)уШч-А (А (A-E)-E)öu(W +

г

+

и (i) Ru Ct) dt +

k г

T

т

H

if--1

'A(A-E)u(M)i+lÂ(А (А-Е)~Е)ВиСЮ! ÏA

i

i

и

* I

(tídt + \u(^ätA ^А (А

к

к

+ А'1 (А~\А - Е) - Е) В*и(к) > =

Полученное соотношение запишем в виде г ** -г г **

Т ** т ^ Т

где

т *

(3 = (А-Е)А 0.А СА-Е\ (1.9)

Я =(А (А (А-ЕУЕ)В)ЯА СА (А--Е)-Е)В*+Я*+ (А *~Ь (А -Е)-Е)В*) ТА +

Л, -х-

+А2А (А (А-Е)-Е)В) (1.Ю,

А, =(А-Е)А Я А (А (А-Е)-Е)3 +

+ (А-Е)ГА~" А*, (1Л1)

** * Т -х-

А2=(А (А (А-Е)~Е)В )@А (А-£)+

+АРА'\А-Е). (,12)

Так как Ц (к) = _Х , то из этих тождеств �