Лекция 23. Минимизация нелинейных функционалов

1. Как было отмечено ранее, применение на практике метода максимального правдоподобия или МНК может приводить к задаче отыскания минимума функции многих переменных. Например, станция слежения наблюдает искусственный спутник Земли и измеряет три координаты в сферической системе координат. Если обозначить параметры движения

ИСЗ через в некоторый момент времени то применение МНК для обработки выборки измерений сводится к минимизации

где

— вектор измерений в моменты времени (выборка измерений),

измерение в момент времени состоящее из нескольких измеряемых величин (например, - дальность, - азимут, - угол места в ской системе координат),

К - ковариационная матрица размера ошибок измерений, - вектор, компоненты которого вычислены по параметрам

Итак, мы пришли к задаче минимизации

функции (функционала) шести переменных

В общем виде, будем рассматривать задачу

где у - вектор - произвольная функция.

2. Рассмотрим один из наиболее распространенных методов решения задачи (23.3) - метод градиента. Этот метод представляет собой процесс последовательных итераций

где

k - номер итерации (шага),

- приближенное решение на шаге итераций,

- приближенное решение на шаге,

- некоторый коэффициент,

Для запуска процесса итераций (23.4) необходимо задать начальное приближение и сформировать критерий остановки

где - заданная точность.

Как выбрать коэффициент Я? Выбрать его, естественно, надо так, чтобы на направлении

функция достигла своего минимума:

Таким образом, мы имеем более простую задачу отыскания минимума функций одной переменной

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

При рассмотрении методов будем предполагать, что мы умеем определить такое, что на интервале функция имеет один минимум. Интервал назовем интервалом неопределенности [12].

2.1. Метод дихотомии.

Вычисляем в точках где - малое число, такое, что на интервале длиной функцию можно считать линейной.

Если то за новый интервал неопределенности принимаем если нет, то

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

Это означает, что мы нашли значение X, соответствующее минимуму с точностью до

Например, при имеем .

2.2. Метод Кифера.

Фиксируем допустимое число вычислений функции

Вычисляем числа Фибоначчи

и находим

Вычисляем в точке и в точке, симметричной относительно середины интервала неопределенности. Эту симметричную точку обозначим Если то новый интервал неопределенности если то интервал

Для нового выбранного интервала неопределенности формируем новые значения вычисляем и сравнивая эти значения, выбираем новый интервал неопределенности и т.д.

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

После вычислений функции мы имеем конечный интервал неопределенности

в предположении, что много меньше

Например, при При этом, интересно, Поэтому первое вычисление происходит в точке

2.3. Золотое сечение.

Пусть на интервале неопределенности каким-то образом выбрана точка и вычислено значение Вторая точка на этом интервале выбирается симметрично относительно середины интервала и вычисляется Далее выбираем в зависимости от неравенства или новый интервал неопределенности. На новом выбранном интервале будет известно значение или а следующее значение вычисляется в точке, симметричной относительно середины и т.д.

Пусть длина интервала неопределенности после к шагов равна Тогда из вышеизложенной процедуры выбора интервала неопределенности следует

Потребуем, чтобы на каждом шаге Тогда и (23.8) дает

Отсюда

Решая (23.10), получим

Отсюда, первое значение и далее симметрично относительно середины интервала и т.д. Такое деление отрезка называется “золотым сечением".

Если число вычислений функции то после вычислений мы имеем протяженность интервала неопределенности

При имеем

Сравнивая три рассмотренных метода, видим, что при одном и том же количестве вычислений наиболее точно определяет точку минимума метод Кифера (при далее метод золотого сечения и менее точно - метод дихотомии

3. Таким образом, возвращаясь к исходной задаче (23.4), на каждом шаге одним из рассмотренных методов вычисляем X как точку минимума на направлении и далее формируем новую точку и т.д.