Методы оптимизации. Азарнова Т.В - 37 стр.

                                           39
      Даже для квадратичных           функций сходимость градиентных
методов за конечное число итераций не гарантирована. Однако если
квадратичная функция n переменных приведена к виду суммы полных
квадратов, то ее оптимум может быть найден в результате реализации n
одномерных поисков по преобразованным координатным направлениям.
Процедура преобразования квадратичной функции f ( x) =a +bx T + 12 xHx T к
виду суммы полных квадратов эквивалентна нахождению такой матрицы
преобразования Q, которая приводит матрицу квадратичной формы к
диагональному виду. Таким образом, заданная квадратичная форма xHx T
путем преобразования x=zQ приводится к виду xHx T = zQ T HQz T =zD z T ,
где D -диагональная матрица. Пусть q j −j - тая строка матрицы Q. Тогда
преобразование x= zQ позволяет записать каждый вектор x в виде линейной
комбинации векторов q j : x= zQ= z1q 1 +z 2 q 2 +.. +z n q n . Другими словами,
осуществляется переход к новой системе координат, задаваемой векторами
q j ( заметим, что это преобразование не является единственным). Таким
образом, с помощью преобразования переменных квадратичной функции
                            оординат, совпадающих с главными осями
квадратичной функции. Следовательно, одномерный поиск точки минимума
в пространстве преобразованных переменных эквивалентен поиску вдоль
каждой из главных осей квадратичной функции. Для полученной системы
векторов q j будут выполняться равенства q i H ( q j ) T =0, i ≠ j.
Определение. Система линейно независимых векторов q j , для которой
выполняются равенства q i H (q j ) T =0, i ≠ j , называется системой H-
сопряженных направлений.
     Итак, если заданы любые n H-сопряженных направлений q 1 , q 2 ..q n , то
процедура x k +1 =x k +α k q k , где α k = arg min f ( x k +α q k ) , k =1,2...n ,
                                                α
позволяет найти минимум квадратичной функции.
     Так как достаточно большой класс целевых функций может быть
представлен в окрестности точки минимума своей квадратичной
аппроксимацией, описанная идея применяется и для неквадратичных
функций.
      Построение системы H- сопряженных направлений возможно
различными способами. Рассмотрим некоторые из них.
               Метод сопряжённых направлений Пауэлла
     Итерационный процесс в методе Пауэлла организуется без
предварительного построения H- сопряженных векторов, которые
последовательно находятся в процессе минимизации с использованием
свойства параллельного подпространства.