Методы отсечений в линейном оптимальном быстродействии тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Бузинов, Александр Александрович

• Бузинов, Александр Александрович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Бузинов, Александр Александрович

Введение

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Бузинов, Александр Александрович, 2000 год

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