Содержание к диссертации
Введение
I. Исследование процедуры Кифера-Вольфовица для нахождения точки экстремума функции регрессии с оцениванием второй производной
I. Основные леммы
2. Описание исследуемой процедуры и условий на функцию регрессии
3. Сходимость процедуры поиска минимума ,с оцениваниг ог. ем второй производной
4. Сходимость с вероятностью I последовательности случайных величин Вп к значению второй производной функции регрессии в точке экстремума 34
5. Скорость сходимости процедуры и последовательности А а оценок второй производной
6. Асимптотические свойства процедуры с оцениванием второй производной. Оптимальность процедуры .
Процедуры поиска экстремума функции регрессии с использованием метода наименьших квадратов и сплайнов
1. Необходимые сведения 48
2. Построение процедуры поиска экстремума функции регрессии с использованием метода наименьших квадратов
3. Сходимость процедуры с вероятностью I 52
4. Поведение процедуры с использованием метода наименьших квадратов при невыпуклых функциях регрессии
5. Минимизация функции регрессии с использованием интерполяционных и сглаживающих сплайнов
6. Некоторые результаты экспериментального исследрвания алгоритмов на ЭВМ
Заключение... 79
Приложение . 8
Литература
- Описание исследуемой процедуры и условий на функцию регрессии
- Скорость сходимости процедуры и последовательности А а оценок второй производной
- Построение процедуры поиска экстремума функции регрессии с использованием метода наименьших квадратов
- Поведение процедуры с использованием метода наименьших квадратов при невыпуклых функциях регрессии
Описание исследуемой процедуры и условий на функцию регрессии
Во П главе, состоящей из шести параграфов предлагается процедура поиска экстремума функции регрессии, использующая метод наименьших квадратов. В пункте 1 уже отмечалось то обстоятельство, что классические процедуры стохастической аппроксимации (0.2) и (0.3) не используют на /ъ-ом шаге предыдущих наблюдений величин f(К) Однако в целом ряде практических задач, в которых осуществление эксперимента, необходимого для наблюдения случайной величины f fX), связано с большими материальными или временными затратами, представляется целесообразным использование хотя бы части накопленной информации о процессе. Следует отметить что в рассмотренной в I главе процедуре (0.4) эта информация использовалась, но только при оценке второй производной.
В процедуре же, исследуемой во П главе, конечное фиксированное число Измерений используется для оценки производной функции FfX) в точке Xs , которая позволяет определить точку Xs+f
Надо отметить, что учет предыдущих наблюдений производится лишь в том случае, если точки Xj. , .. . , Xs не очень близки друг к другу. В этом случае в качестве оценки производной РМ в точке Х$ берется угловой коэффициент прямой, построенной по методу наименьших квадратов на основании наблюдений f (Х-3_Ыч), ... , /% (Х5)ъ точках s-if i t Xs , Естественно ожидать, что при этом можно получить более достоверную оценку производной (особенно на тех участках, где функция FfX) близка к линейной) чем в классических процедурах, использующих лишь два наблюдения в точках XS"CS и Xs - -Cs . В предлагаемую процедуру можно ввести также и оценку второй производной функции регрессии подобно тому, как это делалось в 1-ой главе.
Далее предлагается использовать для оценки производных построение интерполяционных и сглаживающих сплайнов по наблюдениям функции регрессии, выполненным в некоторой совокупности оценок точки минимума.
В 1 второй главы приводятся сведения о случайных ква-зифейеровских последовательностях и их свойства, используемых в доказательстве теоремы о сходимости рассматриваемых процедур. Эти понятия и свойства впервые были введены и доказаны в работе /26/, обобщающей понятие фейеровской последовательности, рассмотренное в /27/.
В 2 содержится построение процедуры поиска минимума функции регрессии. Оценка производной выполняется в соответствии с вышеприведенными замечаниями с использованием метода наименьших квадратов. Приводятся условия, которым должны удовлетворять функция регрессии и ошибки (помехи) при ее измерениях. Приводимый набор условий является, в общем-то, стандартным для такого рода процедур. Помехи предполагаются ограниченными на каждом конечном отрезке (но не обязательно на всей прямой), что выполняется для большинства практических задач. Кроме того, следует отметить, что в приложениях сходимость процедур стохастической аппроксимации имеет место, как правило, и при более слабых условиях чем те, при которых она доказана теоретически, что является, по-видимому, следствием недостаточного совершенства применяемых методов доказательства. Рассматриваемая в работе процедура определяется формулой
В 3 обсуждается вопрос сходимости предложенной процедуры. G использованием свойств случайных квазифейеровских последовательностей доказывается
Теорема 3.1. Построенная в 2 процедура (то есть последовательность случайных величин Х$ , определяемая соотношениями (0.5)-(0.7)) сходится к точке минимума функции регрессии с вероятностью I.
Отметим, что функция регрессии здесь предполагается выпуклой и дважды дифференцируемой.
В конце параграфа указана скорость сходимости рассматриваемой процедуры. В 4 рассматривается вопрос о возможности применения процедуры (0.5)-(0.7) с использованием для оценки производ ных метода наименьших квадратов в случае минимизации невыпук лых функций регрессии. Для решения этой задачи достаточно лишь немного модифицировать построенную в 2 процедуру. Предположим, что задача минимизации решается на некотором множестве А-ІХ ІХІ
Скорость сходимости процедуры и последовательности А а оценок второй производной
В предыдущих параграфах были доказаны сходимость процедуры к точке минимума функции FCoc) и сходимость последовательности Л п. к значению второй производной в точке экстремума. Но пока остался открытым вопрос о том, в чем же состоят существенные особенности рассматриваемой процедуры и какие ее свойства определяют целесообразность ее применения вместо стандартного алгоритма Кифера-Вольфовица поиска экстремума фрнкпии регрессии. Оказывается, что рассматриваемая процедура оптимальна в смысле своих асимптотических свойств, а именно: случайная величина VtVc cX S) является асимптотически нормальной со средним 0 и минимальной предельной дисперсией по сравнению со всеми процедурами Кифера-Вольфовица, использующими другой способ выбора коэффициента при определении ct . Этот факт устанавливает следующая
Это можно показать с помощью леммы 1.3, аналогично /13/, где показано, что при с1ь.-- в стандартной процедуре Кифера-Вольфовица асимптотическая дисперсия есть
При решении задач стохастической аппроксимации мы не располагаем значением ои и поэтому не можем положить рассмотренная процедура вместе с теоремой 6.1 означает, что асимптотической оптимальности можно добиться, вводя в определение процедуры вместо неизвестного параметра сИ его оценку.
В 1 приводятся необходимые сведения о свойствах случайных квазифейеровских последовательностей, используемых при доказательстве сходимости предлагаемой процедуры,
В 2 строится процедура и описываются условия, которым должна удовлетворять функция регрессии и случайные ошибки измерений.
3 содержит доказательство теоремы о сходимости процедуры к точке экстремума с вероятностью I.
В 4 рассматривается случай, когда функция регрессии не является выпуклой.
В 5 рассматриваются возможные обобщения процедуры, построенной в 2, связанные с построением сплайнов.
В 6 содержатся результаты численного моделирования задачи минимизации функции регрессии.
При исследовании сходимости процедуры поиска экстремума функции регрессии с использованием метода наименьших квадратов нам понадобятся некоторые свойства случайных квазифейе-ровских последовательностей, впервые изученные в работе /26/.
Напомним (см./26/), что последовательность случайных величин XS((A?) называется случайной квазифейеровской относительно множества Д С /R. . если для произвольной точки Ч Л выполняется неравенство Т -алгебра, индуцированная семейством (Х0}... , Xs)t а неотрицательные случайные величины W$ являются измеримыми относительно &5 и
При доказательстве сходимости процедур будет использована Теорема I.I /26/. Если последовательность случайных величин Xs(OJ) является случайной квазифейеровской относительно множества А » то: 1) для любого у А последовательность /U -Xs(о)/ сходится почти наверное; 2) множество предельных точек {XS(CJ)J яе пусто почти для каждого и; ; 3) если предельная точка X(CJJ последовательности Xs ( ) для некоторого СХГ принадлежит А , то Х(Ш) является единственной предельной точкой при данном
Приведенная теорема дает условия для сходимости с вероятностью I последовательности величин X fu/J и точкам множества л Она показывает, что для этого достаточно проверить, что эта последовательность является случайной квазифейеровской относительно множества А и что хотя бы одна ее предельная точка с вероятностью I принадлежит множеству А .
Введение понятий случайных фейеровских и квазифейеров-ских последовательностей позволило распространить на стохастический случай методы фейеровских приближений, примененных в работе /27/ к исследованию задач выпуклого программирования.
Свойства случайных квазифейеровских последовательностей, собранные в вышеприведенной теореме дают по существу универсальный метод доказательства сходимости процедур стохастической ашгроксимации в случае выпуклых функций регрессии.
В случае невыпуклых функций регрессии исследование процедур удобно проводить с помощью сформулированных в /28/ условий сходимости алгоритмов стохастического программирования. Они будут приведены в 4 этой главы непосредственно перед доказательством сходимости предлагаемой процедуры.
Построение процедуры поиска экстремума функции регрессии с использованием метода наименьших квадратов
Во введении уже отмечалась связь между задачей исследования функции регрессии по результатам наблюдений в некоторой последовательности точек и задачей интерполирования функций ш набору ее значений. Там же обосновывалась целесообразность применения интерполяционных методов при решении задач стохастической аппроксимации. Наиболее перспективным представляется использование кубических сплайнов. Как известно, кубические сплайны - это кусочно-полиномиальные дважды непрерывно дифференцируемые функции /29/-/3I/ (заметим, что существование второй производной у фикции регрессии часто требуется в теоремах стохастической аппроксимации), они удобны при решении задач на электронных вычислительных машинах (невысокая степень многочленов, наличие пакетов программ для построения различных типов сплайнов), позволяют хорошо восстанавливать не только значения интерполируемых функций, но и значения их производных, имеются оценки для соответствующих уклонений и теоремы о сходимости сплайнов для различных классов последовательностей сеток
Рассмотренная в 3 настоящей главы модификация процедуры Кифера-Вольфовица допускает естественное усовершенствование: вместо построения прямой по методу наименьших квадратов можно использовать построение сплайна по результатам конечного числа наблюдений функции регрессии в точках XS- с его помощью произвести оценку производной F (А5уи осуществить переход от точки Xs.
Перейдем теперь к описанию соответствующей модифицированной процедуры. Пусть Л0 произвольные действительные числа, а последовательность случайных величин определяется формулой
Здесь, как и ранее, 5 - нормирующий множитель, / - положительное число, определяющее величину сдвига, a -A-s - случайная величина, являющаяся оценкой производной функции регрессии F(X) в точке Xs и заданная соотношением & (К).еош пил,. , / // -X/ / Cs ts в противном случае. (5,2) Здесь {Сs; s = о,у,і .J - последовательность положительных чисел, а кубический сплайн, построенный по набору значений случайных величин f(x) соответствующих точкам XS-A/ » sf+i - » Xs;tt$- его производная.
Тогда последовательность случайных величин Л5 (и?), определяемая соотношениями (5.1), (5.2), для почти всех их сходится к элементам множества JC точек минимума функции регрессии
Доказательство. Проводится аналогично доказательству теоремы 3.1 с учетом следующих замечаний.
Как известно, сплайн U(X) в формуле (5.2) является решением задачи минимизации функционала U(XJ представляет собой кусочно кубическую функцию на отрезке
Так как среди набора значений {ti9 і -0,1,..., Л имеется Xs, то (5.II) и (5.12) останутся справедливыми при замене в них t-L
Поэтому, как и в теореме 3.1, можно доказать, что последовательность величин Л$ , определяемая формулами (5.1), (5.2), является случайной квазифейеровской относительно множества X. » и» следовательно, множество предельных точек для { Xs(u ), S-0,4,...J не пусто почти для всехоТ, Далее устанавливается существование при почти всех ост предельной точки этого множества, принадлежащей А. , отку да и вытекает утверждение теоремы 5.1. Замечания.
1. Как и в 4, используя условия сходимости процедур стохастического программирования /28/, можно установить возможность применения алгоритма (5.1), (5.2) для минимизации невыпуклых функций регрессии (при этом последовательность F(K5(cO)) сходится с вероятностью I, и для почти всех ЦТ все предельные ТОЧКИ { Xs(C )js =0,4,.. Jnpn-надлежат множеству
2. Измерения f(X) функции F(%)производятся с ошибками, поэтому узловые условия являются излишне жесткими при построении сплайна и могут привести к существенным искажениям характера интерполируемой функции. Целесообразнее производить сглаживание экспериментальных данных; например, вместо интерполяционного сплайна использовать при оценивании производной функции регрессии в (5.2) сглаживающий кубический сплайн 0 доставляющий минимум функционалу Весовые коэффициенты p следует обратно пропорциональными средним разбросам при наблюдениях в точках Хк , например рк = У/б/с , где О к - дисперсия случайной величины /Wjc/.
Поведение процедуры с использованием метода наименьших квадратов при невыпуклых функциях регрессии
Во-первых, можно выделить область ( О, С ) "больших" значений функции, вне которой значения функции очень малы и не представляют практического интереса. При этом значение С при изменении условий эксперимента изменяется незначительно.
Во-вторых, на промежутке ( О , С ), имеются две экстремальные точки ZL и T2 , знание которых имеет исключительно большое значение для восстановления функции f(T) . Располагая точками fі, и Гд ш можем выделить интервалы монотонности, что позволяет значительно улучшить качество интерполяции и сглаживания.
При уменьшении числа проводимых наблюдений применение рассмотренного способа приводит к значительному ухудшению результатов: во-первых, как правило, наблюдаются заметные отклонения кривой Q L построенной при малых значениях N , от кривойр , построенной при больших N ; во-вторых, у кривой fi появляются на интервале ( О ; С ) "лишние" минимумы и максимумы, при этом определение истинных экстремумов и сглаживание становятся затруднительными.
Так, например, в нашем случае результаты обработки наблюдений, как правило, дают неудовлетворительные результаты (см., например, рис.2, где приведены данные оценивания без сглаживания; при этом сплошная ломаная соответствует N = 250, пунктирная - N = 89).
Проведение же большого числа наблюдений в нашем случае по целому ряду причин невозможно. В связи с этим был предложен другой путь решения рассматриваемой задачи.
Способ 2. Как уже отмечалось, этот способ ориентирован на применение методов стохастической аппроксимации. Предпосылки его применения заключены в отмеченных выше свойствах нормированной корреляционной функции изучаемого случайного процесса: прежде всего в наличии двух "больших" экстремумов и той роли, которую они играют в определении свойств восстанавливаемой функции. Рис. 2
Схема применения этого способа состоит в следующем.
С помощью модифицированных алгоритмов стохастической аппроксимации типа Кифера-Вольфовица находятся (разумеется, приближенно) экстремальные точки t и Тг , т.е. решается задача
Более точно: сначала, начиная с точки Т- О , решается задача минимизации - при этом вычисляется значение Т . Далее на отрезке Г Tjr ; С J решается задача максимизации - вычисляется значение 2 Подчеркнем, что здесь Т - не обязательно целое число, а функция К %) при нецелых Т доопределяется линейным образом (более подробно см, замечание I). Вычисляются значения р (Т) для Т 1,2,..., С с] . (см. также замечание 2).
На каждом из отрезков [0 ; Т± ] , С Тх , 7 и СЦ. С] проводится монотонное сглаживание (с сохранением непрерывности на всем отрезке С О ; С ] ).
Замечание I. При использовании метода стохастической аппроксимации для получения наблюдений функции К(Г) следует: при целом Г вычислить значение 5 (і+Г) (с) при некотором целом t ; при нецелом Т , используя наблюдения /(([?]) и/иСТЗ + і) , провести линейную интерполяцию. Значения L при этом следует выбирать таким образом, чтобы последовательно используемые наблюдения над функцией К (Т) были слабо коррелированными и весь объем выполненных наблюдений (Л , .. . , (Л/) использовался равномерно. Использование модифицированных алгоритмов, изложенных в данной работе, даже при небольших N позволит избежать быстрого зацикливания.
Замечание 2. Вместо вычисления jP( w по формулам (I) и (2) можно находить точки уровня функции fi(T) посредством решения уравнений о( Т) - (А для некоторого набора С 6 ( О; І) (например, d =0,9, 0,7, 0,5, 0,3).
