Консалтология Общая теория консалтинга (стр. 33 )

Пусть Х0 = (х1(0), …, хп(0)) — начальная точка поиска (рис. 9.4, а).

Рис. 9.4. Поиск экстремума квадратичной функции методом покоорди­натного спуска (а), методом параллельных касательных (б), методом наискорейшего спуска (в) и методом сопряженных градиентов (г)

Результат первой итерации X1 получается из Х0 при выполнении однопараметрической оптимизации по па­раметру x1, т. е.

Х1 = (х1(1), х2(0) …, хп(0)),

причем

Результат второй итерации Х2 получается из X1 путем оптимизации F(X) по параметру х2 и т. д. Далее процесс продолжается из точки Xп снова путем варьирования пара­метра х1 и т. д. Величину шага αk выбирают по способу оптимального шага.

Величина r за один цикл поиска равна размерности пространства, т. е. r = п.

Модификацией алгоритма покоординатного спуска яв­ляется метод ортогональных направлений (метод Розенброка), который основан на вращении системы координат в соответствии с изменением скорости убывания критерия оптимальности. При этом направление одной оси соответ­ствует наиболее вероятному направлению скорейшего убы­вания на данной итерации критерия оптимальности, а ос­тальные находятся из условия ортогональности.

Если в задаче оптимального консультирования поверх­ность отклика ограничена концентрическими эллипсоида­ми, то точное местоположение оптимума не более чем за (2п—1) одномерных итераций позволяет получить метод параллельных касательных. Идея этого метода для п=2 иллюстрируется на рис. 9.4, б.

Метод заключается в поис­ке центра системы концентрических эллипсов. Первона­чально определяют направление касательной π0 из точки Х0 к линии уровня (точка X1), затем строят произвольную прямую π1, параллельную π0, и на ней точку Х2, соответст­вующую точке касания π1 и линии уровня. Местоположе­ние центра X* определяется путем поиска вдоль линии X1X2.

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

Градиентные методы. Методы поиска, в кото­рых направление движения от итерации Xk-1 к Xk определяется градиентом (антиградиентом), вычисленным в точ­ке Xk-1, носят название градиентных методов.

Наиболее применяемым из методов минимизации является метод наискорейшего спуска. В большой степени широкому распространению метода способствуют его сравнительная простота и возможность применения для минимизации весьма широкого класса функций. При определении направления поиска выбирают наибыстрейшее убывание целевой функции F(Х), т. е.

Pk=-gradF(Xk-1).

Работа метода заключается в следующем. После опре­деления градиента критерия оптимальности в точке Xk движутся вдоль направления антиградиента до точки, в которой достигается минимальное значение функции. За­тем в этой точке снова определяют градиент и движутся по прямой согласно направлению нового антиградиента и т. д., пока не достигнут точки, имеющей наименьшее зна­чение функции F(X). На рис. 9.4, в приведен пример дви­жения при поиске методом наискорейшего спуска оптиму­ма для критерия оптимальности, зависящего от двух пере­менных. Направление

grad F(Xk-1) является касательным к поверхности уровня в точке Xk, и, следовательно, grad F(Xk) в точке Xk-1 ортогонален grad F(Xk-1).

Простейшим среди градиентных методов является метод, при котором движение из точки Xk-1 осуществляется по антиградиенту с постоянным шагом αk=const.

Если окажется, что F(Xk)>F(Xk-1), то для определе­ния экстремума используют один из возможных алгорит­мов поиска с возвратом. Так, в частности, поиск может производиться путем возврата в точку Xk-1 и дальнейшего перемещения из этой точки вдоль антиградиента с шагом α/2. Процедура дробления шага производится до тех пор, пока его значение не станет меньше некоторого малого положительного числа ε.

Описанные варианты реализации градиентного метода отличаются друг от друга способом выбора длины шага. Скорость сходимости этих методов примерно одинакова, а трудоемкость каждой итерации вариантов процесса (9.42) различна только в способах определения параметра αk. Как правило, вычисления градиента в меньшем числе то­чек требует метод наискорейшего спуска.

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

Метод сопряженных градиентов. В гради­ентных методах для поиска экстремума использовались свойства ортогональности векторов. В методе сопряжен­ных градиентов оптимум целевой функции ищется на основе свойств орготональности приращений вектора гради­ентов. Для этой цели наряду с градиентом используют матрицу Гессе Г критерия оптимальности. С помощью матрицы Г удается выбрать направление поиска, наиболее полно учитывающее особенности критерия оптимальности. Напомним, что векторы А и В называют сопряженными относительно симметричной и положительно определенной матрицы Г, если скалярное произведение векторов А и ГВ равно нулю, т. е. <А, ГВ>=0. Направление поиска Рk+1 на k+1-м шаге определяется как

где

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

Методы Ньютона и переменной метрики. Ускорение поиска экстремума связано с улучшением выбо­ра сопряженных направлений. Довольно эффективным яв­ляется поиск сопряженных направлений с одновременным накоплением информации о матрице Гессе критерия опти­мальности. Используют соотношение

которое является формулой метода Ньютона с регулиров­кой шага. Обычный метод Ньютона соответствует случаю αk=l.

Метод Ньютона с регулировкой шага сходится к реше­нию независимо от выбора начальной точки Х0 и обладает либо линейной, либо квадратичной скоростью сходимости в зависимости от вида функции F(X). В обычном методе Ньютона сходимость гарантируется лишь при наличии до­статочно хорошего начального приближения.

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

На основе метода Ньютона разработан эффективный метод, получивший название метода переменной метрики. Идея метода заключается в использовании информации о градиенте критерия оптимальности для приближенного вычисления матрицы Гессе. Этот метод — итерационный. Поиск в нем ведется по формуле

где Нk — приближенно вычисляемая обратная матрица Гессе; hk — величина шага, определяемая одномерной ми­нимизацией целевой функции на луче— Нk grad F (Xk).

Главное преимущество метода переменной метрики пе­ред методом Ньютона — отказ от вычислений матрицы Гессе на каждой итерации. Положительно определенная матрица

где ∆Xk-1 — приращение вектора переменных консультирования на предыдущем (k—1)-м шаге, имеет форму вектор-столбца; (∆Xk-1)T— транспонированный вектор ∆Xk-1, т. е. вектор-строка;

— вектор-строка.

В начале вычислений нужно задаться произвольной по­ложительно определенной матрицей Н0, в частности Н0 может быть единичной матрицей. Шаг hk выбирают по ме­тоду одномерной оптимизации.

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

Методы одномерной оптимизации. Эти методы позво­ляют найти оптимум для функций одной переменной. Они не требуют условия дифференцируемости критерия опти­мальности, а требуют только его непрерывности. Среди этих методов наиболее распространены методы чисел Фибоначчи, золотого сечения и полиномиальной аппроксимации. Для их применения необходимо знать интервал [а, b] переменной х, на котором функция F(х) имеет един­ственный минимум.

При применении метода чисел Фибоначчи должно быть зафиксировано число точек N, в которых производится вы­числение критерия оптимальности.