5.3. Концепция допустимости

Рассмотрим итерацию процедуры минимизации. Предположим, что, начиная с мы двигаемся в некотором направлении образующем луч:

Вдоль этого луча меняются значения целевой функции по мере изменения тем самым она оказывается лишь функцией Обозначим эту функцию

Ее производная по равна:

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

В дальнейшем будем предполагать, что

Величина называется производной от по направлению х в точке 0. Если отрицательна, то уменьшается при движении

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

Теперь можно доказать следующую теорему.

Теорема. Направление является допустимым тогда и только тогда, когда существует положительно-определенная матрица такая, что

Доказательство

1. Пусть некоторая положительно-определенная матрица, а направление задается равенством Тогда из равенства и из свойства положительной определенности матрицы следует:

2. Предположим теперь, что Выберем

Отсюда следует справедливость уравнения и матрица оказывается положительно-определенной (подробное доказательство мы предлагаем выполнить читателям в качестве упражнения).

Условие означает, что в направлении значения уменьшаются, если угол между этим направлением и градиентом больше 90°. В рассмотренной выше теореме констатируется, что это условие может быть выполнено, если направление определяется как Произведение отрицательного вектор-градиента на положительноопределенную матрицу в соответствии с равенством Метод минимизации, в котором направления движения находятся этим способом, называется допустимым градиентным методом (он был бы просто градиентным методом, если отказаться от требования положительной определенности матрицы Основное уравнение для итерации в любом градиентном методе записывается в виде

Разные градиентные методы отличаются друг от друга способом выбора

При разработке или выборе метода оптимизации всегда пытаются свести к минимуму общее время расчетов, требуемое для достижения минимума. Это время определяется главным образом следующими двумя факторами:

1) вычислениями значений функции и производной;

2) алгебраическими преобразованиями, такими, как обращение матрицы или вычисление ее собственных значений.

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

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