Нелинейный метод наименьших квадратов Постановка задачи
|
Скачать 177.72 Kb.
|
|
2. H > 0 в точке *. Поэтому в качестве условий останова обычно фигурируют: а) малость изменения (относительного) целевой функции (Q( (l)) – Q( (l+1))) / Q( (l)) 1 ; б) малость относительного изменения параметров ; в) малость градиента Q (т.к. Q / = 0 в стационарной точке) || gl+1 || = 3 . Ни одно отдельно взятое условие останова не гарантирует достижения минимума. Так, если R1 , для Q(), имеющей горизонтальную точку перегиба ’, в этой точке выполнены условия останова a) и в), а если эта Q() быстро убывает, то в точке ” , расположенной на таком участке на склоне, выполнено условие останова б), но ни та, ни другая точка не является точкой локального минимума. Надёжным условием останова является совместное выполнение всех трёх критериев (при этом нужно согласовывать допуски 1, 2, 3 ). Вернёмся к рассмотрению допустимого шага. Для заданного направления рассмотрим f() = Q( + ) (индекс итерации для краткости опускаем). Пусть мы ещё не в точке минимума, так что градиент не равен нулю, || g || > 0. Имеем = g T . (8) При рассмотрении малой окрестности точки можно записать f() = Q( + ) f(0) + | = 0 = Q( ) + g T . Чтобы шаг был допустимым, требуется, чтобы Q( + ) < Q( ), т.е. g T должно быть меньше 0 при достаточно малых . Так как > 0, отсюда следует условие g T < 0 (9) (в допустимом шаге направление шага составляет с градиентом тупой угол). Теорема 4.1. Для того, чтобы шаг был допустимым, необходимо и достаточно выполнение условия = – R g , (10) где R R k x k , R > 0 . Доказательство (а) Достаточность . Покажем, что из (10) следует (9). Поскольку || g || > 0 , имеем g T = – g TR g < 0 . (б) Необходимость. Пусть g T < 0 . Покажем, что R I k – (11) требуемая матрица. Действительно, R = R T очевидно, и выполняется равенство – R g = – g + g+ = , т.е. (10). Покажем, что для всех z R k , || z || > 0 квадратичная форма z TR z > 0. Действительно, z TR z zTz – . –––––––––– ––––––––– Первое подчёркнутое слагаемое согласно неравенству Коши-Шварца : (|| z|| 2 || g || 2 - (z T g) 2 ) / || g || 2 , причём равенство реализуется при z = g. Но в этом случае второе слагаемое равно - 2( Tg) > 0 (согласно (9)). Напротив, если второе слагаемое z T равно 0, то z ортогонален , но при этом первое слагаемое больше 0, ибо оно равно 0 лишь при z = g , но тогда было бы g , что противоречит (9). Итак, различные допустимые методы отличаются видом матрицы R и способом выбора величины шага на итерациях. Таким образом, (l+1) = (l) – l R l g l , где l > 0, R l > 0 . (12) 1. Метод наискорейшего спуска. Согласно (10), = – R g , с R > 0 , || || = 1. Простейший способ выбора R – положить её единичной матрицей, с точностью до константы: R = = , (10’) т.е. направление шага выбирается по антиградиенту. Это метод наискорейшего спуска, предложенный Коши 150 лет назад. Величина шага в нём произвольна: = const > 0 (l+1) = (l) – l g l . (12’) Метод является допустимым, и значения целевой функции вдали от минимума уменьшаются довольно быстро. Но вблизи от точки * для функций с сильно вытянутыми линиями уровня, например, для функции (долины) Розенброка: Q() = 100 (2 – 1 2 )2 + (1 - 1 )2 итерации наискорейшего спуска приводят к шагам от борта к борту долины, так что количество итераций до достижения * = Arg min Q() велико, сходимость крайне медленная. Поэтому метод наискорейшего спуска редко используют при решении практических задач. 2. Метод Ньютона. Недостаток метода наискорейшего спуска в том, что он “видит ближайшую перспективу”, даваемую градиентом. Между тем, как вы знаете из теории дифференцируемых функций одной или нескольких переменных, поведение графика (поверхности) функции, радиус её кривизны определяются вторыми производными. Рассматривается квадратичное приближение для Q( ) : Q( ) Q( (l)) + ( – (l)) T g l + 1/2( – (l)) TH l ( – (l)) , (13) где H l R k x k матрица вторых производных Q( ) (матрица Гессе ). В качестве (l+1) принимается стационарная точка , т.е. решение уравнения Эйлера 0 = / gl + H l ( – (l)) (l+1) = (l)– H l -1 gl . (14) Шаг (14) будет допустимым, если H l > 0 . Но достаточным условием минимума является H l > 0 в точке минимума *, а так как H ( ) непрерывна, то в близкой окрестности * обеспечено H l > 0 . Таким образом, метод Ньютона будет допустимым вблизи * с R = H l -1, l = 1. Его достоинства: 1. Для квадратичной функции он сходится за одну итерацию. 2. Для не квадратичных функций он имеет максимальную скорость сходимости (квадратичную) среди общих градиентных методов [2] : || (l+1)|| const || (l)|| 2. Недостатки: 1. Не гарантировано выполнение условия H l > 0 вне близкой окрестности *. Нужны хорошие начальные оценки.
Чтобы не вычислять вторые производные целевой функции, но в то же время использовать быструю скорость сходимости метода Ньютона, в общих методах оптимизации были разработаны квази-ньютоновские методы, первый из которых – метод Дэвидона-Флетчера-Пауэлла (или переменной метрики). В этих методах последовательно (на итерациях) строятся приближения E(l) к матрице Гессе H , причём переход к следующему приближению E(l+1) производится путём обновления (модификации) матрицами С (l) ранга 1 или ранга 2 по формуле E(l+1) = E(l) + С (l) , где, например, для случая поправок ранга 1 С (l) = Const (b(l) - E(l) s(l)) (b(l) - E(l) s(l))T, а s(l) = (l+1) – (l) = (l), b(l) = g (l+1) - g (l) (обновление E(l+1) делается уже после вычисления нового приближения (l+1)). Таким образом, для вычисления очередного приближения E(l+1) требуются только первые производные целевой функции Q( ) для построения вектора b(l). Показано, что последовательность матриц {E(l)} сходится к H за конечное, довольно малое, число шагов. В качестве начального приближения можно брать единичную матрицу: E(1) = Ik . Из (14) ясно, что на каждом итерационном шаге метода Ньютона нужно вычислять обратную к матрице H матрицу, что требует O(n 3) флоп работы. При использовании вместо неё матрицы E(l+1) , например. в случае поправок ранга 1, можно использовать формулу Шермана-Моррисона (см., например, Голуб Г., Ван Лоун Ч. “Матричные вычисления” М.: Мир, 1999. Стр. 58): если матрица A R m x m , а u , v – векторы длины m, то (A + u v T ) – 1 = A – 1 – A – 1 u (1 + v T A – 1 u) – 1 v T A – 1. Если матрица A – 1 (у нас E(l)) уже вычислена, то обращение матрицы A + u v T (у нас E(l+1)) по формуле Шермана-Моррисона потребует всего лишь O(n 2) флоп. Таким образом, при использовании квази-ньютоновских методов не только не нужно вычислять вторые производные функции регрессии, но и обращение матрицы E(l+1) можно делать экономично. Более подробно материалы по теории и (что особенно ценно !) по практике оптимизации можно посмотреть в превосходной книге Гилл Ф., Мюррей У., Райт М. “Практическая оптимизация”. М.: Мир, 1985. При изложении метода МП в конфирматорном факторном анализе мы ещё вспомним квази-ньютоновские методы... Название “метод Ньютона” связано с задачей поиска изолированного корня x0 функции f(x), т.е. в простейшем одномерном случае ищется решение уравнения f(x) = 0. (*) Ньютон использовал (если излагать метод в современных обозначениях) линейное разложение по формуле Тейлора в окрестности точки t f(x) = f(t) +(x - t) = 0 , где точка x* расположена между x и t. Отсюда, если производная – гладкая функция, а точки x и t близки, можно взять производную в точке x = t , а не в x* и получить очередное приближение для корня x0 в виде: x = t - . (**) В многомерном случае x – вектор, – матрица, а операция деления заменяется в (**) на обращение этой матрицы и умножения результата обращения на x. Как мы видели, среди и необходимых, и достаточных условий минимума (само по себе оно – признак стационарной точки) – 0 = g( *) = Q / . Полагая в формуле (*) f = g (так что вместо нужно подставить H = ), придём к итерационному шагу типа (**) метода Ньютона, совпадающему с (14). |
Похожие:
 |
Постановка задачи Роботы — это физические агенты, которые выполняют поставленные перед ними задачи, проводя манипуляции в физическом мире. Управление... |
 |
Математические модели cae систем Описание и постановка прикладной задачи, реализованной в качестве дипломной работы. 33 |
|
Математические модели cae систем Описание и постановка прикладной задачи, реализованной в качестве дипломной работы. 33 |
|
Определение ориентации неподвижного объекта с помощью спутниковых радионавигационных систем В статье рассматривается постановка задачи определения ориентации. Описана модель, используемая для решения задачи. Приведен алгоритм... |
|
I. Обзор предметной области 1 Цель работы 6 Постановка задачи 6 Глава ... |
|
Отчет по лабораторной работе должен содержать следующие материалы... Аналитическое решение тестового примера и результат вычислительного эксперимента по тесту |
|
Программа по курсу: практикум по программированию в ядре Постановка задачи на драйвер kLogger. Базовая структура драйвера. Работа с файлами из режима ядра. Инициализация и выгрузка драйвера.... |
|
Отчет должны содержать следующие: заголовок или титульный лист, введение,... Спешу вам сообщить, что мы чуть не упустили такую замечательную вещь как курсовая работа |
|
Д. Е. Кочкин в статье рассматривается постановка задачи относительного... Применение математической модели вторых разностей фазовых измерений gps в задаче относительного местоопределения |
|
Робоча програма по дисципліні Чисельні методи Численные методы решения систем линейных алгебраических уравнений. Правило Крамера, метод обращения матрицы, метод Гаусса |