9.5. Методы, не использующие вычисления производных

9.5.1. Основные подходы к устранению необходимости вычисления производных.

Как уже отмечалось, существенным недостатком методов, изложенных в предыдущих параграфах, является необходимость подсчета производных а в методе Ньютона — и вторых производных на каждой итерации. При сложных функциях это, во-первых, оказывается утомительным с программистской точки зрения, а во-вторых, приводит к громоздким вычислениям на каждой итерации.

Возможно несколько способов избавления от необходимости подсчета производных:

использование методов прямого поиска (нулевого порядка), таких, как симплекс-метод, метод случайного поиска и т. п. [185], аппроксимация производных конечно-разностными аналогами, специальные методы аппроксимации матриц позволяющие реализовать итерационные процедуры, близкие по эффективности к процедурам Ньютона и Ньютона—Гаусса, но с меньшим объемом вычислений.

Прямые методы минимизации оказались малоэффективными для задач регрессионного типа даже по сравнению с градиентными методами [251. К тому же после отыскания с их помощью экстремальных значений В требуется проведение объемистых вычислений по нахождению статистических характеристик, описывающих качество оценок.

Конечно-разностная аппроксимация хотя и избавляет потребителя от утомительной работы по составлению дополнительных программ для вычисления производных, но не решает проблемы сокращения объема вычислений. Чаще всего она приводит к его заметному увеличению.

Наиболее перспективными и удобными оказались методы третьей группы. Они завоевали весьма прочное место во многих статистических пакетах (см., например, [169]).

9.5.2. Разностные аналоги метода Ньютона — Гаусса.

Основная идея, на которую опираются методы третьей группы, за ключается в использовании на (s + 1)-й итерации информации, полученной на предыдущих s итерациях, для построения разумных аппроксимаций элементов матрицы и компонент градиента

При решении регрессионных задач хорошо зарекомендовали себя методы, являющиеся, по существу, аппроксимациями метода Ньютона—Гаусса. По-видимому, работа [236] является в этом направлении пионерской. Упрощенный и непосредственно приспособленный к задачам регрессии алгоритм предложен в [242], см. также [1691. Достаточно подробный анализ алгоритмов подобного типа и их дальнейшее развитие содержатся в [37, 38]. Данную совокупность методов целесообразно назвать методами Ньютона—Гаусса без подсчета производных. Как и обычный метод Ньютона—Гаусса (см. п. 9.4.2), эти методы опираются на линейную аппроксимацию функций в окрестности точки

В отличие от метода Ньютона—Гаусса коэффициенты не совпадают с производными а подсчитываются по значениям функции полученным по прошлым итерациям. В принципе величины могут быть подсчитаны самыми различными способами, но в программах по регрессионному анализу оказывается очень удобным отыскивать их с помощью все того же мнк. Определим как решение задачи мнк:

где веса, описывающие вклад того или иного значения При этом s значений получены непосредственно из итерационной процедуры, а выбор остальных q значений параметров будет объяснен позднее. В частности, в алгоритме, предложенном в [242], , а остальные веса полагаются нулевыми.

Хорошие результаты дает выбор весов вида где — убывающая функция, например

Можно показать, что

где

Подставляя теперь в (9.2) приближенное значение функции (ср. с § 9.4), получим, что функция достигает своего минимума при , где

После несложных преобразований приходим к очень удобной в вычислительном плане формуле

где

Итерационная процедура Ньютона—Гаусса, опирающаяся на (9.18), принимает вид

Выбор осуществляется по одному из правил, принимаемых для процедуры Ньютона—Гаусса с переменным шагом.

Остановимся на некоторых особенностях процедуры (9.19). Ее основное достоинство состоит в том, что на каждом шаге до. статочно всего одного вычисления функции (естественно при всех . Данное свойство оказывается чрезвычайно полезным при сложных функциях , например, в тех случаях, когда эта функция удовлетворяет некоторому дифференциальному уравнению, допускающему лишь численное решение, для получения которого требуются специальные объемистые вычисления.

Процедура (9.19) содержит операцию обращения матрицы, от которой можно было бы избавиться, заменив ее обращением с помощью рекуррентных формул.

Однако, как правило, трудоемкость этой операции несущественна по сравнению с трудоемкостью подсчета значений функций .

В [242] утверждается, что вместо непосредственного обращения матрицы целесообразно использовать пошаговые процедуры, применяемые при отборе существенных факторов (см. гл. 8). Подобный прием особенно удобен при функциях «овражного» типа (матрица плохо обусловлена).

Для определения требуется подсчет функций по крайней мере в точке На последующих итерациях достаточно проведения подсчета функций лишь в одной точке Однако при плохо обусловленных матрицах рекомендуется использовать в (9.17) дополнительные значения функций, подсчитанные в точках . Таким образом, упоминавшееся ранее q равно Дополнительные точки рекомендуется располагать на направлениях, ортогональных к направлению, определяемому (9.17).

При линейной параметризации метод Ньютона—Гаусса без подсчета производных дает точное решение задачи мнк на первой итерации, если

На наш взгляд, выигрыш в объеме вычислений при переходе от итерационной процедуры (9.18) к более сложным процедурам весьма сомнителен ввиду резкого увеличения сложности расчетов на каждой итерации.

9.5.3. Некоторые замечания о выборе длины шага.

Один из главных недостатков изложенного метода состоит в следующем. Как показано ранее, существенным свойством квазиградиентных методов является возможность отыскания такого (может быть, достаточно малого) шага , в выбранном направлении, который приводит к уменьшению значения минимизируемой функции. Это имеет место всякий раз, когда направление минимизации составляет острый угол с антиградиентом. Выбор же направления в формуле (9.19) не гарантирует нам этого. Поэтому даже при малых мы будем не в состоянии уменьшить значение . В [242] предлагается попеременно для пробовать как положительные, так и отрицательные значения. Например, если задаться коэффициентом редукции , то можно положить , где тогда соответствует первому , для которого . Однако и эта процедура иногда может не привести к уменьшению функции, (например, в случае, когда направление минимизации ортогонально градиенту).

Тогда следующую точку можно искать методом случайного поиска, в окрестности данной

9.5.4. Разностные аналоги метода Ньютона.

В предыдущем пункте отправной точкой при конструировании итерационных процедур служила доступность. информации лишь о функциях . Иногда в регрессионных задачах оказывается сравнительно просто подсчитать производные Подчеркнем, что речь идет о непосредственном подсчете величины а не их разностных аналогов, которые требуют, по крайней мере вычисления функций Обращение к разностным формулам для вычисления делает применение изложенной ниже группы методов бессмысленным. Каждый шаг, ими определяемый, будет по трудоемкости близок к нескольким шагам из итерационных процедур, рассмотренных в п. 9.4.1 и 9.5.2.

По-видимому, наиболее известным из рассматриваемой группы методов является метод Дэвидона—Флетчера—Пауэлла. Идея, лежащая в основе данных методов, состоит в отыскании на каждом шаге направлений спуска, близких к направлению метода Ньютона, но без использования матрицы вторых производных.

Матрица аппроксимирующая матрицу . из метода Ньютона, может быть, например, выбрана как решение системы

где Н — симметричная матрица.

Решение системы (9.20) при неоднозначно, поэтому возможны различные способы конструирования матрицы Н Различные методы рассматриваемой группы отличаются способами конструирования этой матрицы и правилами выбора направлений , если они не определены однозначно. Матрица должна удовлетворять одновременно уравнениям (9.20) при всех

Приведем способы конструирования матриц для некоторых наиболее распространенных методов (см. [108, 115, 240, 211]):

а) метод сопряженных градиентов:

где матрицу часто выбирают единичной или диагональной с элементами

б) метод Дэвидона—Флетчера—Пауэлла:

в) измененный вариант метода Дэвидона—Флетчера—Пауэлла:

При квадратичной функции (в нашем случае — линейной параметризации) после шагов матрица Н, подсчитываемая любым из методов а)-в), в точности совпадает с матрицей определенной в п. 9.3. Иными словами, при в этом случае точное решение исходной экстремальной задачи будет заведомо получено за шагов. Если выбирается из условия наискорейшего спуска в направлении , то при выполнении не слишком ограничительных условий последовательность сходится при к со сверхлинейной скоростью независимо от выбора