Главная Методы условной оптимизации [0] [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] [ 28 ] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] В качестве такой оценки берут ф+-с, где Ф-оценка второй производной а -верхняя граница неизвестного множителя в выражении для ошибки условий. (Метод расчета величин Ф и С, использующий только значения функции, представлен в разд. 8.6.) В предположении, что величина Ф не равна нулю, искомый минимум достигается при (4.55) у Ф- Интересно посмотреть, каким будет интервал h для функции (4.54) из примера 4.5, если в роли Ф использовать точное значение второй производной Г (х), а С определить по точному значению ошибки условий. Оказывается, что при 1 величина h равна 4.497х Ю" (и попадает в диапазон, предсказанный на основе табл. 4а), а для x = 50 получим ft= 1.436х Ю". 4.6.1.3. Построение набора конечно-разностных интервалов. Результаты предыдущего раздела без изменений переносятся на многомерный случай, когда в процессе минимизации некоторой функции F ее градиент g{x) аппроксимируется в точке Xj вектором g{x, /-я компонента которого вычисляется по формуле Здесь нужен набор конечно-разностных интервалов {hj\. Строятся они независимо друг от друга на основе формулы (4.55), но, так как рса.пизация этой формулы (определение фигурирующих в ней величин С и Ф), описанная в разд. 8.6, предполагает вычисление функции по меньшей мере в двух дополнительных точках, обычно считагсгг нецелесообразным прибегать к ней на каждом шаге основного процесса. Процедуры типа представленной в разд, 8.6, как правило, используются только один раз - в нача.1ьной точке х. Обозначим через hj оценку оптимального конечно-разностного интервала для /-й переменной, вычисленную в х„. Величина hj представляет собой абсолютный интервал. Вводится и понятие относительного интервала. Набор относительных интервалов J6/I определяют так; 6, = 1 1ч-0/(дг„)уГ Здесь о--некий параметр, удовлетворяющий неравенству 0Оу<11, причем обычно Оу иолагагсгг равным единице. Опыт показывает, что оптимальные значения относительных интерва- лов устойчивее оптимальных значений абсолютных. Следовательно, если отказаться от расчета на каждом шаге оценок (4.55), то имеет смысл, определив набор {tj) по {й} в точке Хо, на последующих итерациях вычислять h/ по формуле Лу = 6/(1--а,.(хд)/). (4.56) Важно отметить, что фиксированного набора относительных интервалов, подходящего для всех точек, где в процессе поиска минимума придется аппроксимировать градиент, может не существовать. Поэтому на те редкие случаи, когда интервалы hj из (4,5.6) окажутся непригодными и в алгоритме минимизации из-за этого возникнут трудности, предусматривают возможность повторных обращений к формуле (4.55). 4.6.1.4. Выбор конечно-разностных формул. Как уже было сказано ранее, наиболее ходовым средством оценивания первых производных является правая конечно-разностная формула. Она требует вычисления лишь одного дополнительного значения функции на одну компоненту вектора градиента и там, где норма g(x) достаточно велика, обычно обеспечивает приемлемое качестю оценок. Однако по мере приближения к искомой точке безусловного минимума величина lg(x) стремится к нулю. Значит, даже при хорошо отмасштабированной функции и правильно выбираемых конечно-разностных интервалах правая аппроксимация рано или поздно теряет надежность. К сожалению, это обычно происходит задолго до того, как достигнута предельная точность решения задачи. Поэтому для завершающих итераций поиска минимума правая конечно-разностная формула может не подойти. Иногда от правой формулы приходится отказываться и на ранних итерациях, где от xi, до оптимума еще далеко. Ее следует заменять всякий раз, когда приращение функции при сдвиге /-Й компоненты вектора xj, на hj мало относительно hj: в данном случае возникающая при ее реализации ошибка условий обесцениваег результат вычисления. Более точная аппроксиматдая желательна и тогда, когда шаг спуска оказывается малым по сравнению с приращениями, используемыми для оценивания градиента. Если точности правой конечно-разностной аппроксимации не хватает, вместо нее можно использовать центральную аппроксимацию g(Xj), у-я компонента которой определяется по формуле 8l Ы = щ(Р (x + h,e,)-F (X,-V/))- (4.57) Для нее ошибка отбрасывания является величиной порядка Щ (см. разд. 2.3.5). Что же касается ошибки условий, то она останется пропорциональной Ijhj. При переключении с правой конечно-разностной аппроксимации на центральную, вероятнее всего, потребуется увеличить величины интервалов hj. Когда функция F хорошо отмасштаби-рована (в смысле определений разд. 8.7), разумной оценкой hj оптимального интервала центральной аппроксимации будет h, = (h,Yl\ Для центральной аппроксимации, как и для правой, целесообразно ввести набор относительных интервалов [bj\. Тогда, подобрав однажды значения \hj\ путем минимизации оценки суммарной ошибки и зафиксировав соответствующие величины {бу[, в дальнейшем можно вычислять Н/ для (4.57) по формулам, аналогичным (4.56). Когда градиент аппроксимируется по центральной конечно-разностной формуле, оценивание одной его компоненты требует двух дополнительных вычислений функции. Поэтому не стоит пользоваться центральной аппроксимацией там, где пригодна правая, и не стоит окончательно переключаться на нее до того, как поиск зайдет в малую окрестность решении и уровень ошибок праюй аппроксимации станет неприемлемым. Если же из-за плохих локальных свойств F к симметричной формуле придется прибегнуть в точке хд, далекой от решения, ю впоследствии рекомендуется вернуться к правой формуле. 4.6.2. КВЛЗИНЬЮТОНОВСКИЕ МЕТОДЫ БЕЗ ВЫЧИСЛЕНИЯ ПРОИЗВОДНЫХ Каждую схему из разд. 4.5 можно переделать в алгоритм минимизации без вычисления производных, заменив в ней настоящие градиенты их конечно-разностными оценками. Лучше всего для этой цели подходят квазиньютоновские схемы, рассмотренные в разд. 4.5.2. Будучи правильно реализованными, конечно-разностные квазиньютоновскне алгоритмы оказываются весьма эффектив-ньши и проявляют те же свойства устойчивости и быстродействия, что и их прототипы с точными производныли!. Однако было бы большим заблуждением думать, что хорошую процедуру аюжно получить простой комбинацией любого квазиньютоновского метода и какой-нибудь формулы аппроксимации градиента с фиксированными конечно-разностными интервалами (подразумевается замена всех значений градиентов, фигурирующих в квазиньютоновском методе, их конечно-разностными оценками без какой-либо модификации его логики вычислений). Во-первых, ошибки приближений производных могут существенно влиять на ход процесса минимизации, и, чтобы уменьшить их эффект, при построении алгоритма надо использовать рекомендации разд. 4.6.1. В частности, следует предусмотреть возможности смены формул аппроксимации и подбора значений конечно-разностных интервалов в зависимости от наблюдаемых характеристик минимизируемой функции. Во-вторых, для построения каждой численной оценки градиента потребуется п (или 2п) дополнительных вьмислеинй функций, и, стало быть, при переходе от обычного квазиньютоновского метода к конечно-разностному необходимо позаботиться о сокращении частоты вычисаения этих оценок. Это прежде всего означает, что процедуру выбора длины шага, предполагающую оценивание градиентов, нужно заменить другой, которой оно не требуется. Кроме того, как правило, придется повысить точность одномерного поиска: это ведет к сокращению числа итераций и тем самым к сокращению требуемого числа оценок градиента. Рис. 4п. Траектория поиска мин1(ыума функции Розенброка BFOS-методом с конечно-разностной аппроксимацией граднентов. На рис. 4п изображена траектория движения конечно-разностного квазиньютоноБСКого алгоритма при минимизации функции Розенброка (см. пример 4.2). Этот алгоритм был построен на основе BFGS-формулы пересчета квазиньютоновских матриц. Шаги по направлениям спуска определялись аккуратным одномерным поиском. Вдали от решения алгоритм ведет себя практически так же, как обычный BFGS-метод (ср. рис. 4т), но по мере приближения к нему начинает работать сравнительно хуже. Это объясняется тем, что здесь становятся существенными ошибки использованной в нем правой конечно-разностной формулы. Замечания и избранная библиография к разделу 4.6 Среди известных на сегодняшний день алгоритьюв минимизации гладких функций без вычисления производных есть много таких, которым не нужны численные оценки градиентов; их можно найти В работах Пауэлла (1964), Гринштадта (1972) и Брента (1973а). Однако в настоящее время считается, что конечно-разностные ква-вииьютоновские методы эффективнее. В числе первых публикаций по конечно-разностным квазиньютоновским методам следует назвать работу Стюарта (1967). Он предложил процедуру, в которой интервалы аппроксимации заново рассчитываются для каждого шага по формуле (4.55), причем оценка Ф строится по диагональным элементам DFP-приближения матрицы Гессе (см. (4.34)). Данный способ выбора Ф основан на предположении, что диагональные элементы квазиньютоновской матрицы хорошо оценивают порядки величин точных вторых производных. Метод построения интервала для центральной конечно-разностной формулы читатель найдет в работе Кертиса и Райда (1974). Вопросы использования конечно-разностных оценок в рамках оптимизационных процедур рассматриваются в статье Гилла и Мюррея (1972). Общую проблему определения приближенных значений производных с применением конечных разностей называют проблемой численного дифференцирования. Исследования по ней уже давно выделены в самостоятельную область вычислительной математики. Современный обзор методов численного дифференцирования (включающий достаточно полное обсуждение роли ошибок условий при реализации конечно-разностных формул на машине) содержится в работах Лайнесса (1977). По этой теме можно порекомендовать также работы Андерсена и Блюмфилда (1974), Дальквиста и Бьёрка (1974), Лайнесса и Молера (1967), Лайнесса и Сэнда (1971). Оливера и Раффхеда (1975) и Оливера (1980). В настоящее время существует много стандар ных программ численного дифференцирования. Они всегда нацелены на поиск конечно-разностного интервала, обеспечивающего минимальную суммарную ошибку вычисляемого приближения. Соответствующие алгоритмы выбора интервала для центральной конечно-разностной формулы описаны. Hi рнмер, у Дю онте и Виньеса (1977), Стиплмена и Винарски (1979) Однако для оптимизационных приложений подобные программы не подходят. Обеспечивая избыточную точность вычисления оценок производных, они обычно требуют слишком большого числа обращений к процедуре расчета значений функции. Замена настоящих градиентов их конечно-разностными оценками лучше всего проходит в квазиньютоновских методах. Для методов ньютоновского типа результаты получаются менее удовлетворительными. Теоретически построить ньютоновский алгоритм без вычисления производных нетрудно - достаточно в обычном алгоритме заменить и градиент, и матрицу Гессе нх конечио-разност-ньши приближениями (см. Миффлин (1975)). Однако с практической точки зрения такой подход в общем случае бесперспективен, поскольку на каждой ит рации требует вычисления О(п) дополнительных значений функции. К тому же здесь нужно особенно 4,7. Методы решения задан о наименьших квадратах тщательно подбирать конечно-разностные интервалы - ведь они должны обеспечивать приемлемую точность сразу двух оценок. Тем не менее, когда матрица Гессе разрежена, ньютоновские методы без вычисления производных иногда оказываются конкурентоспособными (см. разд. 4.8.1). 4.7. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ О НАИМЕНЬШИХ КВАДРАТАХ 4.7.1. ПРОИСХОЖДЕНИЕ ЗАДАЧ О НАИМЕНЬШИХ КВАДРАТАХ; ОСНОВАНИЯ ДЛЯ ИСПОЛЬЗОВАНИЯ СПЕЦИАЛЬНЫХ МЕТОДОВ Среди задач на поиск безусловного минимума особое место занимают задачи минимизаций функций F (х) вида (4.58) В этой записи f(x) - нелинейная векторная функция с т компонентами fi{x). Ее евклидову норму f(x)a называют невязкой в точке X. (Множитель 1/2 введен в (4.58), чтобы скомпенсировать двойку, возникающую при дифференцировании.) Задачи рассматриваемого типа возникают, например, при настройке математических моделей на реальные данные. Под математической моделью мы подразумеваем здесь функцию ц>(х, t) с независимым аргументом t и векторным параметром х. Предположим, что она сконструирована для предсказания значений некоторой величины у в зависимости от t, и пусть т фактических значений у при определенных t измерены. Результаты этих измерений, вообще говоря сопровождающихся ошибками, обозначим через У1, а соответствующие значения переменной t - через Тогда согласование модели с реальностью будет состоять в том, чтобы подобрать параметр х, при котором разности fi(x)=cf(x, t,)-у, «близки» к нулю. Один из способов формализации данной задачи - ставить ее как задачу поиска минимума суммы квадратов от fi{x). Если модель составлена правильно, можно ожидать, что величина и(х*)\\ окажется «малой», хотя количество наблюдений т обычно намного превосходит размерность п параметра х (при небольшом числе наблюдений хорошее согласование можно получить для любой модели). Функции (4.58) возникают и в несколько иной ситуации в случае, когда речь идет о настройке свободных параметров объекта, поведение которого описывается в непрерывном времени и от которого надо добиться траектории, близкой к заданной. Здесь нет измерений, сопровождающихся ошибками, и в качестве «ориентира» обычно дается непрерывная кривая. Естественная постановка [0] [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] [ 28 ] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] 0.0011 |