Численные методы безусловной оптимизации. Метода параллельных касательных, метод Пауэлла
Метод Пауэла Метод ориентирован на решение задач с квадратичными целевыми функциями, т.е. функциями вида: f(x) = a + bTx + 1/2xTCx, где Q(x) = xTCx – квадратичная форма. Т.к. в окрестности точки оптимума любую нелинейную функцию можно аппроксимировать квадратичной функцией (поскольку линейный член разложения Тейлора обращается в нуль), то метод может быть применен и для нелинейной целевой функции общего вида. Метод Пауэлла использует свойство квадратичной функции, заключающееся в том, что любая прямая, которая проходит через точку минимума функции х*, пересекает под равными углами касательные к поверхностям равного уровня функции в точках пересечения. Метод Пауэла Суть метода заключается в следующем (Рассмотрим случай двух переменных). Выбирается некоторая точка х(0) и выполняется одномерный поиск вдоль произвольного направления, приводящий в точку х(1) (х(1) – точка минимума функции на выбранном направлении). Затем выбирается точка х(2), не лежащая на прямой х(0) – х(1), и осуществляется одномерный поиск вдоль прямой, параллельной х(0) – х(1). Находят точку х(3) – точку минимума функции на данном направлении. Точка х(3) вместе с точкой х(1) определяют направление х(1) – х(3) одномерного поиска, дающего точку минимума х*. Направления х(0) – х(2) и х(1) – х(3) являются сопряженными направлениями относительно матрицы С квадратичной формы Q(x) (C – сопряженные направления). Точно также сопряженными являются направления х(2)-х(3) и х(1)-х(3). В рассмотренных построениях для того, чтобы определить сопряженное направление, требовалось задать две точки и некоторое направление. Это не слишком удобно для проведения расчетов, поэтому предпочтительнее строить систему сопряженных направлений, исходя из одной начальной точки. Это легко осуществить при помощи единичных координатных векторов е(1), е(2), …, е(n). e(1) = (1, 0, …, 0)T; e(2) = (0, 1, …, 0)T; …; e(n) = (0, 0, …, 1)T. Проиллюстрируем процедуру построения сопряженных направлений для случая двух переменных (ее можно обобщить и для n-мерного пространства).
