автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Методы отсечений в линейном оптимальном быстродействии

рго Ий

1 й № 2303

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

Бузинов Александр Александрович

Методы отсечений в линейном оптимальном быстродействии

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

Автореферат

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

Ярославль 2000г

Работа выполнена в Ярославском государственном университете им. П.Г.Демидова.

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

наук, профессор Левин А.Ю.

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

наук, профессор Климов B.C., доктор технических наук, профессор Бытев Д О.

Ведущая организация: Московский государственный университет

им. М.В.Ломоносова.

Защита состоится с^П^&и^ 3, 2000 года в ^ часов па заседании диссертационного совета К 064.12.04 в Ярославском государственном университете им. П.Г.Демидова по адресу 150000, г.Ярославль, ул. Советская, д.14.

С диссертацией можно ознакомится в библиотеке ЯрГУ по адресу г.Ярославль, ул. Кирова, д.8/10.

Автореферат разослан UtA^Ta. 2000 года.

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

Пендюр А.Д.

/У ¿7J

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

Актуальность темы. Теория оптимального управления стала в двадцатом веке одним из наиболее важных и бурно развивающихся разделов математики. С момента возникновения метода динамического программирования Беллмана, появление принципа максимума Понтря-гина (Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф., "Математическая теория оптимальных процессов", 1961 г.) явилось наиболее существенным шагом в развитии теории управления процессами. Принцип максимума дает необходимое условие оптимальности решения задачи управления в весьма общей постановке и его теоретическое значение трудно переоценить. Применительно к рассматриваемой в работе задаче оптимального линейного быстродействия (ЗОЛБ) принцип максимума является еще я достаточным условием оптимальности и сводит решение ЗОЛБ к рассмотрению конечномерной задачи определения подходящего начального значения фо Для сопряженной системы ф — —А'гр. Безусловно, такое сведение является важным достоинством принципа максимума, однако, длительное время не было предложено по-настоящему эффективных подходов к численному решению данной конечномерной задачи.

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

В связи со сказанным, наличие тесной связи между оптимальным управлением и математическим квазивыпуклым программированием приобретает большое значение. Идея решения задачи оптимального линейного быстродействия при помощи сочетания принципа максимума и методов отсечений была предложена, в общих чертах, Левиным А.Ю. еще четверть века назад (Левин А.Ю., "Вестник Ярославского университета", N12, 1975 г, с. 87-93). Впоследствии, в нескольких статьях Левина А.Ю. и Енчевой Т.Н. уточнялись и совершенствовались отдельные аспекты алгоритма (отделение нулей квазиполиномов в связи с определением точек переключения и т.п.). Но тот факт, что исходная идея не была реализована в виде эффективного вычислительного инструмента в течение столь длительного времени, свидетельствует о том, что на этом пути необходимо преодолеть ряд существенных трудностей, что и определяет содержание настоящей работы.

Цель работы. Цели работы сформулируем следующим образом.

1) Разработка эффективных численных алгоритмов синтеза оптимального управления для ЗОЛБ, основанных на сочетании принципа максимума Понтрягина и центрированных отсечений. Сравнение эффективности данных алгоритмов и алгоритмов основанных на исполь-

зовании градиентных методов.

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

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

Научная новизна.

1. Предложен и обоснован стохастический алгоритм минимизации выпуклых и квазивыпуклых функций, названный стохастической модификацией метода центров тяжести (СММЦТ).

2. Реализован эффективный алгоритм численного синтеза ЗОЛБ с постоянными коэффициентами, основанный на сочетании принципа максимума Понтрягина и центрированных отсечений. Суть алгоритма состоит в минимизации, методами отсечений, возникающей в ЗОЛБ квазивыпуклой функции —Р(р), точка минимума которой есть искомое начальное значение 1р0.

3. Обоснована сходимость СММЦТ применительно к решению ЗОЛБ.

4. Определены условия существования и получено выражение константы Липшица для функции —^(р). При выполнении этих условий доказана экспоненциальная скорость сходимости (по вероятности) по функционалу, для СММЦТ, при минимизации функции —

5. Проведено сравнение эффективности реализованного алгоритма решения ЗОЛБ с рекомендуемыми в литературе градиентными методами решения ЗОЛБ. Выявлено значительное преимущество применения методов отсечений над градиентными методами и подтверждена практически высокая эффективность СММЦТ.

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

Апробация работы. Основные результаты диссертации докладывались на научной конференции:"Современные проблемы естествознания", (Ярославль, 1999 год.)

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

Структура и объем работы. Диссертация состоит из введения, ■четырех глав, заключения, двух приложений и списка литературы из 48 наименований. В работе содержится 8 таблиц и 2 рисунка. Диссертация изложена на 102 страницах.

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

Как известно справедливо равенство

Для вычисления интегралов в числителе и знаменателе предлагается использовать специальную версию метода Монте-Карло. Обозначим'. 5,,(1) - единичная сфера, в Я™ и |5г,(1)| - ее (п-1)-мерный объем, го -некоторая внутренняя точка выпуклого тела V, ц(\') - объем тела V и Уу £ 5П(1), р(хо, V,у) - расстояние от точки хо до границы тела V в направлении у. В §1.2 доказывается следующая лемма.

Лемма 1.3: Пусть /(х) б ¿гО'), &,£>...- последовательность независимых реализаций случайного вектора £ равномерно распределенного на 5„(1) и С : —>■ Л" невырожденное аффинное преобразование. Тогда, при га —> оо имеет место соотношение

Статистика, стоящая слева, является несмещенной оценкой для интеграла справа. Далее в §1.3 доказывается, что данная статистика будет обладать наименьшей гарантированной оценкой сверху на дисперсию при условии, что эллипсоид Еп{хо, С) = {х : х = хъ+Сг, ||г|| < 1} является минимальным описанным эллипсоидом для выпуклого тела V.

В §1.4 доказывается следующая лемма-

Лемма 1.6: Пусть ••• - последовательность независимых реа-

лизаций случайного вектора равномерно распределенного на (1),

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

и С : Rn —У Rn невырожденное аффинное преобразование. Тогда

гп

■ Рп+> {Xü,v,cm\c(i\\n+1

п i=i п.н, , .

-™-->q (!)

+ И, <%)/!№

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

На основе соотношения (1) в §1.5 предлагается алгоритм минимизации выпуклых функций, относящийся к классу методов отсечений. Этот алгоритм сочетает использование соотношения (1) для приближенного вычисления центра тяжести текущего локализатора V с подбором для данного локализатора отображения С и точки го £ V таким образом, чтобы эллипсоид Еп(хо,С), описываемый около тела V, имел ло-возможиости меньший объем. Полученный алгоритм назван стохастической модификацией метода центров тяжести (СММЦТ).

Опишем этот алгоритм подробнее. Пусть Ко - выпуклым многогранник. f(x) - непрерывная, выпуклая функция, определенная на Vo и достигающая на Vq своего минимума. Обозначим

m

gk {xl, Vfc, C\, m) = 4 + -^T i=i—«-

1=1

Здесь 14 - локализатор после k шагов, En(x%,Ck) - некоторый эллипсоид описанный около Vjt и т - некоторое конечное число. Итак, Vk,Ck,- приближенное значение центра тяжести тела V*. при каком-то выборе i^Qh т.

Будем считать, что вначале Еп(хд,Со) есть некоторый эллипсоид, желательно меньшего объема, описанный около тела Vq. Часто, ввиду простоты локализатора Vo, можно указать эллипсоид минимального объема. Для любого к — 0,1,2,... шаг алгоритма СММЦТ состоит в следующем.

Шаг (к+1):

1. При некотором т* вычисляем (¡к = Vk,Ck-mk)

2. Очередное отсечение проводим через точку qk■ Именно, вычисляем дн = V/(gi!) и пусть = {х € R" : (х - ¡¡ь, дк) < 0}. Для следующего локализатора Vk+\ имеем: 14+1 = ^rurj и V^+i С Еп(х%, .

3. Строим эллипсоид Еп(х_в:В) минимального объема, описанный около тела Еп[хСк) П ttJ .

4. Если: ib G

To: Полагаем Ck + i ■= B, := хв и переходим к шагу (к + 2).

Иначе: Перестраиваем эллипсоид Е„(хв,В) следующим образом. Пусть а - нормальный вектор первого из ограничений, составляющих которому не удовлетворяет точка хв- Пусть тт~(xß, а) = {х : (х — хд,а) < 0}. Тогда очевидно включение С Еп{хд^В) П 7г~(гв,о). Около полуэллипсоида Еп(хв,В) П п~(хв, л) строим минимальный описанный эллипсоид Еп(хв' ,В'). Его объем строго меньше объема эллипсоида En(xß, В). Полагаем В ~ В', Xß :— хв1 и переходим к пункту 4.

Важно отметить, что выбор на каждом шаге подходящего отображения Ск и точки имеет большое значение при проведении практических вычислений. Рассмотрим использование СММЦТ в задаче линейного оптимального быстродействия (схема применения методов отсечений в ЗОЛБ описывается ниже). Так, если принять на (k-f 1)-м шаге СММЦТ, Vk = 0,1, "2,..., что Ск = Е и х°к - произвольная внутренняя точка Vk, то полученный алгоритм оказывается крайне неэффективным. С помощью этой схемы не-удалось решить ни одной ЗОЛБ размерности выше трех. Ситуация резко меняется, если подбирать для каждого локализатора Vk отображение Ск и точку х°к по описанной ранее схеме.

Для оценок скорости сходимости методов отсечений существенна быстрота убывания объема локализатора с ростом числа проведенных итераций. Для краткости обозначим

4k{mk) = qk{x°k, Vk,Ck, rrik), к = 0,1,...

и пусть Vi+j = Vi+i(gfc(m*)), к = 0,1,... - локализатор, получаемый из локализатора VJt при проведении, на (1Н-1)-м шаге, отсечения через точку qk{m.k). В р.5 для СММЦТ доказана следующая теорема.

Теорема 1.1

Пусть N > 0 произвольное конечное число. Тогда Vi £ (0,1) существует последовательность чисел 14)}, к ~ 0,...,ЛГ — 1, такая, что если Vrrik > т'к(6, N, Vk), на (к -f 1)-м шаге СММЦТ в локализаторе Vk для проведения отсечения выбирается точка г* = <jk{тк), то после проведения N отсечений выполнено

Р(иШя*-1(ты-1))) < (1 - 1)лг ■ v(Vo)) >1-6

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

£м = ( min f(xk) — min f(x)\ /( maxf(i) — min/Yx)),

называемой часто просто точностью решения задачи минимизации, при использовании СММЦТ справедливо следствие из теоремы 1.1.

Следствие 1.1: Пусть N > 0 произвольное конечное число. Тогда \/5 € (0,1) существует последовательность чисел {т'к(6, ТУ, 14)}, = 0,..., Л'—1,такая, что если Упц > (Я. Л', на (к+1)-мшаге СММЦТ в локализаторе для проведения отсечения выбирается точка хк = (¡^{тп'к)-. то после проведения N отсечений с вероятностью более 1 — 5 выполнено

сл-^О-е"1)"/».

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

Во второй главе рассматривается применимость методов отсечений к решению задачи минимизации квазивыпуклых функций. Напомним, что функция /(г) называется квазивыпуклой, на выпуклом множестве И), если Ус £ Л множество {а: е \го : /(ж) < с} выпукло. При минимизации выпуклых дифференцируемых функции большое значение имеет возможность вычисления градиента минимизируемой функции в заданной точке. Если /(х) не дифференцируема, то можно использовать субградиент. В случае квазивыпуклости используется более обшее понятие - квазиградиент.

Определение 2.1: Квазиградиентом квазивыпуклой функции /(х) в точке жо € И, называется любой вектор У/(жо) такой, что из неравенства /(г) < /(го) следует (У/(хо), ® — жо) < 0.

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

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

елг < (иШ/иШ) 1/П

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

В §2.2 приводится оценка погрешности по функционалу в квазивыпуклом случае для СММЦТ. Полагаем, что функция ¡(х) непрерывна

на выпуклом компакте V'o- Тогда существует неубывающая функция g(r) : R+ -¥ R+ такая, что lim ^(г) = 0 и выполнено условие

г-*- О

!/(*)-/(y)l<ff(ll*-vll), Vre Ко, VS6Vo. (2)

В качестве д(г) можно взять например модуль непрерывности f{x). Доказывается следующая теорема.

Теорема 2.1: Пусть решается задача минимизации непрерывной, квазивыпуклой функции J(x) на выпуклом компакте Vo и применяется СММЦТ. Пусть d- диаметр V'o и }{х) удовлетворяет (2). Тогда V7V > О, V<5 £ (0,1) существует последовательность чисел {m'k(S, N,1^)}, к = 0,..., N, такая, что если Vm^ > т'к (J, N, V*), на (к + 1 )-м шаге СММЦТ в локализаторе 14 проводить отсечеяие через точку хк = ¡¡к(тпк), то после проведения N отсечений с вероятностью более 1 — <5 выполняется условие

min f(xk) - min j(x) <g(d-{ 1 - e^f«) 0<k<N x£Vo \ /

Отметим, что если функция f(x) удовлетворяет на множестве ]'0 условию Липшица с некоторой константой L, то можно положить д(г) = Lr. В этом случае, при указанном в теореме способе проведения отсечений, получим, что с вероятностью более 1 — S, погрешность по функционалу убывает экспоненциально с ростом числа итераций.

В третьей главе рассматривается задача ОЛБ в следующей постановке: найти управление u(i) £ U С Rr, переводящее за минимальное время Г» решение x(t) £ Rn уравнения

х = Ах + Яи, z(0) = xt

в начало координат: i(Т.) = 0. Здесь U - область управления, выпуклый многогранник, содержащий внутри себя нуль Лг, А и В вещественные матрицы с постоянными коэффициентами размерности п х п и п х г соответственно. Принцип максимума Понтрягина. в данном случае, является необходимым и достаточным условием оптимальности управления.

В случае оптимального линейного быстродействия, принцип максимума сводит задачу поиска оптимального управления к задаче определения подходящего начального значения фо для сопряженной системы ф — —А*ф, которое обеспечивает попадание траектории в начало координат. Эта задача сводится, в свою очередь, к нахождению точки минимума функции —F(p) в полупространстве D = {р £ Rn : (р,х,) < 0]. Для любой точки р £ D, F(p) удовлетворяет уравнению /(t,p) = 0, где

(

f(t,p) = {р, X, -<?((р)), Vi = - J fi{r)Bu(T,p)dT, i = 1,..., п.

о

Здесь фi(t) " решение сопряженной системы с начальным условием ф(0) = е; и - управление, отвечающее, в соответствии с принципом мак-

симума, решению ф(Ь,р), сопряженной системы, с начальным условием 0(0) р) — Р■ Минимума функция — достигает в конусе Н, = {р £ Я" : г» = 4т. (т7)} С Как уже отмечалось, такое сведение задачи поиска оптимального управления к задаче минимизации функции в конечномерном пространстве является важным достоинством принципа максимума.

Определяемая таким образом функция —F(p) оказывается однородной и квазивыпуклой, и квазиградиентом для нее в точке р £ О является вектор у(р) — х, — 4г(Р)(р). В §3.2 дается описание схемы использования методов отсечений для поиска начального значения фо- Здесь важно отметить, что задача минимизации —Р(р) в полупространстве О сводится к задаче минимизации н некотором компактном мно-

жестве V С О размерности (п — 1).

Схема выглядит следующим образом. Найдем п линейно независимых векторов образующих с искомым вектором фо неострый угол. Для этого положим

У1 = г./||г.||, Уi - » = 2, ...,п (3)

где р 1, ...,р„-а - какие-либо попарно неколлинеарные вектора из О. Поскольку не исключена линейная зависимость векторов (3), могут понадобиться вычисления Р(р) и у{р) более чем в (п — 1)-й точке.

Определив вектора (3) мы заключаем искомый вектор фо в конус К, являющийся пересечением п полупространств тг,- ~ {р 6 й" : (у, ,р) < 0}, г — 1, ...,п. Как известно, данный я-гранный конус А может быть представлен ь виде

А' = {ре Л" :р = Е А<и>> ^ > °> € г'= 1, ¿=1

Каждый вектор ц>,- определяется из системы

Поскольку существенно лишь направление вектора фо, то можно искать вектор -Фо в выпуклой оболочке точек ги,-, то есть в многограннике

V = (р € Я» : р= £ А, «/,, Л,- > 0, £ А,- = 1}.

1=1 1=1

Очевидно V можно представить в виде

V = {р € Дп : р = »1 + Е1 г,- (№1>1 - V)!), г,- > О, Е1 г, < 1}. (4) ¡=1 ¿=1

Обозначим

p(z) = +zi(w2- U'i) H----+ z,,-i(wn - Wj). • (-5)

Таким образом, задача минимизации функции —F[p) в D сводится к задаче минимизации функции —F(z) — — F{p(z)) в симплексе Vo, где

V'0 = {z£ Я"-1 : "ffzj < 1, f=l,...,n-l}.

! = 1

Очевидно — F{p(z)) непрерывна и квазивьшукла в Vo- В каждой точке zn £ И) квазиградиентом функции — F{z) является вектор с = (ci, ..., с«-!), где Ci = {wi+i - wi,y(po)), i = 1....,«- 1 и ро = p(~o).

В §3.3 исследуются вопросы сходимости при минимизации —F(z) на Vo методами отсечений. Доказывается следующая теорема. Теорема 3.1:

1-Для произвольного rj > 0 и V5 £ (0, 1) существует N[tj) > 0 такое, что V7V > iV(jj) существует последовательность чисел {mj.(6, JV, V*)}, fc = 0,..., N, такая, что если Vinj, > гп'к{<5, N, на (к + 1)-м шаге СМ-МЦТ в локализаторе Vk проводить отсечение через точку zk = то после проведения N отсечений с вероятностью более 1 — <5 выполняется условие

min (-F(zk))-mm(-F(z)) < г,

0<k<N гб^о

2. Для произвольного т] > 0 и VJ £ (0,1) существует N(г/) > 0 такое, что VN > N(rj) существует последовательность чисел {m!{.{6, N, V^)}, к = 0,..., N, такая, что если Vm^ > rn'l{S, N, Vk), на (к + 1)-м шаге СМ-МЦТ в локализаторе 14 проводить отсечение через точку Zk = <fk(mk)> то после проведения Лг отсечений с вероятностью более 1 — 6 выполняется условие

P(arg о minN(-F[zk)), Ih) < г,

где //, -множество точек минимума функции —F(z) па Vo и p(z, V) -есть кратчайшее расстояние от точки z до множества V.

Отсюда, в силу линейной связи (5), из близости, в вероятностном смысле, z*N = arg^min^ (-F(zb)) к II,, очевидно следует близость,

также в вероятностном смысле, точкnp(zj) к II«.

В §3.4 исследуется скорость сходимости предложенного алгоритма. Рассматривается задача определения для функции F(p) на множестве V, вида (4), константы Липшица. Важную роль здесь играют свойства функции F(p) в топ или иной задаче ОЛБ. Как уже отмечалось, Vp £ D,

F(p) является решением уравнения f(t,p) = 0. Отсюда, если в точке р, h(p) = -§tf{t,p)\t=F(p) Ф 0, то F(p) дифференцируема в точке р и градиент в этой точке имеет вид

Цр)

К сожалению в общем случае не удается исключить обращение h(p) в нуль на множестве V, а значит и недифференцируемость F(p). Таким образом, в общем случае мы не знаем как определить априори удовлетворяет ли F(p) условию Липшица на V. Однако при некоторых дополнительных условиях это сделать удается. Справедлива следующая лемма.

Лемма 3.4: Если размерность пространства управления г > п и rang(B)=n. то функция F{p) дифференцируема всюду в D.

В силу однородности F(p) имеем h(cp) = ch(p), Vc > 0, Vp € D. Поэтому достаточно исследовать h(p) на множестве D п ¿'„(l). При выполнении условий леммы 3.4 удастся отделить Л(р) от нуля на D П 5,(1).

Лемма 3.9: Пусть ТУТ,, где 'Г, время оптимального движения из точки г:, в начало координат. Тогда, если г > п и rang(B) — п, то

VpeDns„(i)

h(p) > с. = c(U) min 1Ы1 • inf ||В>|| ■ ехрНИН • Т) > 0. i<i<A- pe5n(i)

Здесь (/,-, i = 1,.... ¿г вершины многогранника управления U,

c[U) - ^in^mn^u.yiMIAjVIIMl) > 0

и bjj, j = 1, ....^нормали граней V смежных с вершиной 1Значение Т можно получить построив какое-либо допустимое управление переводящее х, в нуль. Но в одном частном случае можно получить оценку не содержащую Т. Обозначим г = 1,..., п собственные вектора матрицы —А* и пусть G — ..., <7П]> где ¿г,- - вектор столбец. Имеет место следующая лемма.

Лемма ЗЛО: Пусть собственные числа матрицы —Л* вещественны, различны и положительны, г > п и rang (В) = п. Тогда Vp е D Г) 5„(1)

h{p) - а = iicFp^jj • >

Отделение h(p) от нуля на множестве D П .S"n(1) позволяет доказать существование константы Липшица для F(p). В §3.4.4 доказывается следующая теорема.

Теорема 3.2: Пусть Т > Т,, г > п и гапд{В) — п. Тогда V;/ > О функция F(p) на множестве D\Bn{v) удовлетворяет условию Липшица с константой

L(v) = 2v~1C~1 •р-Г||В||ехр(||Л||Г):

где р — шах ||i'i|[ и 2?„(j/) - открытый шар радиуса г/ с центром в нуле. i<t<fc

Из теоремы следует, что, при выполнении условий г > п и гапд(В) = п! ^(р) удовлетворяет на множестве V, вида (4), условию Липшица, так как всегда найдется такое v > О, что V С D\Bn {v). В качестве v можно взять кратчайшее расстояние от начала координат до множества V. Существование константы Липшица позволяет оценить скорость сходимости по функционалу при минимизации —F(z) методами отсечений. В §3.4.5 доказывается теорема.

Теорема 3.3: Пусть г > п и rang (В) = п. Тогда при минимизации функции — F(z) на V0 с помощью СММЦТ выполнено: VjV > О и V<5 Е (0,1) существует последовательность чисел {m'k(S, N,Vk)}, к = О,..., N, такая, что если Vrn* > m'k{S,Nt Vk) на (к А- 1)-м шаге СММЦТ в локализаторе V*,. проводить отсечение через точку zk — qk(mk), то после проведения N отсечений с вероятностью более 1 — 6 выполняется условие

min (~F(zk)) - mM-F(z)) < V2L(v) • ||W||(1 -е"1)^"1)

0<k<n iev0

Здесь W — \u>2 — wi, ..., wn — где («^+1 — wj), i - 1,..., n— 1 рассматривается как вектор столбец (см.(5)).

В четвертой главе приводятся результаты численного решения ряда ЗОЛБ четырьмя различными методами. Два из них относятся к методам отсечений - это СММЦТ и метод описанных эллипсоидов (МОЭ). Два других - рекомендуемые в литературе градиентные методы с выбором шага по Болтянскому В.Г. и по Итону Дж. Каждым из рассматриваемых методов решалось свыше трех десятков различных ЗОЛБ.

Точность попадания в начало координат траектории, найденной методами отсечений, во всех задачах колеблется от Ю-5 до 10~7. Затраты времени при работе методов отсечений составляют в среднем около 3 секунд для задач в R3, 10 секунд для задач в R4 и 55 секунд для задач в Я5.

Для задач в R3, превосходство методов отсечений над градиентными методами по затратам времени, при одинаковых требованиях к точности попадания траектории в начало координат, составляет в среднем два порядка.

При переходе к Я'1 и R5 сходимость градиентных методов стала еще более медленной и в большинстве представленных задач пришлось ограничить время работы этих методов разумной величиной (от одного часа до трех). По достижении установленных ограничений, во всех упомянутых задачах, градиентными методами не было получено сколь-нибудь приемлемой точности решения. В некоторых задачах ограничение на время работы градиентных методов увеличивалось до 11 часов, но это не приводило к ощутимому улучшению результатов. Поэтому есть все основания считать, что реальное превосходство методов отсечений по затратам времени, при размерности задачи более трех, в среднем не меньше трех-четырех порядков.

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

Сравнение всех рассматриваемых методов проводилось на задачах, большинство из которых построены случайным образом. Схема построения ЗОЛБ описана в §4.1. При этом, все рассмотренные задачи удовлетворяют следующим общим ограничениям.

1. Матрица А устойчива.

2. и е и С Rr, X G Rn, где г= 1,2,3 и п = 3,4,5.

3. Выполнено условие общности положения.

Результаты решения задач ОЛБ каждым из методов приводятся в приложении 1 в табличной форме и подтверждают высокую эффективность применения методов отсечений для решения ЗОЛБ в сравнении с рекомендовавшимися ранее градиентными методами. Кроме того, с ростом размерности задачи заметно возрастает превосходство СМ-МЦТ над МОЭ по числу проводимых итераций и составляет, в среднем, 1.5 раза в Я3 . 2 раза в R4 и 3 раза в -R5. При переходе к ЗОЛБ с переменными коэффициентами существенно увеличится стоимость вычисления квазиградиента функции —F(p), поэтому более предпочтительным, по-видимому, станет использование СММЦТ в сравнении с МОЭ.

Список публикаций по теме диссертации.

1. Бузинов A.A., Решение задачи оптимального линейного быстродействия методами центрированных отсечений. // "Современные проблемы математики и информатики", Сб. науч. тр. молодых ученых, студ. и аспирантов., Вып. 2, стр. 41-46, Ярославль 1999г.

2. Бузинов A.A., Методы отсечений в задаче оптимального линейного

быстродействия. // "Современные проблемы естествознания", Сб. те-

зис. обл. науч. конф. студ. аспирантов и молодых ученых., стр. 41-43,

Ярославль 1999г.

Введение

Глава 1. Стохастический алгоритм выпуклого программирования

1.1 Локальные методы математического программирования

1.2 Приближенное вычисление интегралов в пространствах большой размерности.

1.3 Повышение эффективности методов приближенного вычисления интегралов.

1.4 Приближенное вычисление центра тяжести выпуклого многогранника в Вп.

1.5 Алгоритм минимизации выпуклых функций

Глава 2. О минимизации квазивыпуклых функций

2.1 Квазиградиент квазивыпуклой функции.

2.2 Методы отсечений в квазивыпуклой оптимизации

Глава 3. Решение задачи оптимального линейного быстродействия методами отсечений

3.1 Постановка задачи оптимального линейного быстродействия

3.2 Алгоритм решения задачи оптимального линейного быстродействия методами отсечений.

3.3 Сходимость

3.4 Оценка скорости сходимости.

3.4.1 О дифференцируемости функции Р(р)

3.4.2 Вспомогательные утверждения.

3.4.3 Оценка снизу для функции Н(р).

3.4.4 Определение константы Липшица для функции F(p).

3.4.5 Теорема о скорости сходимости.

Глава 4. Численные решения задач оптимального линейного быстродействия

4.1 Характеристики рассматриваемых задач ОЛБ

4.2 Рассматриваемые методы решения задач ОЛБ.

4.3 Результаты численного решения задач ОЛВ.

4.4 Примеры решенных задач ОЛБ.

4.4.1 Задачи в В?.

4.4.2 Задачи в Я

4.4.3 Задачи в Я5 . .-.

4.5 Обсуждение результатов.

В двадцатом веке одним из наиболее важных разделов математики стала теория оптимального управления. Безусловно это связано, в первую очередь, с бурным развитием техники. С появлением сложных технических устроийств возникла необходимость эфективно управлять их функционированием и взаимодействием. Важным шагом в развитии теории оптимального управления стал метод динамического программирования [1] впервые предложенный Беллманом. Несмотря на наличие ряда существенных недостатков, выраженных в наложении заведомо невыполнимых условий на рассматриваемые функции, этот метод послужил отправной точкой для возникновения принципа максимума Понтрягина. Принцип максимума вначале был доказан для линейных управляемых систем и лишь после распространен на системы более общего вида. Теория принципа максимума полно отражена в работах Понтрягина Л.С., Болтянского В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. [2],[3],[4], Иоффе А.Д., Тихомирова В.М., Алексеева В.М., Фомина С.В.[5],[6]. Однако, при всей значимости,принцип максимума не дает эффективного алгоритма численного синтеза оптимального управления, даже для такого основательно изученного вопроса, как задача линейного оптимального быстродействия (30ЛБ), применительно к которой принцип максимума является не только необходимым, но и достаточным условием оптимальности. Решение ЗОЛБ сводится при помощи принципа максимума к рассмотрению конечномерной задачи определения подходящего начального значения для сопряженной системы ф = —А*ф. Это безусловно важно, но вместе с тем, длительное время отсутствовали по-настоящему эффективные подходы к численному решению данной конечномерной задачи.

С появлением принципа максимума были предложены подходы к численному синтезу оптимального управления связанные с градиентным спуском. У истоков методов такого характера стоят Нейштадт и Итон [7],[8]. Изложение аналогичных подходов к решению задачи синтеза оптимального управления можно найти в работах других авторов [9],[10],[11]. К сожалению, сходимость таких методов оказывается, в большинстве случаев, очень медленной. В результате, в последнее время, на практике все чаще применяются иные методы, не связанные с принципом максимума Понтрягина. Такие методы называются прямыми [12].

Одним из разделов математики, где в последние десятилетия также произошли важные изменения, является выпуклое и квазивыпуклое программирование. Важным шагом в развитии математического выпуклого и квазивыпуклого программирования стало построение алгоритмов оптимальных по порядку числа итераций. Эти алгоритмы относятся к так называемым методам отсечений. Существенное влияние на формирование и развитие этих методов оказали работы следующих авторов: Левин А.Ю. [13],Шор Н.З. [14],[15], Немировский A.C., Юдин Д.Б. [16], [17], [18], [19], [20], Хачиян Л.Г.,Эрлих И.И., Тарасов С.П. [21],[22],[23].

В связи со сказанным, большое значение приобретает факт тесной связи между теорией оптимального управления и математическим квазивыпуклым программированием. Именно, еще четветь века назад, в работе [24], Левиным А.Ю. впервые была отмечена возможность применения методов отсечений к определению начального значения фо для сопряженной системы в задаче оптимального линейного быстродействия. Впоследствии, уточнялись и совершенствовались отдельные аспекты алгоритма - отделение нулей квазиполиномов в связи с определением точек переключения [25] и т.п. Но тот факт, что в течение столь длительного времени данная идея не была реализована в виде эффективного вычислительного алгоритма, связан с тем, что на этом пути необходимо преодолеть ряд существенных трудностей, что и определяет содержание настоящей работы. Можно отметить, что при построении таких алгоритмов весьма полезными могут оказаться такие стохастические приемы как биллиардные траектории, марковские блуждания и другие [26],[27].

Цели настоящей работы сформулируем следующим образом.

1) Разработать эффективный численный алгоритм синтеза оптимального управления для ЗОЛБ, основанный на сочетании принципа максимума Понтрягина и центрированных отсечений. Сравнить эффективность алгоритмов использующих идею отсечений и алгоритмов основанных на использовании градиентных методов.

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

Первая глава посвящена рассмотрению вопросов приближенного вычисления интегралов и выпуклого математического программирования, необходимых в дальнейшем. В рамках общей схемы методов отсечений [23], строится метод минимизации выпуклых функций основанный на стохастическом правиле выбора точки в текущем локализаторе. Это правило заключается в приближенном определении центра тяжести </ выпуклого тела V, каковым и является каждый локализатор.

Как известно справедливо равенство

Я.~! хАх/ J йх. к v

Для вычисления интегралов в числителе и знаменателе предлагается использовать специальную версию метода Монте-Карло. Обозначим: 5,1(1) - единичная сфера в Яп и |5П(1)| - ее (п — 1)-мерный объем, хо -некоторая внутренняя точка выпуклого тела V, /и(У) - объем тела V и для любого у 5П( 1) у) - расстояние от точки хо до границы тела V в направлении у. В 1.2 доказывается следующая лемма.

Лемма 1.3: Пусть /(.т) 6 £1,^2, ••• - последовательность независимых реализаций случайного вектора £ равномерно распределенного на 5,1(1) и С : Вп —» Вп невырожденное аффинное преобразование. Тогда, при т —> со, имеет место соотношение

1' '|5П(1)| Е / Д*0 + ^ / Кх)ах т ¿=1 v

Статистика, стоящая слева, является несмещенной оценкой для интеграла справа. Далее в 1.3 показано, что данная статистика обладает определенными преимуществами (касающимися оценки дисперсии) при условии, что эллипсоид Еп{х§,С) = {ж : х = х$ + Сг, \\г\\ < 1} является минимальным описанным эллипсоидом для выпуклого тела V.

В 1.4 доказывается следующая лемма.

Лемма 1.6: Пусть ••• - последовательность независимых реализаций случайного вектора равномерно распределенной на ¿'„(1), и С - невырожденное аффинное преобразование. Тогда п 1сь.р»+\х0,ъстШп+1 пя х0 -\--—ш--'-4 д, (ш оо) (1) п + 1 ер-(«о,^с6)/||с6||1

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

На основе соотношения (1) в 1.5 предлагается метод минимизации выпуклых функций, относящийся к классу методов отсечений. Этот метод сочетает использование соотношения (1) для приближенного вычисления центра тяжести текущего локализатора У с подбором для данного локализатора отображения С и точки xq G У таким образом, чтобы эли-псоид Еп(хо,С), описываемый около тела V, имел по-возможности меньший объем. Полученная схема названа стохастической модификацией метода центров тяжести (СММЦТ).

Опишем СММЦТ подробнее. Пусть Vq - выпуклый многогранник, f(x) - непрерывная, выпуклая функция на достигающая на Vq своего минимума. Обозначим п „ .2 ад - Pn+l(*l Vbод/иедг1 п + 1 1

Здесь Ук - локализатор после к шагов, Еп(хк,Ск) - эллипсоид описанный около Ук и х\ £ Ук, т- некоторое конечное число. То есть, ¿¡к(хк, Ук, Ск, т) - приближенное значение центра тяжести тела Ук при каком-то выборе х°к, Ск и т.

Считаем, что вначале Еп(х^С$) есть некоторый эллипсоид, желательно меньшего объема, содержащий в себе тело Уо- Часто, ввиду простоты локализатора Рд, можно указать описанный эллипсоид минимального объема. Для любого к = 0,1, 2,. шаг СММЦТ состоит в следующем.

Шаг (к+1):

1. При некотором тк вычисляем = с[к(хк, Ук,Ск, тк)

2. Очередное отсечение проводим через точку (¡к. Именно, вычисляем дк = и пусть пк = {х £ Яп : [х — дк^дк) < 0}. Для следующего локализатора Т4+1 имеем: Ук+\ = Ук П тгк и Ук+1 С Еп(х°к,Ск) П тск.

3. Строим эллипсоид Еп(хв-,В) минимального объема, описанный около тела Еп(х°к, Ск) П кк [20].

4. Если: хв € Ук+1

То: Полагаем Ск+\ '•= В, хк+1 := хв и переходим к следующему шагу.

Иначе: Перестраиваем эллипсоид Еп(хв, В) следующим образом. Пусть а - нормальный вектор первого из ограничений, составляющих

Vjt+ъ которому не удовлетворяет точка хв. Пусть тг~(хВ:а) = {х £ Rn : (х — хв,а) < 0}. Тогда очевидно включение Т^+i С Еп{хв,В) П тг~(хв,а). Около полуэллипсоида Еп(хв,В) П -к~~{хв,а) строим минимальный описанный эллипсоид Еп{хв>,В') [20],[23]. Его объем строго меньше объема эллипсоида Еп(хв, В). Полагаем В := В', хв := хв> и переходим к пункту 4.

Важно отметить, что выбор на каждом шаге подходящего отображения Ck и точки имеет большое значение при проведении практических вычислений. Рассмотрим использование СММЦТ в задаче линейного оптимального быстродействия (схема применения методов отсечений в 30JIB описана ниже). Если принять на (к + 1)-м шаге СММЦТ, \/к — 0,1,., что Ck — Е и х\ - произвольная внутренняя точка Т4? то полученный метод оказывается крайне неэффективным. С помощью этой схемы не удалось решить ни одной ЗОЛБ размерности выше трех. Ситуация резко меняется, если подбирать для каждого локализатора V* отображение Ck и точку х\ по описанной ранее схеме.

Для оценок скорости сходимости методов отсечений существенна быстроты убывания объема локализатора с ростом числа проведенных итераций. Для краткости обозначим

Чк(™>к) = qk{xl,Vk,Ck,mk), к = 0,1,. и пусть Vfc+i = к = 0,1,. - локализатор, получаемый из локализатора \4 при проведении, на (к+1)-м шаге, отсечения через точку Чк{п1к)- В 1.5 для СММЦТ доказана следующая теорема.

Теорема 1.1: Пусть N - натуральное число. Тогда для любого S G (0,1) существует последовательность чисел {m'k{8, V^)}, к = 0,JV—1 такая, что если при га& > m'fc(J, Т4)? на + 1)~м шаге СММЦТ в лока-лизаторе V* для проведения отсечения выбирается точка = Qfc(mjt), то после проведения N отсечений выполнено

P(KMÜN-i(mN-i))) < (1 - е-1)^ • ц(Уо)) >1-5.

Для относительной погрешности по функционалу после проведения N отсечений n = { min f(xk)—minf(x))/(m&xf(x)—mmf(x)), называемой часто просто точностью решения задачи минимизации, при использовании СММЦТ справедливо следствие из теоремы 1.1.

Следствие 1.1: Пусть N - натуральное число. Тогда для любого S Е (0,1) существует последовательность чисел {т'к(5, Т4)}, к = О,., JV —1 такая, что если при т* > m'fc(tf,Vfc), на (к+1)-м шаге СММЦТ в локали-заторе Т4 для проведения отсечения выбирается точка жд. = q^г(т*), то после проведения iV отсечений выполнено

Р(е* < (1 - е-1)"/") >1-5.

Во второй главе рассматривается применимость методов отсечений к решению более общей задачи минимизации квазивыпуклых функций. При минимизации выпуклых дифференцируемых функций большое значение имеет возможность вычисления градиента V/(x) минимизируемой функции в заданной точке. Если f(x) не дифференцируема, то можно использовать субградиент. В случае квазивыпуклости используется более общее понятие - квазиградиент [28].

Определение 2.1: Квазиградиентом квазивыпуклой функции f(x) в точке .z'o Е V называется любой вектор Vf(xо) такой, что из неравенства /(.г) < /(.х0) следует (Vf(x0),ж - ж0) < 0.

Очевидно, что если f(x) дифференцируема в точке х0, то можно положить Vf(xo) — Vf(xo). Однако в общем случае, нахождение квазиградиента может представлять собой самостоятельную задачу не сводящуюся к нахождению градиента. Возможные осложнения, связанные с этим, мы здесь не рассматриваем, поскольку при решении задачи оптимального линейного быстродействия они не возникают.

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

EN < МК)М"^о))1/п где п -размерность пространства. Для квазивыпуклых функций эта оценкг не верна. Оценки трудоемкости некоторых методов отсечений для квазивыпуклого случая рассматривались в [19], [28].

В 2.2 приводится оценка погрешности по функционалу в квазивыпуклом случае для СММЦТ. Полагаем, что функция f(x) непрерывна на компакте У0. Тогда существует неубывающая функция g(r) : R+ -> R+ такая, что limg(r) = 0 и выполнено условие

If(x) - f(y)I < д(\\х - у||), Va: G F0, Vy G V0. (2)

В качестве g(r) можно взять, например, модуль непрерывности f(x).

Теорема 2.1: Пусть решается задача минимизации непрерывной квазивыпуклой функции f(x) на выпуклом компакте Vo С Rn и применяется СММЦТ. Пусть d - диаметр Vo и f(x) удовлетворяет (2). Тогда для любого натурального N и любого 5 Е (0,1) существует последовательность чисел {тп'к(6,14)}, к = 0,., N— 1 такая, что если при т^ > rnj.(5, Т4), на (к + 1)-м шаге СММЦТ в локализаторе 14 проводить отсечение через точку Xk = (¡к{тпк), то после проведения N отсечений с вероятностью более 1 — 5 выполняется условие min f(xk) - min f(x) < g(d ■ (1 - e"1)^") 0<k<N—l ' x£V0JK ' ~. V V J '

Отметим, что если функция f(x) удовлетворяет на множестве Vo условию Липшица с некоторой константой L, то можно положить д(г) = = Lr. В этом случае, при указанном в теореме способе проведения отсечений, получим, что с вероятностью более 1 — 5 погрешность по функционалу убывает экспоненциально с ростом числа итераций.

В третьей главе рассматривается задача ОЛБ в следующей постановке: найти управление u(t) £ U С Rr, переводящее за минимальное время Т* решение х(t) £ Rn уравнения х = Ах + Ви, гс(0) = ж*. в начало координат: ж(Т*) = 0. Здесь U - область управления, выпуклый многогранник, содержащий внутри себя нуль Rr, А п В вещественные матрицы с постоянными коэфициентами размерности n х п и п х г соответственно. Принцип максимума Понтрягина, в данном случае, является необходимым и достаточным условием оптимальности управления. Для задачи оптимального быстродействия в общем виде принцип максимума формулируется следующим образом [3].

Пусть рассматривается управляемый объект, движение которого описывается системой уравнений в векторной форме

А) х = /(х, и) х eRn,ueU.

Допустимым управлением считается произвольная кусочно-непрерывная функция u(t) = ur(t)) со значениями в U, непрерывная справа б точках разрыва и непрерывная в концах отрезка, на котором она определена. Далее, в фазовом пространстве заданы две точки яо, - начальное и конечное фазовые состояния. Наконец рассматривается некоторый процесс (и(Ь), t £ [¿0^1] преводящий объект из состояния в состояние Х\; это означает, что х(£) есть решение системы (А) соответствующее допустимому управлению и{£) и удовлетворяющее начальному и конечному условиям: ^(¿о) = #0; #(¿1) = х\- Таким образом,, рассматриваемый процесс затрачивает на переход из х$ в врем,я — ¿о- Процесс называется опт,ималъиым в смысле быстродействия, если не существует процесса переводящего объект из жо в х\ за меньшее время.

Введем в рассмотрение функцию Н зависящую от переменных х = = (ж1,., :сп), и = (и1,.",О; Ф = {Ф\,-,Фп)п

B) Н{ф,х,и) =ф}(х,и) = £ фг^{х,и).

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

C) , = !,.,». где ж(£)) рассматриваемый процесс.

Для оптимальности процесса необходимо существование такого нетривиального решения ?/>(£), t Е [¿0^1] системы {С), что для, любого момента г £ [¿0-^1] выполнено условие максимума

В) В(ф(т),х(т),и(т))=шахЩф(т),х(т),и), иьи а в конечный момент времени ¿1 выполнено условие

Е) Н{ф{11),х{11),и{11))> 0.

Для линейных управляемых систем принцип максимума значительно упрощается. В этом случае имеем:

1. Н(ф, х, м) = фАх + фВи.

2. Система уравнений (С) принимает вид ф = —А*ф.

3. Соотношение (Р) принимает вид ф{т)Ви(т) = тахф(т)Ви.

4. Соотношение (Е) просто не нужно, так как для линейных систем выполнено всегда.

В случае оптимального линейного быстродействия, принцип максимума сводит задачу поиска оптимального управления к задаче определения подходящего начального значения фо для системы (С), которое обеспечивает попадание траектории в начало координат [2],[3]. В случае линейных систем эта задача сводится, в свою очередь, к нахождению точки минимума функции —Р(р) в полупространстве I? = {р £ Лп : (р,х+) < 0}. Для любой точки р 6 -О, момент £ = -Р(р) является единственным корнем уравнения f(t,p) = 0, £ > 0, где f{t,p) = (p,x*-&(p)), й = - / ф{(т)Ви{т,р)<1т, г = 1,., п. о

Здесь - решение системы (С) с начальным условием ф(0) = ег- и и(1,р) - управление, отвечающее, в соответствии с (Б), решению ф(Ь,р) системы (С) с начальным условием ф(0,р) = р. Минимума функция — ^(р) достигает в конусе Н* = {р £ Л" : ж* = £г„(р)} С -О [3]. Такое сведение задачи поиска оптимального управления к задаче минимизации функции в конечномерном пространстве является важным достоинством принципа максимума.

Определяемая таким образом функция —Р(р) оказывается непрерывной, квазивыпуклой [28] и квазиградиентом для нее в точке р £ £) является вектор у{р) = ж* — В 3.2 дается описание схемы использования методов отсечений для поиска начального значения Важно отметить, что задача минимизации —Р(р) в полупространстве И сводится к задаче минимизации —Р(р) в некотором компактном множестве V С О размерности (п — 1).

Поступаем следующим образом [24]. Найдем п линейно независимых векторов образующих с искомым вектором фо неострый угол. Для этого положим аг, у(рг-1) . 9 . V

У1 — и II ■> У г — И / \||! 1 — 72. ^о]

1М 11У (Рг—1)|| где Р1,.,Рп-1 - какие-либо попарно неколлинеарные вектора из Б. Поскольку не исключена линейная зависимость векторов (3), могут понадобиться вычисления Р{р) и у(р) более чем вп-1 точках.

Определив вектора (3) мы заключаем вектор ф§ в конус К являющийся пересечением п полупространств 7гг- = {р £ В.п : (уг,р) < 0}, г = 1 , .,п. Как известно, данный п-гранный конус К может быть представлен в виде

К = {р е Яп : р = Е Ат, Хг > 0, гиг £ Я", г = 1,п}. 1

Каждый вектор ги^ определяется из системы

Пу^щ) = О j ф г. г1 = 1 (у,-,ги,-) =-1

Поскольку существенно лишь направление вектора то можно искать вектор фо в выпуклой оболочке точек гиг-, то есть в многограннике

V = {р е Яп : р = Е Л,-«;,-, Л,- > О, Е А; = 1}. г=1 г=1

Очевидно У можно представить в виде

У = {р е Яп : р = ил + "Ё1 - гиО, г,- > 0, "е г,- < 1}. (4) г=1 ¿=1

Обозначим р(г) = ги] + ¿1(^2 — гох) Ч-----Ь 2п-1(ги„ - «п). (5)

Таким образом, задача минимизации функции —Р(р) в В сводится к задаче минимизации функции = —Р(р(г)) в симплексе где

И) = {г е Л"-1 : "Ё1 2,- < 1, >0, г = 1,п - 1}. г=1

Функция —Г(р(г)) непрерывна и квазивыпукла в Уц. В каждой точке ¿о Е Уо квазиградиентом функции — -Р(г) является вектор с = (сх,., с„1), где с,- = - №Ь у(ро)), г = 1, •», п - 1 и р0 =

В 3.3 исследуются вопросы сходимости при минимизации —Р(г) методами отсечений. Рассматривается сходимость СММЦТ при минимизации функции —Ё(г). Доказывается следующая теорема.

Теорема 3.1: 1. Для любых г] > 0 и 6 £ (0,1) найдется N(71) > 0 такое, что для любого N > N{7]) существует последовательность чисел {771^(5, Т4)}, к = 0,., N — 1 такая, что если при > т'к(5, Т4) на (А; + 1)-м шаге СММЦТ в локализаторе 14 проводить отсечение через точку Zk = = Чк(тк), то после проведения N отсечений с вероятностью более 1 — 8 выполняется условие min (-F(zk)) - min(-F(z)) < ri.

2. Для любых г] > 0 и 5 Е (0,1) найдется N(rj) > 0 такое, что для любого N > N(rf) существует последовательность чисел Т4)}, к = 0,., iV —1 такая, что если при тк > Т4) на (&+1)-м шаге СММЦТ в локализаторе 14 проводить отсечение через точку = то после проведения 7V отсечений с вероятностью более 1 — 5 выполняется условие

Marg^mm^l-F^)),^) < »у, где ii* - множество точек минимума функции —F[z) на Fo и У) - есть кратчайшее расстояние от точки 2 до множества V.

Отсюда, в силу линейной связи (5), из близости, в вероятностном смысле, z*N = arg min (-F(zk)) к H*, очевидно следует близость, также

0<fc< N— 1 в вероятностном смысле, точки p(z*N) к üT*.

В 3.4 исследуется скорость сходимости предложенного метода. Рассматривается задача определения для функции F(p) на множестве V вида (4) константы Липшица. Важную роль здесь играют свойства функции F(p) в той или иной задаче ОЛВ. Как уже отмечалось, \/р £ D F(p) является решением уравнения = 0. Отсюда, если в точке р h[p) = -§if{t:p)\t=F(p) Ф 0, то F{p) дифференцируема в точке р и градиент в этой точке имеет вид [3]

VF(p) =

Чр)

В общем случае не удалось исключить обращение h(p) в нуль на множестве V, а значит и недифференцируемость F(p). Таким образом, в общем случае неясно, как определить априори удовлетворяет ли F(p) условию Липшица на V. Однако при некоторых дополнительных условиях это сделать удается. Справедлива следующая лемма.

Лемма 3.4: Если размерность пространства управления г > п и rang(B)=n, то функция F(p) дифференцируема всюду в D.

В силу однородности F(p) имеем h(cp) = ch(p), Vc > 0, Vp € D. Поэтому достаточно исследовать h(p) на множестве D п 5п(1). При выполнении условий леммы 3.4 удается отделить h(p) от.нуля на D(1 Sn( 1).

Лемма 3.9: Пусть Т > Т+, где Т* время оптимального движения из точки х* в начало координат. Тогда, если г > п и гапд(В) = п, то

-Л(р) > С. = шш Ц^г'Ц • р \\В*р\\ • ехр(-||А|| • Т) > 0. Здесь г!г-, г = 1,А; вершины многогранника управления £У, с(Е7) = тт тт КУ1Ы1, Ьу/ИМ) > 0 и Ьц, ] = нормали граней II смежных с вершиной г>г-. Значение

Т можно получить построив какое-либо допустимое управление переводящее ж* в нуль. Но в одном частном случае можно получить оценку не содержащую Т. Обозначим г = 1 ,.,п собственные вектора матрицы —Л* и пусть (5 = [<7х,., <7„], где д{ -вектор столбец. Имеет место следующая лемма.

Лемма 3.10: Пусть собственные числа матрицы —А* вещественны, различны и положительны, г > п и гапд(В) = п Тогда \/р 6 Т) П 5П(1)

Цр) - С = ОёПсРй' »"'»А,>

Отделение Н(р) от нуля на множестве И П 5„( 1) позволяет доказать существование константы Липшица для Р(р). В 3.4.4 доказывается следующая теорема.

Теорема 3.2: Пусть Т > Т*, г > п и гапд(В) = п. Тогда \/у > 0 функция F(p) на множестве В\Вп(и) удовлетворяет условию Липшица с константой ь{у) = 2у~1с:х • рТ • ||В|| ехр(||А|| • Г), (6) где р = тах ||г?г|| и Вп{у) - открытый шар радиуса V с центром в нуле.

1 < г < Аг

Из теоремы следует, что -Р(р) удовлетворяет на множестве V вида (4) условию Липшица, так как всегда найдется такое и > 0, что выполнено V С 0\Вп(г/). В качестве и можно взять, например, кратчайшее расстояние от начала координат до множества V. Существование константы Липшица позволяет оценить скорость сходимости по функционалу при минимизации —В"[г) методами отсечений. В 3.4.5 доказывается соответствующая теорема для СММЦТ.

Теорема 3.3: Пусть г > п и гапд(В) = п. Тогда при минимизации функции -^(2) на Уо с помощью СММЦТ выполнено: для любого натурального N и любого 5 6 (0,1) существует последовательность чисел {"^.(¿1,14)}, к = 0, — 1 такая, что если при т* > т'к(5, Т4) на (к + 1)-м шаге СММЦТ в локализаторе Т4 проводить отсечение через точку гк = <1к{™>к)-> то после проведения N отсечений с вероятностью более 1 — 5 выполняется условие

Здесь \¥ = [и)2 — и) 1,гип — м^х], где (гиг-+1 — н^), г = 1,п — 1 рассматривается как вектор столбец (см.(5)).

В четвертой главе приводятся результаты численного решения ряда ЗОЛБ четырмя различными методами. Два из них относятся к методам отсечений - это СММЦТ и метод описанных эллипсоидов. Два других - рекомендуемые в литературе градиентные методы с выбором шага по Болтянскому В.Г. и по Итону Дж. [3]. Каждым из рассматриваемых методов решалось пять десятков различных ЗОЛБ. При этом наблюдается значительное превосходство методов отсечений над градиентными методами, как по времени работы, так и по точности получаемых решений. Подробное обсуждение результатов проводится в 4.5.

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

1. Матрица А устойчива.

2. иеи СЯГ,Х е Я", где г = 1,2,3 и п = 3,4,5.

3. Выполнено условие общности положения.

Результаты решения задач ОЛБ каждым из методов приводятся в приложении 1 в табличной форме и подтверждают высокую эффективность применения методов отсечений для решения ЗОЛБ в сравнении с рекомендовавшимися ранее градиентными методами.

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

1.1 Локальные методы, математического программирования

Рассмотрим задачу математического программирования в следующей форме. Найти минимум выпуклой функции /(ж), п вещественных переменных, в выпуклом многограннике У, заданном уравнениями своих граней: f(x) min, при х е V С Rn.

Здесь будут рассматриваться лишь локальные методы математического программирования первого порядка. Как известно [23], эти методы укладываются в следующую общую итеративную схему:

1. С помощью некоторого правила Pq выбираем в множестве V точку xq. Вычисляем в точке xq значение функции и ее градиент:

Ы,у/Ы) Ы

2.С помощью некоторого правила Рь используя информацию (г'о), выбираем точку х\ £ V и вычисляем: i),v/(®i)) Ы к-Ь1). С помощью некоторого правила Рк, используя информацию выбираем точку Xk £ V и вычисляем: f(xk),Vf(xk)) (ik)

После некоторого конечного числа шагов N останавливаемся и объявляем приближенным решением ждг задачи наилучшую, по значению функции, полученную точку, то есть хм = arg min f(xk)

Основной мерой точности решения рассматриваемой задачи является относительная погрешность [16],[43] f{xN)-mmf(x) eN = e(xN) = xev max/(z)-min/(x) x£V xhv называемая часто просто точностью решения. Теоретически известно [23], что для гарантированного достижения заданной точности е £ [0,1], на любой задаче математического программирования, даже лучшему из локальных методов потребуется не менее N(e) = nlog(l/e) итераций. Доказано, что для любого локального метода решения выпуклой задачи математического программирования при е < 1/2 имеет место оценка

N(e) > с- nlog(l/e) где с константа порядка единицы.

В настоящее время наиболее эффективными из локальных методов выпуклого математического программирования первого порядка являются так называемые методы отсечений, основанные на использовании неравенства f(x)>f(xk) + (Vf(:xk),x-xk) верного для любой выпуклой функции /(ж). Из этого неравенства, как известно, вытекает принадлежность точки минимума /(ж) полупространству 7Г~ = {ж £ Rn : (Vf(xk),x — Xk) < 0} и, таким образом, точки лежащие в полупространстве 7Г+ = {ж £ Rn : (У/(ж&),ж — Xk) > 0} можно в дальнейшем не рассматривать.

В соответствии с общей схемой локальных методов математиче^ ского программирования, на (А; + 1)-м шаге метода отсечений, по полученной на предыдущих шагах информации определяется текущий локализатор Т4 области нахождения минимума /(ж), который получается из исходного множества Vo в результате накопленных отсечений:

Vk = {xeVQ: (У/(жг), ж - Xi) < 0, 1 = 0,к - 1}

Затем, используя некоторое правило Р выбирается точка Xk £ Vf. в которой вычисляется информация После этого происходит переход к следующему отсечению (если необходимо). Конкретный метод отсечений определяется выбором правила Р.

Обозначим fi объем локализатора степени однородности 5 и е^ точность решения задачи после проведения N итераций. Для методов отсечений известна важная оценка [21], [23] позволяющая оценивать скорость сходимости методов отсечений с помощью оценок быстроты убывания объема локализатора.

Известны различные версии метода отсечений с детерминированным правилом Р выбора точки в текущем локализаторе, обеспечивающие экспоненциальное убывание объемов локализаторов, то есть выполнение неравенства i(Vfc) < Л • MVfc-i), А € (0,1), Vfc > 0. (8)

Таковыми являются: метод описанных эллипсоидов [23],[16],[15], метод симплексов [20], метод вписанных эллипсоидов [21], метод центров тяжести [13]. Для двух последних методов можно указать абсолютные значения величины Л не зависящие от размерности п пространства. Для метода вписанных эллипсоидов Л = 0.843, для метода центров тяжести Л = 0.632. Кроме того, эти два метода являются оптимальными, по порядку числа итераций локальными методами. Имеют место следующие оценки числа итераций, гарантирующих достижение заданной точности е: Nie) < 4.6 • nlog(l/e) для метода вписанных эллипсоидов (МВЭ) и Nie) < 1.6 • nlog(l/e) для метода центров тяжести (МЦТ).

Итерация МВЭ обладает полиномиальной вычислительной сложностью, а именно t = 0(n4-log(n)) [20]. В то же время, для МЦТ неизвестны детерминированные методы выполнения итерации, обладающие полиномиальной вычислительной сложностью. Более того, известно [23], что задача вычисления точного центра тяжести такого многогранника, как j Х{ е [0,1] г = 1,., п \(а,х)<Ь а = (а i,.,an) является iVP-трудной. Но более внимательный анализ МЦТ показывает, что для оптимальности метода по числу итераций достаточно вычислять центр тяжести приближенно [23]. Это наводит на мысль о поиске локальных методов первого порядка с недетерминированным правилом Р выбора точки в текущем локализаторе. Ниже предлагается алгоритм, где в качестве правила Р выступает стохастический метод приближенного вычисления центра тяжести выпуклого тела.

Заключение

Итоги проделанной работы состоят в следующем.

1. Предложен и обоснован стохастический метод минимизации выпуклых и квазивыпуклых функций, названный стохастической модификацией метода центров тяжести (СММЦТ).

2. Реализован эффективный алгоритм численного решения ЗОЛБ с постоянными коэффициентами, основанный на сочетании принципа максимума Понтрягина и центрированных отсечений.

3. Определены условия существования и получено выражение константы Липшица для функции — Р(р). Наличие константы Липшица позволяет получить более точную информацию о числе итераций требуемых для решения ЗОЛБ предложенным методом.

4. Проведено сравнение эффективности реализованного алгоритма решения ЗОЛБ с рекомендуемыми в литературе градиентными методами решения ЗОЛБ. Выявлено значительное преимущество применения методов отсечений (в различных версиях) над методами градиентного спуска и подтверждена практически высокая эффективность СММЦТ.

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

Автор выражает благодарность профессору Левину А.Ю.

1. Беллман Р. Динамическое программирование. М.: ИЛ, 1963.

2. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: ФМ, 1961.

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

4. Гамкрелидзе Р.В. Теория оптимальных по быстродействию процессов в линейных системах. Изв. АН СССР, 1958. Т.22, №4. С. 449-474.

5. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1974.

6. Алексеев В.М., Тихомиров В.М., Фомин C.B. Оптимальное управление. М.: Наука, 1979.

7. Neustadt L.W. Synthesizing time optimal control systems, J. Math. Anal, and Appl., 1960, V.l.,N3-4,p.484-493.

8. Eaton J.H. An iterative solution to time-optimal control, J. Math. Anal, and Appl.,1962, V.5.,N2, p.329-244.

9. Ли Э.Б., Маркус Л. Основы теории оптимального управления. М.: Наука, 1972.

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

11. Моисеев H.H. Численные методы в теории оптимальных систем. М.: Наука, 1971.

12. Габасов Р., Кириллова Ф.М. Конструктивные методы оптимизации. "Задачи управления", Минск, Изд-во "Университетское" 1984 г. 207 с.

13. Левин А.Ю. Об одном алгоритме минимизации выпуклой функции // ДАН СССР, 160. №6, 1965. С. 1241-1243.

14. Шор Н.З. Использование операции растяжения пространства в задачах минимизации выпуклых функций // Кибернетика, №1, 1970.

15. Шор Н.З. Метод отсечения с растяжением пространства для решения задачи выпуклого программирования // Кибернетика, 1977, №1, С. 94-95.

16. Немировский A.C., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.

17. Юдин Д.Б., Немировский A.C. Информационная сложность и эффективные методы решения выпуклых экстремальных задач Экономика и математические методы. 1976, Т. 12. Вып. 2. С. 357-369.

18. Немировский A.C., Юдин Д.Б. Информационная сложность математического программирования// Техническая кибернетика, 1983. №1, С. 88-117.

19. Юдин Д.Б. Математическое программирование в порядковых шкалах// Изв. АН СССР, TIC, 1984, №2. С. 3-17.

20. Юдин Д.Б. Вычислительные методы теории принятия решений. М.: Наука, 1989.

21. Тарасов С.П., Хачиян Л.Г., Эрлих И.И. Метод вписанных эллипсоидов // ДАН СССР, 1988. Т. 298. С. 1081-1085.

22. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМ и МФ, 1980. Т. 20. №1. С. 51-69.

23. Хачиян Л.Г. Проблема оптимальных алгоритмов в выпуклом программировании, декомпозиции и сортировке // Сб. "Компьютер и задачи выбора", М.: Наука, 1989. С. 161-205.

24. Левин А.Ю. Линейное оптимальное быстродействие и центрированные сечения // Вестник Ярославского Университета, №12, 1975. С. 87-93.

25. Енчева Т.И., Левин А.Ю. О локализации точек переключения оптимального управления // Моделирование и анализ вычислительных систем, стр. 135-140, Ярославль, 1987.

26. Корнфельд И.П., Синай Я.Г., Фомин C.B. Эргодическая теория. М.: Наука, 1980.

27. Русин Ю.В., О марковском генерировании равномерного" распредел-ния в многомерной области // Эвристические алгоритмы оптимизации. Ярославль, 1981. С. 79-82.

28. Encheva T.I., Levin A.Iu. Central sections in quasi-convex programming // Comptes rendus de l'Academie bulgare des Sciences. Tome 42, №11, 1989. P. 39-42.

29. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 2. М.: Наука, 1970.

30. Шварц Л. Анализ. Т. 2. М.: Мир, 1972.

31. Михайлов Г.А. Некоторые вопросы теории методов Монте-Карло. Новосибирск, Наука, 1974.

32. Михайлов Г. А. Оптимизация весовых методов Монте-Карло. М.: Наука, 1987.

33. Бахвалов Н.С. Численные методы. М.: Наука, 1975.

34. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1978.

35. Ширяев А.Н. Вероятность. М.: Наука, 1989.

36. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.: Наука, 1982.

37. Полляк Ю.Г. Вероятностное моделирование на ЭВМ. М.: Наука, 1971.

38. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1989.

39. Никольский С.М. Курс математического анализа. М.: Наука, Т. 1. 1991.

40. Никольский С.М. Курс математического анализа. М.: Наука, Т. 2. 1991. .

41. Рокафелар Р. Выпуклый анализ. М.: Мир, 1973.

42. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.

43. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

44. Левин А.Ю. Алгоритм центрированных сечений // Тезис, докл. конф. по матем. оптим. прогр., Новосибирск, 1965.

45. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983.

46. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.

47. Бузинов A.A. Решение задачи оптимального линейного быстродействия методами центрированных отсечений // "Современные проблемы математики и информатики", Сб. науч. тр. мол. учен., студ. и асп. Вып. 2. С. 41-46, Ярославль 1999.

48. Бузинов A.A. Методы отсечений в задаче оптимального линейного быстродействия // "Современные проблемы естествознания", Сб. тез. обл. науч. конф. студ., асп. и мол. учен. С. 41-43, Ярославль 1999.

49. Бузинов A.A. О методах отсечений в линейном оптимальном быстродействии.: Препринт / Яросл. гос. ун-т. Ярославль, 2000. 15 с.

50. Бузинов A.A., Левин А.Ю. О новом применении схемы центрированных отсечений // Модел. и анализ информ. систем. Т. 7, №1. Ярославль, 2000. С. 3-5.г. А ! . Г1 Л ■ T íг i. , .¡"-с- '-.яг О С У А >'• гС 7 Г; : • H H Л Я1. Màô-oo