В двадцатом веке одним из наиболее важных разделов математики стала теория оптимального управления. Безусловно это связано, в первую очередь, с бурным развитием техники. С появлением сложных технических устроийств возникла необходимость эфективно управлять их функционированием и взаимодействием. Важным шагом в развитии теории оптимального управления стал метод динамического программирования [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 (KMUN-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+ такая, что limg® = 0 и выполнено условие.
If (x) — f (y)I < д (\х — у||), Va: G F0, Vy G V0. (2).
В качестве g® можно взять, например, модуль непрерывности 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.
Отметим, что если функция 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? [?01] преводящий объект из состояния в состояние Хэто означает, что х (£) есть решение системы (А) соответствующее допустимому управлению и{£) и удовлетворяющее начальному и конечному условиям: ^(¿-о) = #0- #(?1) = хТаким образом, рассматриваемый процесс затрачивает на переход из х$ в врем, я — ¿-оПроцесс называется опт, ималъиым в смысле быстродействия, если не существует процесса переводящего объект из жо в х за меньшее время.
Введем в рассмотрение функцию Н зависящую от переменных х = = (ж1,., :сп), и = (и1,.", ОФ = {Ф,-, Фп) п.
B) Н{ф, х, и) =ф}(х, и) =? фг^{х, и).
С помощью этой функции Н, запишем следующую систему дифференциальных уравнений для вспомогательных переменных.
C), = !,.,". где ж (£)) рассматриваемый процесс.
Для оптимальности процесса необходимо существование такого нетривиального решения ?/>(?), t Е [?01] системы {С), что для, любого момента г? [?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.
Функция —Г (р (г)) непрерывна и квазивыпукла в Уц. В каждой точке ¿-о Е Уо квазиградиентом функции — -Р (г) является вектор с = (сх,., с&bdquo-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*, очевидно следует близость, также.
В 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) итераций. Доказано, что для любого локального метода решения выпуклой задачи математического программирования при е < ½ имеет место оценка.
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. Проведено сравнение эффективности реализованного алгоритма решения ЗОЛБ с рекомендуемыми в литературе градиентными методами решения ЗОЛБ. Выявлено значительное преимущество применения методов отсечений (в различных версиях) над методами градиентного спуска и подтверждена практически высокая эффективность СММЦТ.
Реализованный алгоритм позволяет решать ЗОЛБ с постоянными коэффициентами с высокой точностью и малыми затратами времени. Исходя из представленных в работе численных данных решения ЗОЛБ, есть основания полагать, что рассмотренный подход является наиболее эффективным среди всех существующих на данный момент подходов к решению ЗОЛБ. Использование же для решения ЗОЛБ каких-либо методов градиентного спуска представляется явно нецелесообразным.
Автор выражает благодарность профессору Левину А.Ю.
