Содержание к диссертации
Введение
Глава 1. Стохастический алгоритм выпуклого программирования 16
1.1 Локальные методы математического программирования 16
1.2 Приближенное вычисление интегралов в пространствах большой размерности 19
1.3 Повышение эффективности методов приближенного вычисления интегралов 22
1.4 Приближенное вычисление центра тяжести выпуклого многогранника в Вп 24
1.5 Алгоритм минимизации выпуклых функций . 26
Глава 2. О минимизации квазивыпуклых функций 32
2.1 Квазиградиент квазивыпуклой функции 32
2.2 Методы отсечений в квазивыпуклой оптимизации 33
Глава 3. Задачи оптимального линейного быстро действия методами отсечений 36
3.1 Постановка задачи оптимального линейного быстродействия 36
3.2 Алгоритм решения задачи оптимального линейного быстродействия методами отсечений 39
3.3 Сходимость 41
3.4 Оценка скорости сходимости . 44
3.4.1 О дифференцируемости функции F(p) . 44
3.4.2 Вспомогательные утверждения 48
3.4.3 Оценка снизу для функции h(p) 50
3.4.4 Определение константы Липшица для функции F(p) 54
3.4.5 Теорема о скорости сходимости 56
Глава 4. Численные решения задач оптимального линейного быстродействия 59
4.1 Характеристики рассматриваемых задач ОЛБ . 59
4.2 Рассматриваемые методы решения задач ОЛБ 60
4.3 Результаты численного решения задач ОЛВ 62
4.4 Примеры решенных задач ОЛБ 64
4.4.1 Задачи в Я3 64
4.4.2 Задачи в Я4 , 68
4.4.3 Задачи в Я5 . - 75
4.5 Обсуждение результатов 82
Заключение 85
Приложение 1 86
Приложение 2 95
Литература 96
- Приближенное вычисление интегралов в пространствах большой размерности
- Методы отсечений в квазивыпуклой оптимизации
- Алгоритм решения задачи оптимального линейного быстродействия методами отсечений
- Рассматриваемые методы решения задач ОЛБ
Введение к работе
В настоящее время пивоваренная отрасль России насчитывает 300 предприятий различной мощности. На сегодняшний момент она является одной из самых динамично развивающихся в секторе пищевой и перерабатывающей промышленности. Однако уже сейчас темп роста заметно замедлятся [1]. В условиях обострения рыночной конкуренции многие пивоваренные заводы вынуждены искать пути снижения затрат, в том числе и на стадии производства пива. Однако внедрение новых технологий не должно вызвать снижения качества готового продукта.
Сокращение потерь на стадии производства сусла можно достичь применением ферментных препаратов. Поэтому разработка ресурсосберегающей технологии пива с применением комплекса различных ферментных препаратов является актуальной задачей. Сокращение расхода ферментных препаратов можно достичь применением активаторов.
Другим способом является применение новых технологических приемов таких, как использование электрохимически активированных (ЭХА) растворов. Эти растворы обладают особыми свойствами и наличием в их составе окислителей и восстановителей. Применение ЭХА систем в пищевой промышленности достаточно широко. По литературным данным применение ЭХА растворов позволяет ускорить процессы экстракции и гомогенизации компонентов ячменя и солода, уменьшить время осахаривания затора.
Целью наших исследований являлась разработка комплексной ресурсосберегающей технологии производства пива на основе использования мультиэнзимных композиций и ЭХА систем.
Для реализации поставленной цели необходимо было решить следующие задачи:
- разработать технологию получения пива с применением ЭХА растворов и ферментных систем;
- исследовать возможность активации ферментных систем солода и препаратов микробного происхождения;
- провести выбор ферментных препаратов разной степени очистки, позволяющих увеличить выход экстракта при использовании солода и несоложеных материалов;
- разработать технологические приемы получения экстрактов хмеля с использованием МЭК и ЭХА систем;
- провести обоснование и выбор мультиэнзимных систем для получения экстрактов из хмеля;
- провести сравнительный анализ состава сусла и готового пива, полученного с применением ЭХА растворов.
Научная новизна.
Установлены зависимости активности ферментов от использования ЭХА растворов. Показано, что применение анолита позволяет увеличить активность амилолитических ферментов на 10-12%, а протеолитических на 25%, Установлено, что наибольший активирующий эффект на ферменты микробного происхождения оказывает анолит.
Определено, что применение ЭХА растворов на стадии получения сусла, увеличивает степень гидролиза полисахаридов, белков и повышает содержание сбраживаемых Сахаров и аминокислот. В опытном образце концентрации мальтозы и глюкозы выше соответственно на 7% и 5%. Увеличение содержания аминокислот происходит за счет лизина, валина, глутаминовой и аспарагиновой кислот,
Исследовано совместное применение ЭХА воды и ферментных препаратов для экстракции горьких веществ хмеля.
Практическая ценность работы.
Разработана комплексная ресурсосберегающая технология получения пива при совместном применении ЭХА воды и ферментных препаратов.
Установлено, что применение ЭХА воды на стадии получения пивного сусла позволяет увеличить выход экстракта на 1-1,5% и улучшить аминокислотный состав сусла.
Разработаны различные способы получения экстрактов хмеля с применением ЭХА растворов и ферментных препаратов, позволяющих сократить потери горьких веществ. Установлено, что количество изогумулона в сусле увеличивается на 27%.
Технология апробирована на экспериментально-пилотной установке в полупроизводственных условиях ГУ ВНИИ пивоваренной, безалкогольной и винодельческой промышленности.
Ожидаемый экономический эффект составляет 253,6 тыс. руб. на 1 млн. дал пива в год, при сокращении массы засыпи зернопродуктов на 1% и доли вносимых ферментов на 10%, с использованием ЭХА воды и мультиэнзимных композиций.
В двадцатом веке одним из наиболее важных разделов математики стала теория оптимального управления. Безусловно это связано, в первую очередь, с бурным развитием техники. С появлением сложных технических устроийств возникла необходимость эфективно управлять их функционированием и взаимодействием. Важным шагом в развитии теории оптимального управления стал метод динамического программирования [1] впервые предложенный Беллманом. Несмотря на наличие ряда существенных недостатков, выраженных в наложении заведомо невыполнимых условий на рассматриваемые функции, этот метод послужил отправной точкой для возникновения принципа максимума Понтрягина. Принцип максимума вначале был доказан для линейных управляемых систем и лишь после распространен на системы более общего вида. Теория принципа максимума полно отражена в работах Понтрягина Л.С, Болтянского В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. [2],[3],[4], Иоффе А.Д., Тихомирова В.М., Алексеева В.М., Фомина С.В.[5],[6]. Однако, при всей значимости,принцип максимума не дает эффективного алгоритма численного синтеза оптимального управления, даже для такого основательно изученного вопроса, как задача линейного оптимального быстродействия (ЗОЛБ), применительно к которой принцип максимума является не только необходимым, но и достаточным условием оптимальности. Решение ЗОЛБ сводится при помощи принципа максимума к рассмотрению конечномерной задачи определения подходящего начального значения фо для сопряженной системы ф = —А ф. Это безусловно важно, но вместе с тем, длительное время отсутствовали по-настоящему эффективные подходы к численному решению данной конечномерной задачи.
С появлением принципа максимума были предложены подходы к численному синтезу оптимального управления связанные с градиентным спуском. У истоков методов такого характера стоят Нейштадт и Итон [7],[8]. Изложение аналогичных подходов к решению задачи синтеза оптимального управления можно найти в работах других авторов [9],[10],[11]. К сожалению, сходимость таких методов оказывается, в большинстве случаев, очень медленной. В результате, в последнее время, на практике все чаще применяются иные методы, не связанные с принципом максимума Понтрягина. Такие методы называются прямыми [12].
Одним из разделов математики, где в последние десятилетия также произошли важные изменения, является выпуклое и квазивыпуклое программирование. Важным шагом в развитии математического выпуклого и квазивыпуклого программирования стало построение алгоритмов оптимальных по порядку числа итераций. Эти алгоритмы относятся к так называемым методам отсечений. Существенное влияние на формирование и развитие этих методов оказали работы следующих авторов: Левин А.Ю. [13],Шор Н.З. [14],[15], Немировский А.С., Юдин Д.Б. [16], [17], [18], [19], [20], Хачиян Л.Г.,Эрлих И.И., Тарасов СП. [21],[22],[23].
В связи со сказанным, большое значение приобретает факт тесной связи между теорией оптимального управления и математическим квазивыпуклым программированием. Именно, еще четветь века назад, в работе [24], Левиным А.Ю. впервые была отмечена возможность применения методов отсечений к определению начального значения фо для сопряженной системы в задаче оптимального линейного быстродействия. Впоследствии, уточнялись и совершенствовались отдельные аспекты алгоритма - отделение нулей квазиполиномов в связи с определением точек переключения [25] и т.п. Но тот факт, что в течение столь длительного времени данная идея не была реализована в виде эффективного вычислительного алгоритма, связан с тем, что на этом пути необходимо преодолеть ряд существенных трудностей, что и определяет содержание настоящей работы. Можно отметить, что при построении таких алгоритмов весьма полезными могут оказаться такие стохастические приемы как биллиардные траектории, марковские блуждания и другие [26],[27].
Цели настоящей работы сформулируем следующим образом.
1) Разработать эффективный численный алгоритм синтеза оптимального управления для ЗОЛБ, основанный на сочетании принципа максимума Понтрягина и центрированных отсечений. Сравнить эффективность алгоритмов использующих идею отсечений и алгоритмов основанных на использовании градиентных методов.
2) Показать, что принцип максимума Понтрягина является не только важным теоретическим, но, в сочетании с центрированными отсечениями, и мощным практическим средством репіения прикладных задач, намного более эффективным, чем при его традиционном применении.
Первая глава посвящена рассмотрению вопросов приближенного вычисления интегралов и выпуклого математического программирова ния, необходимых в дальнейшем. В рамках общей схемы методов отсечений [23], строится метод минимизации выпуклых функций основанный на стохастическом правиле выбора точки в текущем локализаторе. Это правило заключается в приближенном определении центра тяжести q выпуклого тела V , каковым и является каждый локализатор. Как известно справедливо равенство q = / xdx/ / dx. V V
Для вычисления интегралов в числителе и знаменателе предлагается использовать специальную версию метода Монте-Карло. Обозначим: 5 (1) - единичная сфера в Rn и \Sn(l)\ - ее (п — 1)-мерный объем, XQ -некоторая внутренняя точка выпуклого тела V, p(V) - объем тела V и для любого у Є Sn(l) p(xo,V,y) - расстояние от точки XQ ДО границы тела V в направлении у. В 1.2 доказывается следующая лемма.
Лемма 1.3: Пусть /(.т) Є L {V), 1, 2, ••• - последовательность независимых реализаций случайного вектора равномерно распределенного на Sn(l) и С : Rn — Rn невырожденное аффинное преобразование. Тогда, при т — со, имеет место соотношение \dctC\ rn Р( оУ. %)/11 % [5„(1) / Д о + tC )tn ldt Jf(x)dx v т І=І Статистика, стоящая слева, является несмещенной оценкой для интеграла справа. Далее в 1.3 показано, что данная статистика обладает определенными преимуществами (касающимися оценки дисперсии) при условии, что эллипсоид En(xQ,C) = {х : х = XQ + Cz, \\z\\ 1} является минимальным описанным эллипсоидом для выпуклого тела V.
В 1.4 доказывается следующая лемма.
Лемма 1.6: Пусть ь2, ••• - последовательность независимых реализаций случайного вектора , равномерно распределенной на S„(1), и С - невырожденное аффинное преобразование. Тогда х0 -\ -2=±—ш -4 q, (m -4 со) (1) + 1 E ( o,V,Cfc)/ %ll" 1=1
В работе рассматривается лишь случай, когда локализатор на каждом шаге является выпуклым многогранником, заданным уравнениями своих граней. Для таких множеств V реализация вычислений по формуле (1) не вызывает больших затруднений.
На основе соотношения (1) в 1.5 предлагается метод минимизации выпуклых функций, относящийся к классу методов отсечений. Этот метод сочетает использование соотношения (1) для приближенного вычисления центра тяжести текущего локализатора V с подбором для данного локализатора отображения С и точки XQ V таким образом, чтобы эли-псоид Еп(хо,С), описываемый около тела V, имел по-возможности меньший объем. Полученная схема названа стохастической модификацией метода центров тяжести (СММЦТ).
Опишем СММЦТ подробнее. Пусть VQ - выпуклый многогранник, f(x) - непрерывная, выпуклая функция на У0, достигающая на VQ своего минимума. Обозначим
n „ EC .p (xlVbCk /\\Ck \\ qk{xl Vk, С,, m) = xl + —--L- .
і—і
Здесь Vk - локализатор после к шагов, Еп(х\,Ск) - эллипсоид описанный около Vk и х\ Є V&, т - некоторое конечное число. То есть, qk(x°k, Vk, Ск, т) - приближенное значение центра тяжести qk тела Vk при каком-то выборе х°к, Ск и т.
Считаем, что вначале EH[XQ,CQ) есть некоторый эллипсоид, желательно меньшего объема, содержащий в себе тело VQ. Часто, ввиду простоты локализатора VQ, можно указать описанный эллипсоид минимального объема. Для любого к = 0,1, 2,... шаг СММЦТ состоит в следующем.
Шаг (к+1):
1. При некотором тк вычисляем qk = qk{x\, Vk,Ck, тк)
2. Очередное отсечение проводим через точку qk. Именно, вычисляем = V/( ) и пусть 7г = {х Є Rn : (x — qk,gk) 0}. Для следующего локализатора T4+i имеем: Vk+i = Vk П -кк и Vk+i С Еп{х\,Ск) П тск.
3. Строим эллипсоид Еп(хв,В) минимального объема, описанный около тела Еп(х°к, Ск) П ттк [20].
4. Если: хв Є Vk+i
То: Полагаем Ск+\ := В, х°к+1 := хв и переходим к следующему шагу.
Иначе: Перестраиваем эллипсоид Еп(хв, В) следующим образом. Пусть а - нормальный вектор первого из ограничений, составляющих Vk+\, которому не удовлетворяет точка хв- Пусть тх {хв-,о) = {х Rn : (х — хв,а) 0}. Тогда очевидно включение T4+i С Еп{хв,В) П тг (хв,а). Около полуэллипсоида Еп(хв,В) П 7г_(гг5,а) строим минимальный описанный эллипсоид Еп(хв ,В ) [20],[23]. Его объем строго меньше объема эллипсоида Еп(хв,В). Полагаем В := В , хв := хв и переходим к пункту 4.
Важно отметить, что выбор на каждом шаге подходящего отображения Ск и точки х имеет большое значение при проведении практических вычислений. Рассмотрим использование СММЦТ в задаче линейного оптимального быстродействия (схема применения методов отсечений в ЗОЛБ описана ниже). Если принять на (к + 1)-м шаге СММЦТ, VA: = 0,1,..., что Ck — Е и х\ - произвольная внутренняя точка Т4, то полученный метод оказывается крайне неэффективным. С помощью этой схемы не удалось решить ни одной ЗОЛБ размерности выше трех. Ситуация резко меняется, если подбирать для каждого локализатора V отображение Ck и точку х\ по описанной ранее схеме.
Для оценок скорости сходимости методов отсечений существенна быстроты убывания объема локализатора с ростом числа проведенных итераций. Для краткости обозначим qk{mk) = qk{xl,VhlCk,mk), fc = 0,1,... и пусть T4+i = Vfc+i(gfc(mjfc))? к = 0,1,... - локализатор, получаемый из локализатора \4 при проведении, на (к+1)-м шаге, отсечения через точку Чк{ ч)- В 1.5 для СММЦТ доказана следующая теорема. Теорема 1.1: Пусть N - натуральное число. Тогда для любого S Є (0,1) существует последовательность чисел {т к(8, V )}, к = 0, ...,iV—1 такая, что если при га& m fc(J, "Ц.), на (к -\- 1)-м шаге СММЦТ в лока-лизаторе Vk для проведения отсечения выбирается точка х\. — Qfc(mjt), то после проведения N отсечений выполнено Р(ММ&г-і(тлг-і))) (1 - e Y • /x(Vo)) 1 - 5. Для относительной погрешности по функционалу после проведения N отсечений Єм = ( min f(xk) — min f(x))/(m&x f(x) — min fix)). называемой часто просто точностью решения задачи минимизации, при использовании СММЦТ справедливо следствие из теоремы 1.1.
Следствие 1.1: Пусть N - натуральное число. Тогда для любого S Є (0,1) существует последовательность чисел {т к(5, Т4)}, к = О, ...,ЛГ—1 такая, что если при m m k(6,Vk), на (к+1)-м шаге СММЦТ в локали-заторе Vk для проведения отсечения выбирается точка-ж = д&(т ), то после проведения N отсечений выполнено
P(eN (1 - е-У") 1-5.
Во второй главе рассматривается применимость методов отсечений к решению более общей задачи минимизации квазивыпуклых функций. При минимизации выпуклых дифференцируемых функций большое значение имеет возможность вычисления градиента V/(x) минимизируемой функции в заданной точке. Если f(x) не дифференцируема, то можно использовать субградиент. В случае квазивыпуклости используется более общее понятие - квазиградиент [28].
Определение 2.1: Квазиградиентом квазивыпуклой функции f(x) в точке .то Є V называется любой вектор V/(#o) такой, что из неравенства f(x) /(.то) следует (Vf(x0),x - х0) 0.
Очевидно, что если f(x) дифференцируема в точке ГЕ0, то можно положить V/(.To) = V/(xo). Однако в общем случае, нахождение квазиградиента может представлять собой самостоятельную задачу не сводящуюся к нахождению градиента. Возможные осложнения, связанные с этим, мы здесь не рассматриваем, поскольку при решении задачи оптимального линейного быстродействия они не возникают.
Различия в применении методов отсечений в выпуклом и квазивыпуклом случае имеются не столько в алгоритме, который практически не меняется, сколько в оценке погрешности по функционалу. Для выпуклых функций, как известно, относительная погрешность по функционалу после проведения N отсечений удовлетворяет условию N (МК)М о))1/п где п -размерность пространства. Для квазивыпуклых функций эта оценкг не верна. Оценки трудоемкости некоторых методов отсечений для квазивыпуклого случая рассматривались в [19], [28].
В 2.2 приводится оценка погрешности по функционалу в квазивыпуклом случае для СММЦТ. Полагаем, что функция f(x) непрерывна на компакте У0. Тогда существует неубывающая функция g(r) : R+ - R+ такая, что limg(r) = О и выполнено условие \f(x)-f(y)\ 9(\\ -y\\h 4xEVb4yeV0. (2)
В качестве д(г) можно взять, например, модуль непрерывности f{x).
Теорема 2.1: Пусть решается задача минимизации непрерывной квазивыпуклой функции f(x) на выпуклом компакте VQ С Rn и применяется СММЦТ. Пусть d - диаметр VQ и f(x) удовлетворяет (2). Тогда для любого натурального N и любого 5 Є (0,1) существует последовательность чисел {т к(5,14)}, к = 0,..., N— 1 такая, что если при m raj.((S, 14), на (к + 1)-м шаге СММЦТ в локализаторе 14 проводить отсечение через точку Xk = qfc(nifc), то после проведения N отсечений с вероятностью более 1 — 5 выполняется условие min f(xk) - min fix) gid (1 - e-1) ")
Отметим, что если функция f{x) удовлетворяет на множестве Vo условию Липшица с некоторой константой L, то можно положить g(r) = = Lr. В этом случае, при указанном в теореме способе проведения отсечений, получим, что с вероятностью более 1 — 5 погрешность по функционалу убывает экспоненциально с ростом числа итераций.
В третьей главе рассматривается задача ОЛБ в следующей постановке: найти управление u(t) Є U С Rr переводящее за минимальное время Т решение x(t) Rn уравнения х = Ах + Ви, rc(O) = ж . в начало координат: ж(Т ) = 0. Здесь U - область управления, выпуклый многогранник, содержащий внутри себя нуль Rr, А п В вещественные матрицы с постоянными коэфициентами размерности п х п и п х г соответственно. Принцип максимума Понтрягина, в данном случае, является необходимым и достаточным условием оптимальности управления. Для задачи оптимального быстродействия в общем виде принцип максимума формулируется следующим образом [3].
Пусть рассматривается управляемый объект, движение которого описывается системой уравнений в векторной форме (А) х = fix, и) х Є Rn, и Є U.
Допустимым управлением считается произвольнал кусочио-иепрерывнал функция u(t) = {ul{t),...,ur{t)) со значениями в U, непрерывная справа б точках разрыва и непрерывная в концах отрезка, на котором она определена. Далее, в фазовом пространстве заданы две точки XQ, Х\ - начальное и конечное фазовые состояния. Наконец рассматривается некоторый процесс (u(t),x(t)), t Є [h,ti] првводящий объект из состояния XQ в состояние х\ , это означает, что x(t) есть решение системы (А) соответствующее допустимому управлению u[t) и удовлетворяющее начальному и конечному условиям: #(о) = #0; x{ti) — %i- Таким образом,, рассматриваемый процесс затрачивает на переход из XQ в Х\ врем,я t\ — t0. Процесс называется оптимальным в смысле быстродействия, если не существует процесса переводящего объект из XQ в Х\ за меньшее время.
Введем в рассмотрение функцию Н зависящую от переменных х = = (х1:...,хп), и= (и\...,иг), ф = (фь...,фп). п (В) Н{ф,х,и) = ф${х,и) = Т,Фіїі{х,и). С помощью этой функции Н, запишем следующую систему дифференциальных уравнений для вспомогательных переменных ох1 где (u(t),x(t)) рассматриваемый процесс. Для оптимальности процесса [u(t),x(t)) необходимо существование такого нетривиального решения ф{і), t Є [оэ і] системы {С), что для, любого момента г Є [ о- і] выполнено условие максимума (D) Н{ф(т),х{т),и(т))=шд1хН(ф(т),х(т),и), а в конечный момент времени t\ выполнено условие (Е) ЯМ і),я( і),и(«і)) 0. Для линейных управляемых систем принцип максимума значительно упрощается. В этом случае имеем: 1. Н(ф, х, и) = фАх + фВи. 2. Система уравнений (С) принимает вид ф = —А ф. 3. Соотношение (D) принимает вид ф{т)Ви(т) = тахф(т)Ви. 4. Соотношение (Е) просто не нужно, так как для линейных систем выполнено всегда. В случае оптимального линейного быстродействия, принцип максимума сводит задачу поиска оптимального управления к задаче определения подходящего начального значения фо для системы (С), которое обеспечивает попадание траектории в начало координат [2],[3]. В случае линейных систем эта задача сводится, в свою очередь, к нахождению точки минимума функции —F(p) в полупространстве D = {р Є Rn : {р,х+) 0}. Для любой точки р Є D, момент t = F(p) является единственным корнем уравнения /(,р) = 0, t 0, где іf{t,p) = (p,x -t(p)), Ct = - Jфі{т)Ви(т,р)(Іт, і = 1,..., п.о
Здесь фі{ї) - решение системы (С) с начальным условием ф(0) = ег- и u(t,p) - управление, отвечающее, в соответствии с (D), решению ф(Ь,р) системы (С) с начальным условием ф(0,р) = р. Минимума функция —F(p) достигает в конусе Н = {р Є Rn : ж = т„(р)} С D [3]. Такое сведение задачи поиска оптимального управления к задаче минимизации функции в конечномерном пространстве является важным достоинством принципа максимума.
Определяемая таким образом функция —F(p) оказывается непрерывной, квазивыпуклой [28] и квазиградиентом для нее в точке р Є D является вектор у(р) = ж —F(P)(P)- В 3.2 дается описание схемы использования методов отсечений для поиска начального значения ф§. Важно отметить, что задача минимизации —F(p) в полупространстве D сводится к задаче минимизации —F{jp) в некотором компактном множестве V С D размерности (п — 1).
Поступаем следующим образом [24]. Найдем п линейно независимых векторов образующих с искомым вектором фо неострый угол. Для этого положим _ а?» _ y(pi-i) . . . \Ы\ \\У(РІ-І)\\ где pi,...,Pn-i - какие-либо попарно неколлинеарные вектора из D. Поскольку не исключена линейная зависимость векторов (3), могут понадобиться вычисления F(p) и у(р) более чем вп-1 точках.
Определив вектора (3) мы заключаем вектор ф$ в конус К являющийся пересечением п полупространств 7гг- = {р Є Rn : (yi,p) 0}, і = 1,...,п. Как известно, данный п-гранный конус К может быть представлен в виде К = {PeRn :р= Е \№, Л,- 0, Wi Є Rn, і = 1,•...,n}. Каждый вектор W{ определяется из системы і {yj,Wi)=0, зфі. Поскольку существенно лишь направление вектора / о, то можно искать вектор ф$ в выпуклой оболочке точек Wi, то есть в многограннике V = {р Є Rn : р = Е Л;«7,-, Л,- О, Е Л; = 1}. i—l i—l Очевидно V можно представить в виде V = {р Є Rn : р = «л + "Ё 2гК+і - wi), г,- О, "Ё г,- 1}. (4) »=1 » =1 Обозначим p(z) = ги і + гі(ги2 - гиі) Н Ь zn_i(w„ - w\). (5) Таким образом, задача минимизации функции —F(p) в ) сводится к задаче минимизации функции —F(z) = —F(p(z)) в симплексе Vo, где = (26 : 2 1, г,- 0, г = 1,...,п-1}. г=1
Функция —F(p(z)) непрерывна и квазивыпукла в VQ. В каждой точке ZQ Є VQ квазиградиентом функции —F(z) является вектор с = (ci,..., cn_i), где СІ = (wi+i - wi, y(po)), г = 1, —, n-1 и po= p(z0).
В 3.3 исследуются вопросы сходимости при минимизации —F(z) методами отсечений. Рассматривается сходимость СММЦТ при минимизации функции —F(z). Доказывается следующая теорема.
Теорема 3.1: 1. Для любых 7] 0 и 5 Є (0,1) найдется N(rj) 0 такое, что для любого N N(r]) существует последовательность чисел {т к(5, Т4)}, к = 0,..., N—1 такая, что если при mjt т к{8, Т4) на (& + 1)-м шаге СММЦТ в локализаторе Vk проводить отсечение через точку Zk = = Qk(iTik), то после проведения iV отсечений с вероятностью более 1 — 6 выполняется условие min (-F(zk)) -mm(-F(z)) rj. 0 k N-V V " z6V0x v " 2. Для любых г] 0 и 6 Є (0,1) найдется N(rj) 0 такое, что для любого N N(TJ) существует последовательность чисел {w fc (J, Т4)}, к = = 0,..., iV —1 такая, что если при т& mjj!(, Vk) на (&+1)-м шаге СММЦТ в локализаторе V проводить отсечение через точку z = (fa (га ), то после проведения N отсечений с вероятностью более 1 — 5 выполняется условие /К - Ы) ) ту, где Н - множество точек минимума функции —F(z) на VQ и p(z, V) - есть кратчайшее расстояние от точки z до множества V.
Отсюда, в силу линейной связи (5), из близости, в вероятностном смысле, z N = arg min (-F(zk)) к H , очевидно следует близость, также в вероятностном смысле, точки p(z N) к Н .
В 3.4 исследуется скорость сходимости предложенного метода. Рассматривается задача определения для функции F(p) на множестве V вида (4) константы Липшица. Важную роль здесь играют свойства функции F(p) в той или иной задаче ОЛБ. Как уже отмечалось, \/р Є D F(p) является решением уравнения f(t,p) = 0. Отсюда, если в точке р h(p) = /( , p)t=F(p) ф 0, то F(p) дифференцируема в точке р и градиент в этой точке имеет вид [3] VF(p) = - - )(Р). h{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 Л Sn(l). При выполнении условий леммы 3.4 удается отделить h{p) от.нуля на D(l Sn(l). Лемма 3.9: Пусть ТУТ , где Т время оптимального движения из точки ж в начало координат. Тогда, если г п и rangiB) = п, то VpeDnSn(l) hip) С. = c(U) min Ы • inf Л • ехР(-И • T) 0. \. і к PEbn(l) Здесь Vi7 г = 1,..., А; вершины многогранника управления /", с(С7) = mm mm (w,-/IM,by/M) 0 и biji 3 — -,----, Si нормали граней U смежных с вершиной г г-. Значение Т можно получить построив какое-либо допустимое управление переводящее ж в нуль. Но в одном частном случае можно получить оценку не содержащую Т. Обозначим д і — 1,...,п собственные вектора матрицы —Л и пусть G = [діт--,дп], где д-г -вектор столбец. Имеет место следующая лемма.
Лемма 3.10: Пусть собственные числа матрицы —А вещественны, различны и положительны, г п и гапд(В) = п Тогда Vp Є D П 5n(l) h{p) - c-= IcFlb • ІШ ЫАв 1 ° Отделение h(p) от нуля на множестве D П 5П(1) позволяет доказать существование константы Липшица для F(p). В 3.4.4 доказывается следующая теорема.
Теорема 3.2: Пусть Т Т , г п и гапд(В) = п. Тогда W 0 функция F(p) на множестве D\Bn(v) удовлетворяет условию Липшица с константой L(v) = 2v lC;x • рТ \\В\\ ехр(А • Г), (6) где /) = max \\vA\ и Вп(у) - открытый шар радиуса и с центром в нуле. i f fc
Из теоремы следует, что F{jp) удовлетворяет на множестве V вида (4) условию Липшица, так как всегда найдется такое v 0, что выполнено V С D\Bn(i/). В качестве г/ можно взять, например, кратчайшее расстояние от начала координат до множества V. Существование константы Липшица позволяет оценить скорость сходимости по функционалу при минимизации —F(z) методами отсечений. В 3.4.5 доказывается соответствующая теорема для СММЦТ.
Теорема 3.3: Пусть г п и rang(B) = п. Тогда при минимизации функции —F(z) на VQ С ПОМОЩЬЮ СММЦТ выполнено: для любого натурального N и любого 5 Є (0,1) существует последовательность чисел {" .(5,14)}, к = 0, ...,iV — 1 такая, что если при т т к(5,Т4) на (к + 1)-м шаге СММЦТ в локализаторе Vj. проводить отсечение через точку Zk = їк{™ к)- то после проведения N отсечений с вероятностью более 1 — 5 выполняется условие о В&-1(- )) - -Р М 11 (1 - е-1) »-1) Здесь W = [w2 — «ч,..., ги„ — wi], где (w;,-+i — w/i), г = 1,..., п — 1 рассматривается как вектор столбец (см.(5)).
В четвертой главе приводятся результаты численного решения ряда ЗОЛБ четырмя различными методами. Два из них относятся к методам отсечений - это СММЦТ и метод описанных эллипсоидов. Два других - рекомендуемые в литературе градиентные методы с выбором шага по Болтянскому В.Г. и по Итону Дж. [3]. Каждым из рассматриваемых методов решалось пять десятков различных ЗОЛБ. При этом наблюдается значительное превосходство методов отсечений над градиентными методами, как по времени работы, так и по точности получаемых решений. Подробное обсуждение результатов проводится в 4.5.
Сравнение всех рассматриваемых методов проводилось на задачах, большинство из которых построены случайным образом. Схема построения случайных ЗОЛБ описана в 4.1. При этом, все рассмотренные задачи удовлетворяют следующим общим ограничениям.
1. Матрица А устойчива.
2. и Є U С Rr, х Є R \ где г = 1,2,3 и п = 3,4,5.
3. Выполнено условие общности положения.
Результаты решения задач ОЛБ каждым из методов приводятся в приложении 1 в табличной форме и подтверждают высокую эффективность применения методов отсечений для решения ЗОЛБ в сравнении с рекомендовавшимися ранее градиентными методами.
Приближенное вычисление интегралов в пространствах большой размерности
Сразу подчеркнем особенность настоящей работы. Важное (если не решающее) значение для оценки работы носит общий характер экспериментальных данных. Именно он свидетельствует, что предлагаемое изменение схемы использования принципа максимума - применение центрированных отсечений, приводит к радикальному повышению эффективности алгоритма. По этой причине много места уделяется описанию результатов проведенных экспериментов.
В данном параграфе мы подведем итоги проделанной работы, опираясь на экспериментальные данные решения ряда задач оптимального линейного быстродействия, представленных в предыдущем параграфе, а также в приложениях 1 и 2.
Главная цель работы, сформулированная во введении, достигнута - реализован эффективный алгоритм синтеза оптимального управления для класса задач оптимального линейного быстродействия с постоянными коэфициентами, основанный на сочетании двух базовых идей -принципа максимума Понтрягина и центрированных отсечений. Идея алгоритм впервые высказана в [24] и кратко описывается в 3.2. Проведенные исследования доказали на практике его высокую эффективность. Суть этого алгоритма состоит в минимизации методами отсечений возникающей в ЗОЛБ квазивыпуклой функции —F(p). Напомним, что специфика решения ЗОЛБ такова, что определив точку минимума функции —F(p), мы одновременно находим и искомое оптимальное управление, и время оптимального движения под воздействием этого управления, то есть решаем задачу ОЛБ.
Полученные при выполнении работы данные численного решения свыше тридцати различных задач ОЛБ, убедительно показали преимущества применения методов отсечений в ЗОЛБ над использованием в ЗОЛБ градиентных методов. Для проведения сравнения были реализованы четыре различных алгоритма решения ЗОЛБ. Два из них используют для минимизации —F{p) методы центрированных отсечений- метод описанных эллипсоидов и предложенную в первой главе стохастическую модификацию метода центров тяжести (СММЦТ). Эти алгоритмы являются модификациями схемы изложенной в 3.2. Два других являются рекомендуемыми в литературе градиентными методами и описаны в 4.2.
Сравнение эффективности всех методов проведено по следующим характеристикам: реальное время затрачиваемое на поиски решения, расстояние фазовой точки до нуля в конечный момент времни движения. В итоге получены следующие результаты.
Для задач в Л3, превосходство методов отсечений над градиентными методами по затратам времени, при одинаковых требованиях к точности попадания траектории в начало координат, составляет в среднем два порядка. В тех задачах, где рассматриваемые методы градиентного спуска получают точность попадания в начало координат такую же как методы отсечений (главным образом это задачи в Л3), мы имеем полную картину соотношения характеристик тех и других методов.
При переходе к RA и Rb сходимость градиентных методов стала еще более медленной и, с целью ограничения времени работы этих методов разумной величиной (не более трех часов), в большинстве из представленных в предыдущем параграфе задач в Л4 и і?5, были установлены ограничения на число проводимых итераций. Однако по достижении установленных ограничений градиентные методы не смогли получить сколь нибудь приемлемой точности попадания в начало координат. То есть в таких случаях, по истечении длительного промежутка времемени, решение ЗОЛБ градиентными методами так и не было найдено. Поэтому есть все основания считать, что реальное превосходство методов отсечений по затратам времени, для задач в І?4, Л5, достигает в среднем трех-четырех порядков. Подробные численные данные, подтверждающие сказанное, представлены, в табличной форме, в приложении 1. Эти данные позволяют также оценить реальные затраты градиентных методов в тех задачах, где за отведенное число итераций приемлемая близость фазовой точки к нулю в конечный момент времени не была достигнута.
Важно отметить, что при переходе к неавтономным задачам управления существенно увеличится стоимость вычисления квазиградиента функции —F(p). Учитывая огромное преимущество методов отсечений над градиентными методами по количеству проводимых итераций, переход к таким задачам еще больше увеличит превосходство методов отсечений в ЗОЛБ.
Обратим внимание на еще одно обстоятельство. Как видно из данных, представленных в приложении 1, с ростом размерности задачи, заметно возрастает преимущество СММЦТ над МОЭ по числу проводимых итераций. Более того, видно, что число итераций СММЦТ растет, в среднем, линейно с ростом размерности задачи и близко к числу итераций теоретически предсказываемому для детерминированного метода центров тяжести в худшем случае. Поэтому с усложнением задачи ОЛВ следует ожидать, что более предпочтительным станет использование СММЦТ по сравнению с МОЭ.
Представленные результаты убедительно доказывают, что при решении ЗОЛБ принцип максимума является не только теоретическим, но и мощным практическим средством. Но при этом, его целесообразно сочетать не с с градиентными методами, как это рекомендовалось до сих пор в большинстве источников, а с методами центрированных отсечений. Это можно считать главным итогом работы.
Малая эффективность градиентных методов подтверждается, в част ности, следующим примером. Градиентным методом с шагом Болтянского, который является улучшением исходного метода с шагом Итона (см. 4.2), после 11 часов 17 минут 40 секунд работы над решением задачи 14 было проведено 65000 итераций. При этом найденное значение времени оптимального движения равно 2.913649922 (тогда как методы отсечений дают значение времени оптимального движения равное 5.505520206), а полученная, по истечении указанного времени, траектория, рассматриваемая на отрезке [0,2.913649922], не приближается к началу координат ближе чем на расстояние 31.1693 единицы. В то же время, применяя ме-тоды отсечений получаем расстояния до нуля порядка 10 — 10 , при этом затраты времени составляют около 100 секунд.
Все численные эксперименты проводились на персональном компьютере с процессором Intel Pentium-S, 133 MHz.
Методы отсечений в квазивыпуклой оптимизации
Итоги проделанной работы состоят в следующем. 1. Предложен и обоснован стохастический метод минимизации выпуклых и квазивыпуклых функций, названный стохастической модификацией метода центров тяжести (СММЦТ). 2. Реализован эффективный алгоритм численного решения ЗОЛБ с постоянными коэффициентами, основанный на сочетании принципа максимума Понтрягина и центрированных отсечений. 3. Определены условия существования и получено выражение константы Липшица для функции — F(p). Наличие константы Липшица позволяет получить более точную информацию о числе итераций требуемых для решения ЗОЛБ предложенным методом. 4. Проведено сравнение эффективности реализованного алгоритма решения ЗОЛБ с рекомендуемыми в литературе градиентными методами решения ЗОЛБ. Выявлено значительное преимущество применения методов отсечений (в различных версиях) над методами градиентного спуска и подтверждена практически высокая эффективность СММЦТ. Реализованный алгоритм позволяет решать ЗОЛБ с постоянными коэффициентами с высокой точностью и малыми затратами времени. Исходя из представленных в работе численных данных решения ЗОЛБ, есть основания полагать, что рассмотренный подход является наиболее эффективным среди всех существующих на данный момент подходов к решению ЗОЛБ. Использование же для решения ЗОЛБ каких-либо методов градиентного спуска представляется явно нецелесообразным. Автор выражает благодарность профессору Левину А.Ю.
В приложении 1 используются обозначения введённые в 4.3. В табличной форме представлены две группы результатов численного решения задач из 4.4. Одна соответствует значению є = Ю-10 в правиле остановки (55) и ее развернутый аналог содержится в 4.4. Другая соответствует значению є = Ю-14. Это позволяет сравнить другие характеристики рассматриваемых в работе методов решения ЗОЛБ в обоих случаях.
Таблицы 1.1,1.2,1.3 соответствуют є = Ю-10, таблицы 2.1, 2.2, 2.3 соответствуют є = Ю-14. В таблицах 1.1, 2.1 содержатся данные о времени решения (в секундах) каждой задачи каждым из методов. Там же, для задач одинаковой размерности, указано среднее время работы каждого метода. Аналогичные данные о количестве итераций собраны в таблицах 1.2, 2.2. Данные о расстоянии до нуля траекторий X{(t) в конечные моменты времени Т , і — 1,2,3,4 для каждой задачи представлены в таблицах 1.3, 2.3.
Для задач 7,8,11,12,14-20, в столбцах таблиц 1.1, 1.3 и 2.1, 2.3, отвечающих градиентным методам, содержатся результаты полученные этими методами после проведения числа итераций, указанного для них в соответствующих строках таблиц 1.2 и 2.2 соответственно.
В таблице 3, для задач 7,8,11,12,14-20 указаны наибольшие значения функции F(p), полученные градиентным методом с шагом Болтянского. При этом, через F Bolt обозначены наибольшие значения функции F(p) полученные после проведения числа итераций указанного для данного метода в таблице 1.2, а через F oU обозначены наибольшие значения функции F{p) полученные после проведения числа итераций указанного в таблице 2.2. Аналогичные данные для задач 7,8,11,12,14-20 по градиентному методу с шагом Итона содержатся в таблице 4. Используемые в таблице 4 обозначения F Eaton и Fgaton имеют для метода с шагом Итона тот же смысл, что обозначения F Bolt: FBolt для метода с шагом Болтянского. В качестве приемлемого максимального значения функции F{p) для задач 6,7,10,11,13-19 в последнем столбце таблиц 3 и 4 указаны значения, полученные для рассматриваемых задач с использованием СММЦТ при є = 10 10 в правиле остановки (55).
Согласно сказанному в 4.2 о градиентных методах, всегда F(pk) F(pk i), то есть приближение к максимальному значению происходит монотонно. Это позволяет оценить, по данным таблиц 1.1,1.2, 2.1, 2.2 и 3, 4, затраты времени и итераций, необходимые каждому из рассмотренных градиентных методов в задачах 7,8,11,12,14-20 для достижения приемлемого максимального значения функции F(jp). Таким образом мы получим более полное представление о затратах рассматриваемых градиентных методов в ЗОЛБ вцелом.
Во всех остальных задачах градиентные методы работали до тех пор, пока не получали такое же значение максимума функции JP(P), что и методы отсечений. Для этих задач градиентные методы и методы отсечений получают практически одинаковую точность попадания в начало координат, что позволяет сравнить эффективность методов непосредственно по табличным данным.
Заметим, что в задачах из Л4, решаемых градиентными методами, у функции F(p) эффект острия выражен весьма слабо (см. замечание 3.5), а в тех, где градиентные методы за длительное время не получили приемлемого решения, эффект острия выражается заметно сильнее. Также, эффект острия является существенным и во всех представленных задачах в Л5.
Алгоритм решения задачи оптимального линейного быстродействия методами отсечений
В большинстве расмотренных задач, в малой окрестности точки максимума (порядка 10 5 - Ю-10), функция F(p) стремительно возрастает. Значения нормы градиента (в различных задачах) достигают величин порядка 105 - 1015. При этом, проверка поведения функции в еще более мелких (на несколько порядков) окрестностях точки максимума показывает, что, по-видимому, в самой точке максимума функция F(p) остается дифференцируемой. Эту особенность поведения функции F(p) можно назвать эффектом острия.
Строгого теоретического объяснения природы данного эффекта мы пока не имеем. Однако, исходя из проведенных экспериментов, можно выделить некоторые факторы влияющие на его характер. 1. Разброс модулей вещественных частей собственных зна чений матрицы А. Чем больше разница между максимальной по мо дулю и минимальной по модулю вещественными частями собственных значений, тем сильнее выражен эффект острия. 2. Удаленность начальной точки я от начала координат. Чем дальше точка ж , тем сильнее выражен эффект острия. 3. Размерность многогранника управления U С Rr. Экспериментальный анализ ряда задач показал, что при г п эффект острия выражен слабее, чем для той же задачи при г п. Данный эффект наблюдается уже для задач в J?2, при вещественных собственных значениях матрицы А и одном управляющем параметре. В качестве примера, в приложении 2 приведены графики функции F{z) = F(p(z)) для одной задачи оптимального линейного быстродействия в І?2, при различном удалении точки гс от начала координат. Наличие практически в каждой задаче эффекта острия заставляет, для успешного решения задачи поиска оптимального управления, использовать максимальное число разрядов в представлении действительных чисел на ЭВМ. Возможно также, что именно наличие у функции F(p) данного эффекта является одной из главных причин необычайно неудовлетворительных результатов показываемых градиентными методами во многоих ЗОЛБ. Данное предположение подтверждается проведенными экспериментами. Детальное исследование описанного эффекта и изучение его природы, является темой дальнейшей работы. Различные методы, такого типа, различаются правилом выбора шага. Здесь мы воспользуемся для решения задач оптимального линейного быстродействия двумя методами. Первый из них предложен Болтянским В.Г. второй восходит к Итону [3]. В данном параграфе приводятся данные численного решения ряда задач ОЛБ в Я3, Я4, R5. Для каждой задачи выписывается уравнение движения, область управления и начальная точка в фазовом пространстве. Также выписываются собственные значения A = (Ai, ..., Ап) матрицы А. В качестве результата работы указывается общий вид найденного оптимального управления u(t) и для каждого метода выписываются: найденные значения моментов переключения оптимального управления, оценка снизу для времени оптимального движения Т , расстояние до нуля в конечной точке траектории, соответствующей найденному управлению. Также, для каждого метода указывается число итераций, проведенных при поиске значения гро и затраченное на это время. Для каждой задачи обозначим: N1 - число итераций проведенных методом описанных эллипсоидов. N2 - число итераций проведенных СММЦТ.- число итераций градиентного метода с шагом Болтянского. iV4 - число итераций проведенных градиентным методом с шагом Итона. т„т2,т3,т4 - реальное время, затраченное соответствующим методом при проведении указанного числа итераций - Nt, І\Г2, iV3, ЛГ4. Т1, і = 1,2,3,4 - оценка времени оптимального перехода из х+ в начало координат, найденная соответстующим методом. жг(Т+г), г = 1,2,3,4. - расстояния до нуля траектории жг-() в момент Тг%. Здесь х\{) - траектория полученная после проведения N\ итераций метода описанных эллипсоидов, X2(t) - траектория полученная после проведения iV2 итераций СММЦТ, xs(t) - траектория полученная после проведения iV3 итераций градиентного метода по Болтянскому, ХА{Ь) - траектория полученная после проведения N± итераций градиентного метода по Итону. Как уже отмечалось, искомое значение ф минимизирует функцию —F(jp) в D. Опишем какое значение р Є D выбирается в качестве приближения для і/?о, другими словами опишем правило остановки процесса минимизации функции —F(p). Поступаем следующим образом. Задаем значение є 0. Остановка процесса происходит, когда выполнено полученную за проведенные к отсечений. Данное правило регулирует работу методов отсечений. Что касается методов градиентного спуска с шагом Болтянского и Итона, то их работа прерывается либо по достижении того же минимального значения для —F(p), что и найденеє методами отсечений в соответвующей ЗОЛБ, либо (в случае если за длительное время решение не определяется) по достижении установленного для них, в той или иной задаче, ограничения на число проводимых итераций.
Рассматриваемые методы решения задач ОЛБ
В данной главе будут рассмотрены некоторые вопросы применения методов отсечений к минимизации квазивыпуклых функций на выпуклых множествах.
Как известно, определенная на выпуклом множестве V С Rn функция /(ж) называется квазивыпуклой на этом множестве, если Vc Є R множества {х Є V : f(x) с} выпуклы. Легко видеть, что замена нестрогого неравенства строгим приводит к эквивалентному определению.
При минимизации выпуклых дифференцируемых функций методами отсечений существенную роль играет возможность вычисления градиента V/(x) в заданной точке. В случае недифференцируемости вместо градиента можно использовать субградиент. Для квазивыпуклого случая используем более общее понятие - квазиградиент [28]. Квазиградиентом квазивыпуклой функции f(x) в точке х0 Є V называется любой вектор Vf(xo) такой, что из f(x) /(XQ) следует выполнение (У/(жо),ж — хо) 0. Для определенности будем полагать V/(XQ) = 0 если XQ является точкой минимума /(ж) на V. Очевидно, для любой точки х Є V в которой f(x) дифференцируема можно положить Vf(x) = с Vf(x) при любом О 0. Было доказано (Енчева Т.И., Левин А.Ю.) что для квазивыпуклости непрерывной функции f(x) на выпуклом компактном множестве V С С Rn необходимо и достаточно, чтобы в каждой точке множества V у функции f(x) существовал квазиградиент. Нахождение квазиградиента может представлять собой самостоятельную задачу, не всегда сводящуюся к нахождению градиента. Однако в приложениях типичным является случай, когда в качестве квазиградиента может быть выбран градиент. В дальнейшем будет видно, что в задаче оптимального линейного быстродействия с определением квазиградиента не возникает каких-либо особых проблем. Несмотря на то, что с момента возникновения методов отсечений была ясна возможность их применения для минимизации квазивыпуклых функций [44], большинство работ относились к выпуклому программированию. Это отчасти объясняется отсутствием важных прикладных задач минимизации квазивыпуклых функций. В методах отсеченний, которые используют только вычисление Vf(x) или V/(ar) между выпуклым и квазивыпуклым случаем нет существенных различий. Если же применяются схемы в которых на каждом шаге вычисляется также и значение /(ж), то различия имеются не столько в алгоритме [17], который практически не меняется, сколько в оценке погрешности по функционалу. Для выпуклых функций известна удобная оценка трудоемкости [16], [43], которая для квазивыпуклых функций не верна. Оценки трудоемкости некоторых методов отсечений для квазивыпуклого случая рассматривались в [19], [28]. Здесь мы оценим погрешность по функционалу для СММЦТ. Следуя [21], назовем s-размером функцию //, определенную на выпуклых телах V С Rn, р : V —ї R+, если она возрастает по включениям и однородна, степени s 0, по гомотетиям Во всех известных версиях метода отсечений s = п. Пусть рассматривается задача минимизации непрерывной квазивыпуклой функции f(x) на выпуклом компакте VQ С Rn- Опишем общий шаг метода отсечений. Пусть У , -локализатор точки минимума после к шагов. На (к + 1)-м шаге в Vj. выбирается некоторая точка Xf. и вычисляется f(xk) и Vf(xk). Если Vf(xk) = 0, то Xk принимается за решение. В противном случае отсекается часть У , лежащая в полупространстве (Vf(xk),x-xk) 0 (25) и не содержащая точек минимума f(x). При этом обеспечивается выполнение неравенства (8). В общем случае нельзя гарантировать обращение V/(rc) в нуль в точке минимума, поэтому приведем оценку погрешности по функционалу после проведения N отсечений для СММЦТ. Поскольку f(x) полагается непрерывной на компакте VQ, существует неубывающая функция д{г) : Я+ - JR+, limg(r) = 0 такая, что В качестве д можно выбрать, например, модуль непрерывности f(x) или любую монотонную оценку сверху на него. Пусть /i(V) есть объем множества V С Rn, тогда для СММЦТ справедлива следующая теорема. Пусть решается задача минимизации непрерывной квазивыпуклой функции f(x) на выпуклом компакте Vb С Rn и применяется СММЦТ. Пусть d-диаметр множества Vo и /(ж) удовлетворяет (26). Тогда, для любого натурального N и любого 8 Є (0,1) существует последовательность {m k(8,Vk)}i к = О,..., TV — 1 такая, что если при тк m fc( 5, Vk) на (к + 1)-м шаге СММЦТ в локализаторе Vk проводить отсечение через точку Xk"= Цк(тк)і т0 после проведения iV отсечений с вероятностью более 1 — выполняется условие Доказательство: Выберем натуральное N, тогда для V5 Є (0,1), в силу теоремы 1.1, существует последовательность чисел {тпк(5,Ук)}, к = 0, ...,iV — 1 такая, что если при тк m k(8,Vk) на [к + 1)-м шаге СММЦТ в локализаторе Vk проводить отсечение через точку хк = gjt(mjfc), то после проведения JV отсечений с вероятностью более 1 — 8 выполняется