автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Задачи управления параметрами и их приложение к развитию методов улучшения

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

Черемных Светлана Викторовна

ЗАДАЧИ УПРАВЛЕНИЯ ПАРАМЕТРАМИ И ИХ ПРИЛОЖЕНИЕ К РАЗВИТИЮ МЕТОДОВ УЛУЧШЕНИЯ

05.13.01 - Системный анализ, управление и обработка информации (в технике, экологии и экономике)

Автореферат

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

Иркутск - 2006

Работа выполнена в Институте динамики систем и теории управления Сибирского отделения Российской академии наук (ИДСТУ СО РАН)

Научный руководитель: доктор физико-математических наук,

с.н.с. Батурин Владимир Александрович

Официальные оппоненты: доктор физико-математических наук,

доцент Аргучинцев Александр Валерьевич; кандидат физико-математических наук, с.н.с. Горнов Александр Юрьевич

Ведущая организация: Институт математики им. С.Л. Соболева

СО РАН

Защита состоится 9 июня 2006 г. в 16.00 час. на заседании диссертационного совета Д 003.021.01 в ИДСТУ СО РАН по адресу: 664033, Иркутск, ул. Лермонтова, 134, зал заседаний Ученого совета, ком. 407.

С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.

Автореферат разослан 5~мая 2006 года.

Ученый секретарь диссертационного совета

Опарин Г.А.

Общая характеристика работы

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

Основополагающими результатами теории оптимального управления являются: принцип максимума Л.С. Понтрягина, метод динамического программирования Р. Беллмана, достаточные условия оптимальности В.Ф. Кро-това. На основе этих классических результатов созданы различные методы последовательных улучшений первого и второго порядка. Наиболее изученными оказались такие классы задач оптимального управления, как линейные, билинейные, квадратичные задачи. Свойства перечисленных классов задач позволяют упростить многие операции, необходимые для поиска решения, что приводит к созданию эффективных алгоритмов улучшения. Сложнее обстоит дело, когда надо решать задачу оптимального управления нелинейной системой, характер нелинейности которой не известен заранее. Алгоритмы последовательных улучшений, разработанные в предположении, что система и функционал имеют общий вид, как правило, содержат параметры, роль которых - регуляторы шага, обеспечивающие эффективное решение задачи улучшения. В результате эффективность такого алгоритма в той или иной степени (иногда в очень большой) зависит от выбора значений параметров. В то же время вопрос выбора наилучших значений параметров либо сводится к решению одномерной задачи минимизации (если она не трудоемка, то решение вопроса закрыто), либо часто не рассматривается, считается достаточным указать только область допустимых значений. Поэтому при практическом решении задачи оптимального управления достаточно хорошие значения параметров алгоритма обычно находятся методом «проб и ошибок», отнимая у пользователя много времени.

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

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

Методы исследования. При выполнении работы использовались аппарат дифференциального исчисления, элементы теории матриц и векторов, методы оптимизации.

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

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

■ выведены формулы частных производных функционала по параметрам алгоритма улучшения;

" исследованы свойства наименее трудоемкого из предложенных алгоритмов, доказаны теоремы о его релаксационности и сходимости;

" создано программно-алгоритмическое обеспечение, реализующее предложенные в работе методы улучшения;

• проведена проверка работоспособности и эффективности новых алгоритмов на серии тестовых примеров;

■ полученные новые методы улучшения применены для сценарного анализа в задаче управления эколого-экономической системой.

Практическая ценность. Разработанные алгоритмы могут использоваться при решении различных прикладных задач (технических, экономических, природно-экономических и др.). Работоспособность и эффективность этих алгоритмов подтверждена рядом тестовых примеров.

Апробация работы. Основные результаты работы докладывались и обсуждались:

на первой конференции молодых ученых Иркутского государственного университета (Иркутск, 1983),

на второй конференции молодых ученых Иркутского государственного университета (Иркутск, 1984),

на Всероссийской конференции «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, 2003), на Ляпуновских чтениях (Иркутск, 2003),

на региональной конференции молодых ученых «Филология и современное лингвистическое образование» (Иркутск, 2004),

на семинаре «Приближенные методы и алгоритмы оптимального управления», проводимом в рамках симпозиума ШАС по обобщенным решениям в задачах управления (С8СР-2004) (Переславль-Залесский, 2004),

на Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (Алматы, 2004),

на VII школе-семинаре молодых ученых «Математическое моделирование и информационные технологии» (Иркутск, 2005),

на IV Всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005).

Результаты работы обсуждались на семинарах лаборатории «Системного анализа и методов оптимального управления» и Объединенном семинаре ИДСТУ СО РАН.

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

Краткое содержание диссертационной работы

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

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

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

К,',]:

^ = /(;,*, н), *('о) = *о> (1)

где состояние х(1) е Я" - непрерывная и кусочно дифференцируемая вектор-функция, а управление и(1) е и с Л™ — кусочно непрерывная вектор-функция. Множество пар (х(1), и(/))> удовлетворяющих перечисленным условиям, называется множеством допустимых О. Предполагается, что На множестве £> задан функционал

г,

1(х,и) = Г(х (/,)) + ]/\(,х,и)сИ. (2)

'о

Требуется минимизировать функционал I на множестве £>, т.е. найти такую последовательность {(лг1(/),м1(0)}с:^)> чтобы выполнялось

/(.*:,,«,)—»• = при -»со, в частности, найти минималь

о

(х.(*), и,(<))е.О, на которой 1(х,,и,) = /., если такой элемент существует на множестве И.

Поиск последовательности {(х,(1),иг(1))} можно осуществлять с помощью итерационной процедуры, в которой на каждом шаге решается задача улучшения: имеется элемент (хг,иг)еО, требуется найти такой элемент (хи,и") е/Э, чтобы выполнялось неравенство 1{х",и") <1(х',и').

Развитие методов, основанных на принципе расширения, началось с теоремы В.Ф. Кротова, указывающей достаточные условия оптимальности. Принцип расширения состоит в замене исходной задачи минимизации функционала / на множестве Б другой, более простой задачей (минимизации функционала Ь на множестве Е), которая и дает решение исходной задачи. В работе В.И. Гурмана и его учеников «Новые методы улучшения управляе-

мых процессов» приведены утверждения, являющиеся теоретическим обоснованием такой замены: лемма 1 (В.Ф. Кротов, М.М. Хрусталев), теорема (В.Ф. Кротов)1.

Раздел 1.2 посвящен рассмотрению алгоритмов сильного и слабого улучшения второго порядка для поставленной задачи оптимального управления, созданных В.А. Батуриным. Эти алгоритмы основаны на методе локализации2, т.е. элемент т" — (х", и") выбирается достаточно близким к элементу от' = (л', и'). Если требование близости накладывается только на компоненту состояния х(1) элементов т' и т", то получается алгоритм сильного улучшения; если требование близости накладывается на обе компоненты л(/) и и(/) элементов т' и т", то получается алгоритм слабого улучшения. Для вывода алгоритма слабого улучшения рассматривается функционал

1а,р,г = + (1 ~ аУр,г, где •//>,г = 2

4

^и'рдмМ + [Дх(/, )]>Дх(/,)

Ди = и - и1 (<), Ах = х — х:7 (<)» а е [0,1] — скалярный параметр, /?, у - диагональные положительно определенные матрицы размерностей тхт и ях п, соответственно.

Алгоритм слабого улучшения второго порядка

1. Задаем управление ы7(/), из системы (1) находим х'(1).

2. Задаем значения параметров: а = а0 , (5 = /?0 , / = у0-

3. Вычисляем ¡//(г) и а(1) из нижеследующей системы при а0 , /?0 , /0:

^ = -Нах + (Нахи + аН^ )(Я« - (1 - а)Р)~1Н",

= -На„ - <тНащ - Н%а + (#"ы + оЯ« )(Я « - (1 - а)/?)"1 (Наих + Н%а),

= С,)). (3)

= ))-(!-«)/.

' Новые методы улучшения управляемых процессов / В.И. Гурман [и др.]. - Новосибирск : Наука, 1987.-С. 17-19.

2 Там же. - С. 8-9.

Здесь 1{а(1,х,1//,и) = ^/'/(1,х,и)-а/°(1,х,и); 1/(1) - п-вектор; ст(1) - пхп-симметрическая матрица; все производные функции На вычисляются в точке (гУ(<),|/Ч0У(0)-

4. Задаем управление и=и'+Аи, где

Дм(*, Ах) = -(Я,: - (1 - а)Р)'\Наи + (Н^а + Н")Ах], А* = х - х'.

5. Из системы = /(!,х,и), х(/0) = х0 вычисляем х" (г), а затем находим и1!(1) = и'(() + Аи(1,х"-х').

6. Если 1(х",и") > 1(х',и'), то изменяем значения параметров а , /3, у и повторяем процесс с пункта 3.

Для вывода алгоритма сильного улучшения рассматривается функционал

Л ^

1 |Дх'рДхсИ + [Дх(г, )]>Ах(7,) Л'« >

=aI + { 1 - cc)Jfir, где Jfif = -

Ax = x — x1 (/), a 6 [0,1] - скалярный параметр, p, у — диагональные положительно определенные матрицы размерности п х п. Алгоритм сильного улучшения второго порядка

1. Задаем управление и1 (i), из системы (1) находим х1 (t).

2. Задаем значения параметров: а=а0 , р - р0 , у = у0.

3. Вычисляем y/(t) и a it) из нижеследующей системы при сс0 , /?0 , у0:

^ = -0С1+(\-а)р-ак;х --аЯ^а,

V/(tl) = -aFx(x'(tl)), (4)

В системе (4): W = SupHa(t,x,p,u); y/(t) - и-вектор; cr(t) - пхп-

иЛ!

симметрическая матрица; все производные функции На вычисляются в точке (/,х'(/),у(0)> производная На -вточке (t,x' (t),y/(t),u' (t)).

4. Из системы ^ = (/,*,/>)), л(/0) = хй,

где й{г,х,р) = сит>тахНа(1,х,р,и), р = 4/(1) + аЦ)Ах, Ах = х-х'(г),

и

вычисляем х11 (/).

5. Находим и"(I) = й(1,х"(0, + сг(1)(х"(Г) - х'(?))).

6. Если 1{х" ,и") > 1(х' ,и'), то изменяем значения параметров а, р, у к повторяем процесс с пункта 3.

Наиболее трудоемким процессом на каждом шаге рассмотренных алгоритмов является интегрирование векторно-матричных систем (3) и (4). При каждом изменении значений параметров а, /3 а у этот процесс приходится повторять, что требует больших затрат вычислительных ресурсов. Кроме того, от значений этих параметров зависит глубина улучшения функционала на каждой итерации и, следовательно, количество итераций, необходимых для решения задачи.

Раздел 1.3 посвящен исследованию задачи с параметром, которая рассматривается как частный случай задачи оптимального управления с параметром, описанной в монографии В.А. Батурина и Д.Е. Урбановича3. Постановка задачи

Пусть математическая модель объекта описывается системой ^ = /(*,*,а), *(/„) = х0, (5)

где * е[*0»*1]» функция дг(г)еЛ" - непрерывна и кусочно дифференцируема, а - векторный параметр, аеИг. Заданы ограничения на начальное состояние х(<0)бА'0(а), фазовую переменную л(()е1(/,а), ограничение в конечный момент времени х(^) е ^(а) и на параметр а е А.

Множество пар (х(г),а), удовлетворяющих перечисленным условиям, а также дифференциальной системе (5), называется множеством допустимых О. Предполагается, что £> ^ 0. На множестве О задан функционал

3 Батурин В.А., Урбанович Д.Е. Приближенные методы оптимального управления, основанные на принципе расширения. - Новосибирск : Наука. Сиб. Предприятие РАН, 1997. -С. 119-120.

/(*,а^(х(0,а)+)/°(/,*,в)А. (6)

'о

Требуется минимизировать функционал / на множестве И, т.е. найти такую

последовательность {(л^(г),а^сК, чтобы выполнялось /(х,, ) —> ¡п£/ = /.

о

при 5 —> со, в частности, найти минималь (х.(1),а.) е В, на которой 1(х,, а.) = /., если такой элемент существует на множестве В. Предположим, что при каждом значения параметра а система (5) имеет единственное решение — функцию х(/). Тогда на множестве О функционал

I зависит, на самом деле, только от а, т.е. 1(х, а) = /(я).

Задача улучшения для задачи с параметром формулируется следующим образом: имеется элемент (х1 (1),аг) е £>, требуется найти такой элемент (х!!и),ап)е £>, чтобы выполнялось неравенство 1{х",а") < 1(хг ,а!).

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

Утверждение 1.1. Справедливы следующие формулы для производных функционала 1(а) в точке а':

/>') = Ра(х'и11а')~ ¡ВДАО, ИО.я'М, (7)

(,Г (8)

'о

где Н(1,х,р,а) = /°(/,д:,а); л/(/) находится из системы (5) при

а = а'; функции '//(0> ??(0 находятся из системы

¿У - н

^ = „ - - Я , (9)

) = -/=;(*'(',). а').

<T(tl) = -Fa(x'(tl),a'),

в которой y/(t) — и-вектор; &(t) — п х п -симметрическая матрица; rj(t) - матрица размерности пхг; все производные функции H вычисляются в точке

Алгоритм для задачи с параметром

1. Задаем значение параметра а', из системы (5) находим х' (/).

2. Находим y/(t), <j(1) и rj{t) из системы (9).

3. По формулам (7), (8) вычисляем 1„(а') и 1аа(а').

4. Задаем а = а' — a-[aîaa(a') + (l — cc)Ej -îa(a') и находим значение а" как решение задачи одномерной минимизации î(a(a")) = min î(a(a)).

ае[ 0,1)

5. Из системы (5) при а = а" вычисляем x"(t).

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

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

имеется элемент (х1 (t),u!(<)) е D, требуется найти такие значения параметров а, р, у, чтобы найденный при этих значениях элемент (x/r(t),ïïIl(t))eD был наилучшим (в смысле наименьшего значения функционала) среди всех элементов (х11 (t),uH (t)) е D, найденных при различных допустимых значениях а, р, у.

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

А именно, после выполнения пунктов 1-5 алгоритма улучшения (слабого или сильного) получаем:

решается система ~ = /(1,х,й((,х,а)), л(/0) = лг0, находятся х" и ип = и(1,х" ,а), вычисляется значение функционала /(*",«") = /=•(*"(/,))+ ]/°(1,х"М1,х",а))с1(.

'о

Необходимо найти такое значение параметра а, чтобы х"(<) и ы"(£)), вычисленные по алгоритму при этом значении а, как можно больше улучшали функционал.

Введем обозначения: /{г,х,й(^,х,а)) = g(t,x,a), /°(1,х,й(1,х,а)) = ¿>(1,х,а). Тогда получаем следующую задачу:

л

требуется минимизировать функционал /(а) = 1{х,а) = Г(х(1])) + ^°(1,х,а)(11,

'о

где - непрерывные и кусочно дифференцируемые функции, удовлетворяющие на [Г0,Г,] системе дифференциальных уравнений

& = g(t,x,a), д:(/0) = х0, а - параметр-вектор размерности т + п +1 (или

2и + 1).

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

В то же время это задача с параметром, представленная в разделе 1.3, и, решая данную задачу с параметром итерационным путем с помощью рассмотренного там же алгоритма улучшения, получаем следующие результаты:

1) начальное приближение а1 = (а1 ,р! ,уг), х1 =х"(*)> где х"(г) - состояние, найденное в результате выполнения первого шага алгоритма сильного или слабого улучшения (при а = а1, р = р1, у = у');

2) при 1/7(0, сг(0, ?7(0> найденных из системы с1у/ _ ~

1Г—Н"

^■ = -Нха-тНщ-Нхч,т, (Ю)

у>(0 = -Рх(х" (О),

'!(',) =-КМ"(О),

где = я); производные функции И вычисляют-

ся в точке (1,х/!), выполняется

; 0 = }[//„„ + Я„, • /КО + [/;(?)]' (И)

'о 'о

В разделе 2.2 на основании формул (11) выведены формулы для производных функционала по компонентам параметра а = (а,Д,/у),

« = 1 ,т, 7 = 1,п в алгоритме слабого улучшения.

Утверждение 2.1. В алгоритме слабого улучшения справедливы следующие формулы для производных функционала по параметрам в точке (а°,/?°У):

I

К =-1ни(1,х">у,и")\ .{[я: -(1-а°)/?°]-1 {Яци(гУ,УаУ) + /?°]х

'о

, (12) -[я;„-(1-а0)^0]" -[Яи(гУ,^У) +

+ {H:ч,aa+Hwc{t,x^ ^и'Жх"-х')^ !Л = -][Я„(£,*"^(0>«")]' • -(1 -а0)/?0]"' ■ [я^У У)-(1-а°)£,.]х

А)

х[я;„ +(Я^ + Я:)У' -х'Л-[я° -а-а0)^0!' х

-11-1 _J (13)

X [Я.°(гУ ,!ГДУ ) + (Н"ад + Я°(гУ,удУ))У-*')]} А, I = 1,«;

4 =-')[Я^Л^(0У)]' '{[Я: -(1-ав)у8°X' -Я» (/У

*[>: - (1 -«V]"' х [я; + (Я„"<т + Я" [л- - (1 - «°)/?0Т' X

В формулах (12)-(14)

H(t,.x.p,u) = р' ■ /(/,*,«)- f\t,x,u)\

H"(t,x, р,и,а) = p • f{t,x,u) - af"(t,x,u) ;

H°(t,x,p,u) = p'-f(t,x,м); функции y/(t) и a{t) находятся из системы (3) при а = а0, /? = /?°, у = у\

функция (¡/(t) - из системы ^- = -Hx(t,x",у/,а'), = -Fx(x"(/,)),

где H(t,x,p,à) = p'g(t,x,a) — g"(t,x,a), а'=(а°,Д°,//)> i = l,m, j = \,п ; производные функции , аргументы которых опущены, вычисляются в точке {t,x',цт,и'}; Ej — квадратная матрица тхт, у которой элемент с, = 1, а все остальные элементы равны нулю. Функции !^а(0> ста(0» °д(0»

i = l,m, УГ;(0> (О »У = 1,л находятся из систем, полученных дифференцированием системы (3) соответственно по а, Д и уs.

Получены также формулы для вторых производных функционала по компонентам параметра и системы дифференциальных уравнений для нахождения y/a(t), <ra(t), YplO, сгд(0, i = \,m, УГ/(0> <Trj(t)J = l,n.

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

Модифицированный алгоритм слабого улучшения

1. Задаем управление ul(t), из системы (1) находим x' (t).

2. Задаем значения параметров а = а', p — fi', у = у'.

3. Из системы (3) при а', /?', у' вычисляем y/(t) и сг({).

4. Задаем управление и = и1 + Дм,

где àu(t,Ax) = -(HZ -(1 -«)/?)"'[//; + {H«vo + irjàx], Ax = x-x', производные функции Ha вычисляются в точке (t,x' (t),y(t),u' (t)).

5.Изсистемы = /(/, x, и), x(t0) = вычисляем x" (г), а затем находим u"(t) = u'(t) + Au(t,x"-х').

6. Вычисляем /„, /д и / в точке (а',р'.у') п задаем

а"=а'-<?/а, Д"=Д'-£/д, / = 1,2,...,/и, у'/=у^-£1Гт, ./ = 1,2.....„.

где £ — скалярный параметр.

Переходим к решению одномерной задачи минимизации функционала 1(а",р",у") по переменной

Функции и <т(?) при а = а", /? = /?", у = у" вычисляем по формулам /=1 м

а(1,а" ,р" ,у") = <7«,а' ,р' ,у') + аа(1,а' ,/?' ,у')(а"-«') +

^а^а^Р'УЖ-Р^ + Ъа^а^р'У^-у'). °6)

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

7. Находим и при а",р",у", у/(1,а",Р",у"), <т(?,а",Р",у"), а затем заново вычисляем х" (I) и и"{{).

Для этого алгоритма доказано свойство релаксационности. Теорема 2.1. Пусть функция Р{х) дважды непрерывно дифференцируема по

х, функции /(¿,;с,м) и х,и) дважды непрерывно дифференцируемы по совокупности переменных (х,и), и для управления и1 (I) не выполнено условие стационарности (т.е. Ни(р,х',у/,и')Ф0). Тогда алгоритм улучшает управление м7(0-

Алгоритм слабого улучшения с атг1 = 0

1. Задаем управление и' (/), из системы (1) находим х1 (*).

2. Задаем значения параметров: а = 0 и

р=р!>о.

3. Находим у/а(1,0) и сга(*,0) из системы

,Va,u')-aaHvx{t,x' ,yf,u')-Hxv(.t,x' = (17)

4. По формуле

t

/о(0) = -£яц(/>/,^а)«/)] ■j3-l-Hu(t,x',y/a,u')dt вычисляем /„(0).

'о

5. Задаем а е (0,1].

6. Находим значение а" как решение задачи одномерной минимизации функционала / по параметру а. При этом функции y/(t,a) и ait,а) вычисляем по приближенным формулам:

Ki.a) = Va(i,0)-a, cr(i,a) = cra(i,0)-a. (18)

7. Из системы = f(t,x, «), x{tQ ) = х0,

где u(t,x,a",р') = и' + Au(t,Ax,a",fi'), Ax = x-xr(i),

вычисляется x"(t), а затем находится u"(t) = и'(t) + Au(t,x" — x',a",fl'). В пункте 7 производные функции H" вычисляются в точке (t,x' ,y{t,an),u' ,а").

Итерация алгоритма с а!ШП = 0 является менее трудоемкой не только по сравнению с итерацией модифицированного алгоритма, но и по сравнению с итерацией исходного алгоритма, потому что векторно-матричная система (17) является линейной, в то время как в системе (3) при заданном \j/(t) уравнение на а — уравнение Риккати.

В разделе 2.4 доказаны теоремы о релаксационности и сходимости алгоритма с амп= 0.

Теорема 2.2. Пусть функция /•"(*) дважды непрерывно дифференцируема по л-, функции /(г,*,!/) и /°(/,;с,г/) дважды непрерывно дифференцируемы по совокупности переменных (х,и), и управление и'(1) удовлетворяет условию Ни(1,х',ц/а,и') Ф 0. Тогда алгоритм улучшает управление и'(1). Теорема 2.3. Пусть функция /*Х.х) дважды непрерывно дифференцируема по х, функции /(/,*,м) и дважды непрерывно дифференцируемы по

совокупности переменных (х,и), функционал I ограничен снизу. Тогда для последовательности |м*(0}> генерируемой данным алгоритмом, выполняется

•х

условие Ит Пя =0.

'о

В третьей главе на основе общего подхода рассматривается задача управления параметрами в алгоритмах сильного улучшения. В разделе 3.1 получены формулы для производных функционала по компонентам параметра а = (а,/3^у■), 1 = 1,п, j = \,п, в разделе 3.2 предложен новый алгоритм сильного улучшения второго порядка, аналогичный вышеприведенному новому алгоритму слабого улучшения.

Утверждение 3.1. Пусть максимум функции На(1,х,р,и) по ме£/ достигается во внутренней точке множества и (или £/ = Ят). Тогда в алгоритме сильного улучшения справедливы следующие формулы для производных функционала по параметрам в точке (а\р° ,у°):

'о

X Я„(г,,уа + СГ„(*" - ),и")А; (19)

/д = |я/ (1,х",ц?У)- [я;ц + и(х"-х'\И*)]"' X

'о

X Я°(?,*",+ <Тд(х"-х'),и")Л, I = ; (20)

г,

lrt = jHu\t,x",it,u")-[H^(t,x",y + cr(x" «")]"' X

'о

xH°(t,x",^rj+arj(x"-x'),u")dt, J = m. (21)

В формулах (19)-(21) H(t,x,p,u) = p' ■ f(t,x,u)-f°(t,x,u)\ H"(t,x,p,u,a) = p'- f(t, x,u)~ af0 (/, u);

H°(t,x,p,u) = p'■ f(t,x,u)\ функции у(г) и cr(t) находятся из системы (4) при а = а", Р = у = у°,

функция y/(t) - из системы ^~- = -Hx(t,x" ^(i,) = -Fx(x"(t,)),

где H(t,x,p,a) = p'g(t,x,a)~ g°(t,x,a), a' =(a° ,yД / = l,n, y' = l,n; производные функции H" вычисляются в точке (t,x',у/,и')\ функции y/a(t), <ra(t), Уд(<)> Vo(0> стг/0 находятся из приведенных

в работе систем, полученных дифференцированием системы (4) по а, Д, у}, соответственно.

Модифицированный алгоритм сильного улучшения

1. Задаем управление и1 (t), из системы (1) находим х' (/).

2. Задаем значения параметров: а = а', Р = /?', у = у'-

3. Из системы (4) при а', /?', у' вычисляем и cr(i).

4. Из системы ^ = f{t,x,u(t,x,p)), x(t0) = х0,

где u(t,x,p)) = argmaxHa(t,x,p,и), р = y/(t) + cr(t)Ах, Ax = x — xl(t) вы-

ueU

числяем х11 (i).

5. Находим мя(<) = u(t,xn (t),y/(t) + a{t){x" {t) - x'{t))).

6. Вычисляем /а, /д и в точке (а',/31,/) и задаем

а" Д"=Д'-£/д, ¿ = 1,2.....w, ^ = Г,'7 =1,2,...,и,

где £ - скалярный параметр.

Переходим к решению одномерной задачи минимизации функционала i(a",р",у")по переменной

Функции y/(i) и сг(0 при а=а", р = р", у = у" вычисляем по формулам (15), (16).

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

7. Находим и при а",/?",у", y(t,a",р",у"), <r(t,a",р",у"), а затем заново вычисляем х" (t) и и11 (t).

Для этого алгоритма также доказано свойство релаксационности. Теорема 3.1. Пусть функция F(x) дважды непрерывно дифференцируема по

х, функции f(t,x,u) и f°(t,x,u) дважды непрерывно дифференцируемы по совокупности переменных (х,и), а функции II(t,x,p,u), Jf(t,x,p) и u(t,x,p) удовлетворяют условиям:

1) функция 7f(t,x,p) непрерывна и трижды непрерывно дифференцируема по совокупности переменных (х,р);

2) существует непрерывная и дважды дифференцируемая по р функция H(t,x,p) такая, что выполняется H(t,x,p,U(t,x,p)) = H{t,x,p).

Пусть максимум функции H(t,x,p,u) по ме£/ достигается во внутренней точке множества U (или U — Rm). Тогда, если (х! (t),u' (t)) не является экстремалью Понтрягина, то алгоритм улучшает управление и1 (t).

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

В разделе 4.1 дано описание комплекса программ для решения задачи оптимального управления со свободным правым концом с помощью алгоритмов последовательных улучшений, изложенных в главе 1 (назовем их базовыми), и с помощью новых алгоритмов, предложенных в главах 2 и 3 (назовем их модифицированными).

Комплекс программ, написанных на языке Фортран, реализован на ПЭВМ (ПК) серии IBM PC в операционной среде WINDOWS 98. Он предназначен для решения задач, сформулированных в следующем виде: , 'i ^ = f(t,x,u), *(/„) = *„, te[ta,tj, I(x,u) = F(x(tl))+ jf°(t,x,u)dt-+ min,

'о

x(t)&R", u(t) e R" (если используется метод слабого улучшения) и u(t) е (/ с R" (если используется метод сильного улучшения).

Общая организация работы с комплексом программ осуществляется следующим образом:

1. Составляются подпрограммы описания математической модели, а именно: записанные на языке Фортран выражения для функций f(t,x,u),

F(x{tx)), f°(t>x,u), H(t,x,p,u), H"(t,x,p,u), Ka(t,x,p), u(t,x,p) и их производных помещаются в соответствующие процедуры. Например, процедура для задания функции f(t,x,u) имеет вид SUBROUTINE FP(T,X,N,U,M,F) IMPLICIT REAL* 8 (A-H.O-Z) REAL* 8 X(N),U(M),F(N) (Содержательная часть: выражение на языке Фортран, задающее функцию f{Ux,u))

RETURN END

Смысл параметров процедуры FP(T,X,N,U,M,F):

Т - время; X — вектор состояния; N — размерность вектора состояния; U - вектор управления; М - размерность вектора управления; F - вектор правых частей управляемой дифференциальной системы (функция f{t,x,u)).

2. В головной программе задаются значения параметров задачи, начальное значение вектора управления, управляющие параметры алгоритма и указывается выбор одного из четырех алгоритмов: 1) базовый алгоритм слабого улучшения; 2) модифицированный алгоритм слабого улучшения; 3) базовый алгоритм сильного улучшения; 4) модифицированный алгоритм сильного улучшения.

К параметрам задачи относятся:

- начальный и конечный моменты времени;

- размерность вектора состояния;

- размерность вектора управления;

- вектор состояния в начальный момент времени;

- количество точек дискретизации;

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

К управляющим параметрам алгоритма относятся:

- максимальное количество итераций;

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

- начальные значения параметров а, Р,у.

3. Осуществляются процессы компиляции, создания исполняемого файла и его исполнения (решения задачи). Результаты вычислений записываются в файл.

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

Пример

■^р- = х, + Sin х. + Sin и dt 2 1

^ = xrSinu-Cosx2 , I(x,u) = ;с2(1), /е[0,1], u(t)eR. *,(0) = 0 .*,«>) = 0

Начальное управление u'(í) = 0.1, шаг интегрирования Л = 0.001, точность вычисления функционала е = 0.0001.

В этом примере на первой итерации алгоритма при амг1 = 1 не удается проинтегрировать сопряженную систему (она не имеет решения на всем отрезке [/„,/,]). В этом случае как базовый, так и модифицированный алгоритмы вынуждены уменьшать значение а на 30% и заново выполнять итерацию. В таблице 4.14 представлены результаты вычислений алгоритмами слабого улучшения в случае, когда а>ю„ = 0.7. Таблица 4.14

Базовый алгоритм слабого улучшения Модифицированный алгоритм слабого улучшения

[ Номер итерации Значение параметра а Значение функционала Номер | итерации | Значение параметра а Значение функционала

0 1 2 3 4 5 6 7 8 9 0.7 0.7 0.7 0.7 0.7 0.7 0.7 0.7 0.7 0.7219211Е-02 -0.1676369Е-02 -0.4768544Е-01 -0.1009471Е+00 -0.1192124Е+00 -0.1253517Е+00 -0.1280228Е+00 -0.1295366Е+00 -0.1305716Е+00 -0.1313599Е+00 0 1 2 3 4 5 0.7203 0.75 0.8519 0.9759 0.9759 0.7219211Е-02 -0.4264752Е-02 -0.8902828Е-01 -0.1227605Е+00 -0.1359111Е+00 -0.1359273Е+00

23 0.7 -0.1351940Е+00

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

Раздел 4.3 посвящен решению задачи управления эколого-экономической моделью:

у = Ау+Аа&-+Вг + В Ц-л-СчЛ-р, р А ' Ж ^

Л к ' " И! '

где v(/) - вектор потока общественного продукта; z(f) - вектор интенсивности восстановления природных ресурсов; Z{t) - вектор мощностей восстановительных отраслей; p{t) - вектор конечного непроизводственного потребления; г(/) - вектор, характеризующий состояние природных ресурсов; 7 -вектор естественного состояния ресурсов; А - матрица прямых затрат на производство продукта; Ар - матрица затрат на расширение производства; В

- матрица затрат на восстановление ресурсов; Вр - матрица затрат на расширение мощности восстановления ресурсов; С - матрица, отражающая амортизационные затраты; К - матрица естественного восстановления и взаимного влияния ресурсов; D,Dp - матрицы, отражающие расходы ресурсов, связанные с текущим производством и его расширением. Очевидно, что должны выполняться следующие неравенства: 0 < v < К; К > 0;

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

лезности. Первое слагаемое под знаком интеграла характеризует степень отклонения ресурсов от естественного состояния, а второе - потребление. Величина Л, >0 и вектор Яг >0 — весовые коэффициенты, е"е' - функция, отражающая дисконтирование.

Осуществляется переход к задаче оптимального управления данной эколого-экономической системой, при этом предполагается, что можно управлять интенсивностью изменения мощностей восстановительных отраслей Щ- и конечным потреблением р, т.е. = ы,, р = и1. В функционал ш Л

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

0<z<Z; Z>0; Rmin<r<R,

'так *

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

Основные результаты диссертации, выносимые на защиту

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

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

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

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

Публикации по теме диссертации

1. Батурин В.А. Метод последовательных улучшений в задаче идентификации / В.А. Батурин, C.B. Черемных // Первая конференция молодых ученых : тез. докл. (г. Иркутск, ИГУ им. A.A. Жданова). — Иркутск, 1983. - С. 19.

2. Батурин В.А. О методе последовательных улучшений второго порядка /

B.А. Батурин, C.B. Черемных // Вторая конференция молодых ученых : тез. докл. (г. Иркутск, ИГУ им. A.A. Жданова). - Иркутск, 1984. - Ч. 1. -

C. 8.

3. Батурин В.А. Задача управления параметрами в алгоритмах улучшения для задач оптимального управления / В.А. Батурин, C.B. Черемных И Математика, ее приложения и математическое образование: материалы Меж-

дународной конференции (24-28 июня 2002 г., Улан-Удэ). - Улан-Удэ, 2002.-С. 68-75.

4. Батурин В.А. Модификация метода сильного улучшения второго порядка для задач оптимального управления / В.А. Батурин, С.В. Черемных// Ин-фокоммуникационные и вычислительные технологии и системы: Материалы Всероссийской конференции (5-9 авг. 2003 г., Улан-Удэ - оз. Байкал). - Улан-Удэ, 2003. - С. 36-39.

5. Батурин В.А. Модификация метода сильного улучшения второго порядка для задач оптимального управления / В.А. Батурин, С.В. Черемных // Ля-пуновские чтения & презентация информационных технологий : тез. докл. (24-26 декабря 2003 г., Иркутск). - Иркутск, 2003. - С. 10.

6. Черемных С.В. Модифицированные алгоритмы улучшения второго порядка для задач оптимального управления / С.В. Черемных // Филология и современное лингвистическое образование: материалы региональной конференции молодых ученых (2-4 марта 2004 г., Иркутск). - Иркутск: ИГЛУ, 2004.-С. 155-158.

7. Baturin V.A. Optimization of Parameters in the Second-Order Improving Algorithms for Optimal Control Problems / V.A. Baturin, S.V. Cheremnykh // Generalized solutions in control problems : Proceedings of the IFAC Workshop GSCP-2004 and satellite events (September 21-27, 2004, Pereslavl-Zalessky, Russia). - Moscow: Fizmatlit, 2004. - P. 13-17.

8. Батурин В.А. Алгоритмы управления параметрами в методах последовательных улучшений второго порядка / В.А. Батурин, С.В. Черемных И Вычислительные технологии, т. 9. Вестник КазНУ им. Аль-Фараби, № 3(42): совместный выпуск по материалам Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (7-9 окт. 2004 г., Алматы). — Алматы - Новосибирск, 2004. - 4.1. -С. 260-265.

9. Батурин В.А. Управление выбором параметров в алгоритмах слабого улучшения второго порядка для задач оптимального управления / В.А. Батурин, С.В. Черемных // Изв. РАН. Теория и системы управления. - 2006. -№2. - С. 54-60.

Редакционно-издательский отдел Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, 134 Подписано к печати 26.04.06.

Формат бумаги 60 х 84 1/16, объем 1 п.л. Заказ 2. Тираж 100 экз.

Отпечатано в ИДСТУ СО РАН

Введение.

Глава 1. Необходимые сведения о задачах оптимального управления.

1.1. Постановка задачи и достаточные условия оптимальности.

1.2. Алгоритмы последовательных улучшений.

1.3. Задача с параметром.

Глава 2. Задача управления параметрами в алгоритмах слабого улучшения.

2.1. Автоматизация выбора значений параметров алгоритма в задаче оптимального управления.

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

2.3. Новые алгоритмы слабого улучшения 2-го порядка.

2.4. Свойства алгоритма с astart =

Глава 3. Задача управления параметрами в алгоритмах сильного улучшения.

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

3.2. Новый алгоритм сильного улучшения 2-го порядка.

Глава 4. Программно-алгоритмическая реализация.

4.1. Описание программного комплекса.

4.2. Тестовые примеры.

4.3. Задача управления эколого-экономической моделью.

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

Основополагающими результатами теории оптимального управления являются: принцип максимума JI.C. Понтрягина, метод динамического программирования Р. Беллмана, достаточные условия оптимальности В.Ф.Кротова. На основе этих классических результатов созданы различные методы последовательных улучшений первого и второго порядка. Наиболее изученными оказались такие классы задач оптимального управления как линейные, билинейные, квадратичные задачи. Свойства перечисленных классов задач позволяют упростить многие операции, необходимые для поиска решения, что приводит к созданию эффективных алгоритмов улучшения. Сложнее обстоит дело, когда надо решать задачу оптимального управления нелинейной системой, характер нелинейности которой не известен заранее. Алгоритмы последовательных улучшений, разработанные в предположении, что система и функционал имеют общий вид, как правило, содержат параметры, роль которых - регуляторы шага, обеспечивающие эффективное решение задачи улучшения. В результате, эффективность такого алгоритма в той или иной степени (иногда в очень большой) зависит от выбора значений параметров. В то же время вопрос выбора наилучших значений параметров либо сводится к решению одномерной задачи минимизации (если она не трудоемка, то решение вопроса закрыто), либо часто не рассматривается, считается достаточным указать только область допустимых значений. Поэтому при практическом решении задачи оптимального управления достаточно хорошие значения параметров алгоритма обычно находятся методом «проб и ошибок», отнимая у пользователя много времени.

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

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

Большую группу составляют методы градиентного типа [Брайсон, Хо Ю-Ши, 1972; Васильев О.В., 1994; Васильев О.В., Аргучинцев, 1999; Келли, 1965; Кротов, Гурман, 1973; Полак, 1974; Сеа, 1973; Федоренко, 1978; Шатровский, 1962; Энеев, 1966]. При наличии ограничений на управление и фазовые переменные в градиентных методах первого порядка возникают трудности, которые преодолеваются путем модификации алгоритмов. Некоторые модификации связаны с методом штрафных функций [Гермейер, 1971], другие — это методы спуска в пространстве управлений, представляющие собой аналоги методов конечномерной оптимизации: условного градиента, проекции градиента [Демьянов, Рубинов, 1968; Федоренко, 1975], возможных направлений [Зойтендейк, 1963; Гюрджиев, 1980]; сопряженных градиентов [Брайсон, Хо Ю-Ши, 1972; Федоренко, 1978].

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

Евтушенко, 1982; Моисеев, 1975; Мордухович, 1980; Пшеничный, Данилин, 1975].

Еще одну группу составляют метод вариаций в фазовом пространстве [Васильев Ф.П., 1980; Моисеев, 1964, 1966, 1975; Федоренко, 1978] и его разновидности: метод локальных вариаций [Крылов, Черноусько, 1966; Черноусько, Баничук, 1973] и метод блуждающей трубки [Моисеев, 1966].

Открытый JI.C. Понтрягиным принцип максимума широко используется для построения вычислительных методов решения задач оптимального управления [Аргучинцев, Васильев О.В., 1996; Васильев О.В., 1994; ВасильевО.В., Бельтюков, Терлецкий, 1991; Васильев О.В., Надежкина, 1996; ВасильевО.В., Срочко В.А., Терлецкий, 1990; Васильев О.В., Тятюшкин, 1981, 1983; Васильев Ф.П., 1980, 1981; Любушин, Черноусько, 1983; Моисеев, 1975; Срочко, 1989; Федоренко, 1978; Черноусько, Колмановский, 1977]. Эти работы наиболее полное отражение нашли в монограмме В.А. Срочко [Срочко, 2000]. Простейший алгоритм предложен в работе [Крылов, Черноусько, 1962], он предусматривает последовательное интегрирование исходной и сопряженной систем и выбор управления из условия максимума функции Понтрягина. Метод далеко не всегда сходится, однако известны его модификации, обладающие релаксационностью и сходимостью [Крылов, Черноусько, 1972; Любушин, 1979, 1982; Цирлин, Балакирев, Дудников, 1976].

Для линейных и выпуклых задач оптимального управления принцип максимума Л.С. Понтрягина является не только необходимым, но и достаточным условием оптимальности. Поэтому во всех случаях, когда управляемые процессы можно с достаточной степенью точности моделировать (аппроксимировать) линейными уравнениями, целесообразно применять методы, ориентированные на решение задач оптимального управления для линейных систем [Габасов, Кириллова, 1973, 1981, 1983;

Еремин, Астафьев, 1976; Оптимальное управление ., 1993] и методы линеаризации [Федоренко, 1978].

В работах [Аэродинамика, 1968; Jacobson, 1968] предложены методы, основанные на разложении до второго порядка включительно функции Беллмана и левой части уравнения Беллмана. Для обеспечения близости соседних приближений предлагается применять процедуру не на всем отрезке [а на последней его части [г,?,], при этом г выступает в алгоритме как регулятор.

Развитие методов, основанных на принципе расширения, началось с теоремы В.Ф. Кротова, указывающей достаточные условия оптимальности. В этих условиях присутствует функция, получившая название функции Кротова (Кротова-Беллмана), которая определяется неединственным способом, что дает возможность создавать различные алгоритмы для решения задач оптимального управления. Первые такие алгоритмы описаны в работах [Кротов, 1962-1965, 1975; Кротов, Букреев, Гурман, 1969; Кротов, Гурман, 1973]. В трудах В.И. Гурмана метод Кротова получил дальнейшее развитие и название «принципа расширения». В работах [Кротов, Фельдман, 1978, 1983] представлен алгоритм последовательных улучшений управления, основанный на достаточных условиях оптимальности. На каждой итерации этого алгоритма выполняется интегрирование сопряженной и линейной матричной систем и замыкание исходной системы синтезирующим управлением с линейно-квадратической аппроксимацией функции Кротова.

Следует отметить работы А.И. Москаленко по теоремам сравнения в динамических системах, которые дали толчок для разработки методов решения задач оптимального управления распределенными системами [Москаленко, 1983].

В.И. Гурманом и его учениками были созданы алгоритмы последовательных улучшений первого и второго порядка [Батурин, Урбанович, 1997; Гурман, 1997; Гурман, Батурин, Расина, 1983; Гурман,

Расина, 1979; Новые методы 1987], в которых используется тейлоровское представление с точностью до первого или второго порядка функции Кротова в окрестности текущего приближения. При этом может оказаться, что траектория следующего приближения удаляется от текущей в область, где линейно-квадратическое приближение функции Кротова «не работает», так что улучшение происходить не будет. Для преодоления этой трудности в алгоритмах применены специальные регуляторы близости: в [Гурман, Батурин, Расина, 1983] - аддитивный квадратический функционал с регулируемым весом, в [Батурин, Урбанович, 1997] строится вспомогательный функционал, состоящий из суммы исходного и квадратического функционалов, умноженных на весовые коэффициенты. Если требование близости накладывается на обе компоненты процесса -состояние и управление, то такой алгоритм называют алгоритмом слабого улучшения, если требование близости накладывается только на компоненту состояния, то это алгоритм сильного улучшения. Для алгоритмов сильного и слабого улучшения второго порядка доказаны свойства релаксационности и сходимости [Батурин, Урбанович, 1997], они улучшают любую не оптимальную в локальном смысле программу управления, в том числе и экстремаль Понтрягина.

Среди методов, основанных на принципе расширения, можно выделить в отдельную группу методы, которые основаны на локальных аппроксимациях множества достижимости управляемой дифференциальной системы [Батурин, Гончарова, 1999; Гончарова, Гуркало, 2004; Гурман, Батурин, 1985; Гурман, Константинов, 1981; Константинов, 1983].

При практическом решении задач оптимального управления с помощью наиболее распространенных методов (принципа максимума Понтрягина, принципа оптимальности Беллмана и модификаций классических методов) исследователи столкнулись с различными трудностями: отсутствие искомого оптимального режима в классе сравниваемых, множественность решений, отвечающих необходимым условиям, неприменимость известных достаточных условий. Задачи, в которых встречались подобные трудности, были выделены в отдельный класс задач оптимального управления, получивший название «вырожденные задачи». На основе принципа расширения создано немало эффективных методов для решения вырожденных задач оптимального управления [Гурман, 1967, 1977; Гурман, Батурин, 1980, 1981; Гурман, Расина, 1979; Дыхта, 1991, 1994; Дыхта, Деренко, 1994; Дыхта, Самсонюк, 2000; Казаков, Кротов, 1987; Колокольникова, 1992; Baturin, Verkhozina, 2003].

В алгоритмах сильного и слабого улучшения второго порядка, изложенных в работе [Батурин, Урбанович, 1997], на каждой итерации необходимо интегрировать векторно-матричную систему дифференциальных уравнений, зависящую от параметров, которые как раз и выполняют роль регуляторов близости (шага). Значения этих параметров задаются в самом начале работы алгоритма и определяют глубину улучшения функционала, а следовательно, и ход всего итерационного процесса. Изменение параметра влечет за собой переинтегрирование вспомогательной системы, а это самый трудоемкий процесс в этапах алгоритма. Удачный выбор значений параметров может существенно повысить эффективность работы всего алгоритма. Исследование проблемы поиска наилучших значений параметров алгоритма потребовало рассмотрения особого класса задач оптимального управления - задач оптимального управления с параметром. Схемы (алгоритмы) решения этих задач методами второго порядка предложены в [Батурин, Урбанович, 1997].

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

Объект исследования - задача оптимального управления и алгоритмы последовательных улучшений для ее решения.

Структура работы. Работа состоит из четырех глав, введения, заключения и списка литературы.

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

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

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

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

В заключении излагаются основные результаты диссертации.

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

Практическая ценность. Разработанные алгоритмы могут использоваться при решении различных прикладных задач (технических, экономических, природно-экономических и др.). Работоспособность и эффективность этих алгоритмов подтверждена рядом тестовых примеров.

Апробация работы. Основные результаты работы докладывались и обсуждались на первой конференции молодых ученых Иркутского государственного университета (Иркутск, 1983), на второй конференции молодых ученых ИГУ (Иркутск, 1984), на Всероссийской конференции «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, 2003), на Ляпуновских чтениях (Иркутск, 2003), на региональной конференции молодых ученых «Филология и современное лингвистическое образование» (Иркутск, 2004), на семинаре «Приближенные методы и алгоритмы оптимального управления», проводимого в рамках симпозиума IFAC по обобщенным решениям в задачах управления (GSCP-2004) (Переславль-Залесский, 2004), на Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (Алматы, 2004), на VII школе-семинаре «Математическое моделирование и информационные технологии» (Иркутск, 2005), на IV Всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005), на семинарах лаборатории «Системного анализа и методов оптимального управления» и Объединенном семинаре ИДСТУ СО РАН.

Основное содержание диссертации опубликовано в работах [Батурин, Черемных, 1983, 1984, 2002, 2003, 2004, 2006; Черемных, 2004; Baturin, Cheremnykh, 2004].

выход

II III

X := х II /я и := и

Возврат от x"'(t), u'"(t) к x"(t), и" (/) и значению а перед минимизацией. FL:=FLR

Рис. 4.2. Блок-схема управляющей процедуры модифицированного алгоритма улучшения

Начальное управление и1 it) = 0.

Этот пример был решен как методом слабого, так и методом сильного улучшения. Во всех случаях были выбраны: шаг интегрирования h = 0,001, точность вычисления функционала £ = 0,0001. Начальное значение параметра алгоритма а задавалось равным единице и 0,7.

Результаты вычислений алгоритмами слабого улучшения представлены: при astart = 1 - в таблице 4.1, при ахшг, =0,7 - в таблице 4.2.

Заключение

В диссертационной работе получены следующие результаты и выводы.

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

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

3. Разработаны новые алгоритмы 2-го порядка слабого и сильного улучшения. Особенностями этих алгоритмов являются: 1) разложение по параметру решений вспомогательной векторно-матричной системы дифференциальных уравнений, что позволяет избежать ее многократного интегрирования на каждой итерации; 2) возможность применять эффективно процедуры одномерной задачи минимизации (в отличие от базовых алгоритмов второго порядка), т.е. выбирать наилучшие значения параметров на каждой итерации. Доказаны теоремы о релаксационности новых алгоритмов.

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

5. Создано программно-алгоритмическое обеспечение, реализующее предложенные в работе методы улучшения.

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

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

1. Аргучинцев А.В. Итерационные процессы принципа максимума и их модификации в системах с распределенными параметрами / А.В. Аргучинцев, О.В. Васильев // Дифференц. уравнения. 1996. - Т.32, 6. - С. 797803.

2. Аэродинамика. Ч. 1 / M.JI. Миль и др.. М. : Машиностроение, 1968. -265 с.

3. Батурин В.А. Метод улучшения, основанный на приближенном представлении множества достижимости. Теорема о релаксации / В.А. Батурин, Е.В. Гончарова // Автоматика и телемеханика. 1999. -№11. — С. 19-29.

4. Батурин В.А. Приближенные методы оптимального управления, основанные на принципе расширения / В.А. Батурин, Д.Е. Урбанович. Новосибирск : Наука. Сиб. Предприятие РАН, 1997. - 175 с.

5. Батурин В.А. Метод последовательных улучшений в задаче идентификации / В.А. Батурин, С.В. Черемных // Первая конференция молодых ученых : тез. докл. (г. Иркутск, ИГУ им. А.А. Жданова). Иркутск, 1983. - С. 19.

6. Батурин В.А. О методе последовательных улучшений второго порядка /

7. B.А. Батурин, С.В. Черемных // Вторая конференция молодых ученых : тез. докл. (г. Иркутск, ИГУ им. А.А. Жданова). Иркутск, 1984. - Ч. 1.1. C. 8.

8. П.Батурин В.А. Управление выбором параметров в алгоритмах слабого улучшения второго порядка для задач оптимального управления / В.А. Батурин, С.В. Черемных // Изв. РАН. Теория и системы управления. 2006. - №2. - С. 54-60.

9. Брайсон А. Прикладная теория оптимального управления / А. Брайсон, Хо Ю-Ши. М.: Мир, 1972. - 544 с.

10. З.Васильев О.В. Лекции по методам оптимизации / О.В. Васильев. Иркутск : Изд-во Иркут. ун-та, 1994. - 344 с.

11. Н.Васильев О.В. Методы оптимизации в задачах и упражнениях / О.В. Васильев, А.В. Аргучинцев. М.: ФИЗМАТЛИТ, 1999. - 208 с.

12. Васильев О.В. Алгоритмы оптимизации динамических систем, основанные на принципе максимума / О.В. Васильев, Н.Б. Бельтюков, В.А. Терлецкий // Вопросы кибернетики. Модели и методы анализа больших систем.-М., 1991.-С. 17-38.

13. Васильев О.В. Об одном классе обратных задач оптимального управления / О.В. Васильев, Н.В. Надежкина // Изв. ВУЗов. Математика. 1996. -№ 3. -С. 14-20.

14. П.Васильев О.В. Методы оптимизации и их приложения. Ч. 2. Оптимальное управление / О.В. Васильев, В.А. Срочко, В.А. Терлецкий ; отв. ред. докт. физ.-мат. наук А.П. Меренков. Новосибирск : Наука. Сиб. отд-ние, 1990. - 151 с.

15. Васильев О.В. Об одном методе решения задач оптимального управления, основанном на принципе максимума / О.В. Васильев, А.И. Тятюшкин // Журн. вычисл. математики и мат. физики. 1981. - т. 21, 6. - С. 13761384.

16. Васильев Ф.П. Численные методы решения экстремальных задач / Ф.П. Васильев. М. : Наука, 1980. - 520 с.

17. Васильев Ф.П. Методы решения экстремальных задач / Ф.П. Васильев. -М. : Наука, 1981. -400 с.

18. Габасов Р. Оптимизация линейных систем / Р. Габасов, Ф.М. Кириллова. -Минск : Белорус, гос. ун-т, 1973. 248 с.

19. Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск : Белорус, гос. ун-т, 1981. — 350 с.

20. Габасов Р. Конструктивные методы оптимального управления / Р. Габасов, Ф.М. Кириллова // Изв. АН СССР. Техн. кибернетика. 1983. - № 2. -С. 169-185.

21. Гермейер Ю.Б. Введение в теорию исследования операций / Ю.Б. Гермей-ер. -М. : Наука, 1971.-383 с.

22. Гончарова Е.В. Численная реализация алгоритмов улучшения, основанных на локальных оценках множеств достижимости / Е.В. Гончарова, Е.Н. Гуркало // Вычислительные технологии. 2004. - Т.9, Ч. 2. - С. 113119.

23. Гурман В.И. Метод кратных максимумов и условия относительной оптимальности вырожденных режимов // Автоматика и телемеханика. 1967. -№ 11.-С. 38-45.

24. Гурман В.И. Вырожденные задачи оптимального управления / В.И. Гурман. М. : Наука, 1977. - 304 с.

25. Гурман В.И. Принцип расширения в задачах управления / В.И. Гурман. -М.: Наука, 1997.-288 с.

26. Гурман В.И. Улучшение и локальный синтез управления в вырожденных задачах с ограниченным множеством скоростей / В.И. Гурман, В.А. Батурин. Иркутск, 1980.-14 с.-Деп. в ВИНИТИ, 1981, №618-81 Деп.

27. Гурман В.И. Улучшение и локальный синтез управления. Вырожденные задачи / В.И. Гурман, В.А. Батурин. 24 с. - Деп. в ВИНИТИ, 1981, №618а-81 Деп.

28. Гурман В.И. Алгоритм улучшения управления, основанный на оценках областей достижимости / В.И. Гурман, В.А. Батурин. Деп. в ВИНИТИ, 1985, №651-85.

29. Гурман В.И. Приближенные методы оптимального управления / В.И. Гурман, В.А. Батурин, И.В. Расина. Иркутск : Изд-во Иркут. ун-та, 1983.-178 с.

30. Гурман В.И. Множества достижимости управляемых систем. Связь с управлением Беллмана / В.И. Гурман, Г.Н. Константинов. Иркутск, 1981. - 14 с.-Деп. в ВИНИТИ 14.08.1981, № 4038-81 Деп.

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

32. Гюрджиев В.Г. Метод возможных направлений для решения задачи оптимального управления с фазовыми ограничениями / В.Г. Гюрджиев. М., 1980. - 13 с. - Деп. в ВИНИТИ 18.09.1980, № 4099-80 Деп.

33. Демьянов В.Ф. Приближенные методы решения экстремальных задач / В.Ф. Демьянов, A.M. Рубинов. -Л. : ЛГУ, 1968. -179 с.

34. Дыхта В.А. Вариационный принцип максимума и квадратичные условия оптимальности импульсных и особых режимов / В.А. Дыхта ; Препринт Иркут. ВЦ АН СССР. Иркутск, 1991. - 7. - 42 с.

35. Дыхта В.А. Вариационный принцип максимума и квадратичные условия оптимальности импульсных и особых режимов // Сиб. матем. журн. -1994.-Т. 35, 1.-С. 70-82.

36. Дыхта В.А. Оптимальное импульсное управление с приложениями / В.А. Дыхта, О.Н. Самсонюк. М. : ФИЗМАТЛИТ, 2000. - 256 с.

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

38. Еремин И.И. Введение в теорию линейного и выпуклого программирования / И.И. Еремин, Н.Н. Астафьев. М.: Наука, 1976. - 191с.44.3ойтендейк Г. Методы возможных направлений / Г. Зойтендейк. — М. : Изд-во иностр. лит., 1963. 176 с.

39. Казаков В.А. Оптимальное управление взаимодействием света с веществом / В.А. Казаков, В.Ф. Кротов // Автоматика и телемеханика. 1987. -№4.-С. 9-15.

40. Келли Г. Метод градиентов // Методы оптимизации с приложениями к механике космического полета. — М.: Наука, 1965. С. 101 -116.

41. Колокольникова Г.А. Исследование обобщенных решений задач оптимального управления с линейными неограниченными управлениями на основе кратных преобразований // Дифференциальные уравнения. 1992. -Т. 28, № 11.-С. 1919-1932.

42. Константинов Г.Н. Нормирование воздействий на динамические системы / Г.Н. Константинов. Иркутск : Изд-во Иркут. ун-та, 1983. - 187 с.

43. Кротов В.Ф. Вычислительные алгоритмы решения и оптимизации управляемых систем уравнений : (I, II) // Техн. кибернетика. 1975. -№ 5. - С.З-15; №6.- С. 3-13.

44. Кротов В.Ф. Новые методы вариационного исчисления в динамике полета / В.Ф. Кротов, В.З. Букреев, В.И. Гурман. М. : Машиностроение, 1969. -288 с.

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

46. Кротов В.Ф. Итерационный метод решения экстремальных задач / В.Ф. Кротов, И.Н. Фельдман // Моделирование технико-экономических процессов. М. : МЭСИ, 1978. - С. 54-65.

47. Кротов В.Ф. Итерационный метод решения задач оптимального управления / В.Ф. Кротов, И.Н. Фельдман // Изв. АН СССР. Техн. кибернетика. -1983.-№ 2.-С. 160-168.

48. Крылов И.А. О методе последовательных приближений для решения задач оптимального управления / И.А. Крылов, Ф.Л. Черноусько // Журн. вычисл. математики и мат. физики. 1962. - Т. 2, № 6. - С. 1132-1139.

49. Крылов И.А. Решение задач оптимального управления методом локальных вариаций / И.А. Крылов, Ф.Л. Черноусько //Журн. вычисл. математики и мат. физики. 1966. -Т. 6, № 2. - С. 203-217.

50. Крылов И.А. Алгоритмы метода последовательных приближений для задач оптимального управления / И.А. Крылов, Ф.Л. Черноусько //Журн. вычисл. математики и мат. физики. 1972. - Т. 12, № 1.-С. 14-34.

51. Любушин А.А. Модификации и исследование сходимости метода последовательных приближений для задач оптимального управления // Журн. вычисл. математики и мат. физики. 1979. - Т. 19, № 6. — С. 1414-1421.

52. Любушин А.А. О применении модификации метода последовательных приближений для решения задач оптимального управления //Журн. вычисл. математики и мат. физики. 1982. - Т. 22, № 1. - С. 30-35.

53. Любушин А.А. Метод последовательных приближений для расчета оптимального управления / А.А. Любушин, Ф.Л. Черноусько // Изв. АН СССР. Техн. кибернетика. 1983. - № 2. - С. 147-159.

54. Моисеев Н.Н. Методы динамического программирования в теории оптимальных управлений : I. — II // Журн. вычисл. математики и мат. физики. — 1964. Т.4, № 3. - С. 485-494; Т. 5, № 1. - С. 44-56.

55. Моисеев Н.Н. Численные методы теории оптимального управления, использующие вариации в пространстве состояний // Кибернетика. 1966. -Т. 5, № 3. - С. 1-23.

56. Моисеев Ы.Н. Элементы теории оптимальных систем / Н.Н. Моисеев. М. : Наука, 1975.-488 с.

57. Мордухович Б.Ш. Некоторые свойства многозначных отображений и дифференциальных включений с приложением к вопросам существования оптимальных управлений / Б.Ш. Мордухович. Минск, 1980. - 38 с. — Деп. в ВИНИТИ 12.12.1980, № 5268-80 Деп.

58. Москаленко Л.И. Методы нелинейных отображений в оптимальном управлении / А.И. Москаленко. Новосибирск : Наука, 1983. - 222 с.

59. Новые методы улучшения управляемых процессов./ В.И. Гурман и др.. -Новосибирск : Наука, 1987. 183 с.

60. Оптимальное управление в линейных системах / А.А. Милютин и др.. -М. : Наука, 1993.-267 с.

61. Г1олак Э. Численные методы оптимизации. Единый подход / Э. Полак. -М. : Мир, 1974.-376 с.

62. Пшеничный Б.М. Численные методы в экстремальных задачах / Б.М. Пшеничный, Ю.М. Данилин. М. : Наука, 1975. — 320 с.

63. Сеа Ж. Оптимизация. Теория и алгоритмы /Ж. Сеа. М. : Мир, 1973. -244с.

64. Срочко В.А. Вариационный принцип максимума и методы линеаризации в задачах оптимального управления / В.А. Срочко. Иркутск : Изд-во Ир-кут. ун-та, 1989. - 160 с.

65. Срочко В.А. Итерационные методы решения задач оптимального управления / В.А. Срочко. М.: ФИЗМАТЛИТ, 2000. - 160 с.

66. Федоренко Р.П. Метод проекции градиента в задачах оптимального управления / Р.П. Федоренко ; Препринт Ин-т прикл. математики АН СССР, № 45 .-М., 1975.-70 с.

67. Федоренко Р.П. Приближенное решение задач оптимального управления / Р.П. Федоренко. М. : Наука, 1978. - 488 с.

68. Цирлин A.M. Вариационные методы управляемых объектов / A.M. Цир-лин, B.C. Балакирев, Е.Г. Дудников. — М.: Энергия, 1976. 448 с.

69. Черноусько Ф.Л. Вариационные задачи механики и управления / Ф.Л. Черноусько, В.П. Баничук. М.: Наука, 1973. - 238 с.

70. Черноусько Ф.Л. Вычислительные и приближенные методы оптимального управления / Ф.Л. Черноусько, В.Б. Колмановский // Математический анализ. Итоги науки и техники. 1977.-Т. 14.-С. 101-166.

71. Шатровский Л.И. Об одном численном методе решения задач оптимального управления // Журн. вычисл. математики и мат. физики. — 1962. Т.2, № 3. - С. 488-491.

72. Энеев Т.М. О применении градиентного метода в задачах теории оптимального управления // Косм, исслед. 1966. - Т. 4, вып. 5. - С. 651 -669.

73. Baturin V.A. The Technique of Improving High-order Impulse Modes in the Optimal Control Problem / V.A. Baturin, Y.Y. Nie, I.O. Verkhozina // Mini-micro Systems. 2003. - Vol. 24. - N 2. - pp. 169-173.

74. Jacobson D.H. New second-order and first-ofder algorithms for determining optimal control. A differential programming approach // J. Optimivization Theory and Applications. 1968. -Vol. 2. - N 4. - pp. 411 -440.

75. Ortega J.M. Iterative Solution of Nonlinear Equations in Several Variables / J.M. Ortega, W.C. Rheinboldt. NY : Academic Press, 1970.