в направлении
от точки
Следовательно, если
является достаточно малым положительным числом, шаг
будет допустимым. С другой стороны, при
не может существовать положительного значения
такого, чтобы
было допустимым шагом. Поэтому мы будем называть направление
допустимым в том случае, если
Теперь можно доказать следующую теорему.
Теорема. Направление
является допустимым тогда и только тогда, когда существует положительно-определенная матрица
такая, что
Доказательство
1. Пусть
некоторая положительно-определенная матрица, а направление
задается равенством
Тогда из равенства
и из свойства положительной определенности матрицы следует:
2. Предположим теперь, что
Выберем
Отсюда следует справедливость уравнения
и матрица
оказывается положительно-определенной (подробное доказательство мы предлагаем выполнить читателям в качестве упражнения).
Условие
означает, что в направлении
значения
уменьшаются, если угол между этим направлением и градиентом
больше 90°. В рассмотренной выше теореме констатируется, что это условие может быть выполнено, если направление определяется как Произведение отрицательного вектор-градиента на положительноопределенную матрицу в соответствии с равенством
Метод минимизации, в котором направления движения находятся этим способом, называется допустимым градиентным методом (он был бы просто градиентным методом, если отказаться от требования положительной определенности матрицы
Основное уравнение для
итерации в любом градиентном методе записывается в виде
Разные градиентные методы отличаются друг от друга способом выбора
При разработке или выборе метода оптимизации всегда пытаются свести к минимуму общее время расчетов, требуемое для достижения минимума. Это время определяется главным образом следующими двумя факторами:
1) вычислениями значений функции и производной;
2) алгебраическими преобразованиями, такими, как обращение матрицы или вычисление ее собственных значений.
Обычно эти факторы удается взаимно заменять. Метод, в котором применяются трудоемкие алгебраические процедуры, может потребовать меньшего числа итераций, а следовательно, и меньшего числа
расчетов целевой функции. Такой метод целесообразно использовать при сложном виде целевой функции. В задачах оценивания параметров целевая функция составляется из уравнений модели и результатов многих экспериментов. Вычисление этой функции обычно связано с большими затратами времени. Поэтому мы без всяких колебаний рекомендуем применять методы, сложные с алгебраической точки зрения, но зато эффективные в смысле требуемых вычислений значений функции и производной.