Методы оптимизации

     Шаг 2. Положить d = x[k+1] - xk и найти lym - оптимальное решение задачи минимизации f(x[k+1]+lym*d) при условии lym принадлежит E1. Положить y1= x[k+1]+lym*d, j=1, заменить k на k+1 и перейти к шагу 1. 

         3.2.Многомерный поиск, использующий производные.

     Пусть функция f(x) деференцируема в Еn . В этом разделе рассматривается итерационная процедура минимизации вида:

     xk = x[k-1] + lym[k]*dk, k=1,... , где направление убывания dk определяется тем или иным способом с учетом информации о частных производных функции f(x), а величина шага lym[k] >0 такова, что f(xk) < f(xk-1), k=1,2,....

     Так как функция предполагается дифференцируемой, то в качестве критерия останова в  случае бесконечной итерационной последовательности {xk }, как правило, выбирают условие ||grad(f(xk))||<eps, хотя, разумеется, могут быть использованы и другие критерии.

     Метод наискорейшего спуска

     При использовании метода наискорейшего  спуска на каждой итерации величина шага а_k выбирается из условия минимума функции f(x) в направлении спуска, т. е.  
f(x[k] –a_kf’(x[k])) = f(x[k] – af'(x[k])).

     Это условие означает, что движение вдоль  антиградиента происходит до тех  пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции  
j(a) = f(x[k] - af'(x[k])) .

     Алгоритм  метода наискорейшего спуска состоит  в следующем.

     1. Задаются координаты начальной  точки х[0].

     2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k]).

     3. Определяется величина шага  a_k, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

     4. Определяются координаты точки  х[k+1]:

     х_i[k+1] = x_i[k] – а_kf’_i(х[k]), i = 1 ,..., п.

     5. Проверяются условия останова  стерационного процесса. Если они  выполняются, то вычисления прекращаются. В противном случае осуществляется  переход к п. 1.

     В рассматриваемом методе направление  движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 1). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

     dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.

     

     Рис. 1. Геометрическая интерпретация метода наискорейшего спуска

     Градиентные методы сходятся к минимуму с высокой  скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

     

     мало  отличаются друг от друга, т. е. матрица  Н(х) хорошо обусловлена. Напомним, что собственными значениями l_i, i =1, …, n, матрицы являются корни характеристического уравнения

     

     Однако  на практике, как правило, минимизируемые функции имеют плохо обусловленные  матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

     

     Рис. 2.Овражная функция

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

     3.3.Методы, использующие сопряженные направления.

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

     Определение. Пусть H - симметрическая матрица порядка nxn. Векторы d1,..., dk называются H-сопряженными, или просто сопряженными, если они линейно независимы и di(t)Hdj = 0 при i != j, где di(t) - вектор строка.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЗАКЛЮЧЕНИЕ

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

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

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

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

     Литература:  

     1. Васильев Ф.П. Численные методы  решения экстремальных задач. - М.: Наука, 1980.

     2. Сухарев А.Г., Тимохов А.В., Федоров  В.В. Курс методов оптимизации. - М.: Наука, 1986.

     3. Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.

     4. Сеа Ж. Оптимизация. Теория  и алгоритмы. - М.: Мир, 1973.

     5. Зангвилл У. Нелинейное программирование. Единый подход. - М.: Сов. радио,1973.

     6. Банди Б. Методы оптимизации  (вводный курс). - М.: Радио и связь,1988.

     7. Компьютерное методическое пособие по методам параметрической оптимизации. МГТУ им. Баумана, 1997год.