Метод наискорейшего спуска является градиентным методом с переменным шагом. На каждой итерации величина шага k выбирается из условия минимума функции f(x) в направлении спуска, т.е.
Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f (x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по функции
()=f (x (k) -f (x (k)))
Воспользуемся для этого методом золотого сечения.
Алгоритм метода наискорейшего спуска состоит в следующем.
Задаются координаты начальной точки x (0) .
В точке x (k) , k = 0, 1, 2, …, вычисляется значение градиентаf (x (k)).
Определяется величина шага k путем одномерной минимизации по функции
()=f (x (k) -f (x (k))).
Определяются координаты точки x (k) :
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Проверяется условие останова итерационного процесса:
||f (x (k +1))|| .
Если оно выполняется, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.
Рис. 2.1. Блок схема метода наискорейшего спуска.
Реализация метода в программе:
Метод наискорейшего спуска.
Рис. 2.2. Реализация метода наискорейшего спуска.
Вывод: В нашем случае метод сошёлся за 7 итераций. Точка А7 (0,6641; -1,3313) является точкой экстремума. Метод сопряженных направлений. Для квадратичных функций можно создать градиентный метод, при котором время сходимости будет конечным и равно числу переменных n.
Назовем некоторое направление исопряженными по отношению к некоторой положительно определенной матрице ГессаH, если выполняется:
Тогда т.е.. Значит при единичнойH, сопряженное направление означает их перпендикуляр. В общем же случае H неединичная. В общем случае сопряженность - это применение матрицы Гесса к вектору - означает поворот этого вектора на некоторый уголи его растяжение или сжатие.
А теперь вектору векторортогонален т. е. сопряженность это не ортогональность векторови, а ортогональность повернутого векторат.е.и.
Рис. 2.3. Блок-схема метода сопряженных направлений.
Реализация метода в программе: Метод сопряженных направлений.
Рис. 2.4. Реализация метода сопряженных направлений.
Рис. 2.5. График метода сопряженных направлений.
Вывод: Точка А3 (0,6666; -1,3333), была найдена за 3 итерации и является точкой экстремума.
3. Анализ методов определения минимального, максимального значения функции при наличии ограничений
Напомним, что общая задача условной оптимизациивыглядит так
f(x) ® min, x Î W,
где W - собственное подмножество R m . Подкласс задач с ограничениями типа равенств выделяется тем, что множество задается ограничениями вида
f i (x) = 0, где f i: R m ®R (i = 1, …, k).
Таким образом,W = {x Î R m: f i (x) = 0, i = 1, …, k}.
Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде
f 0 (x) ® min, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Если обозначить теперь через f функцию на R m со значениями в R k , координатная запись которой имеет вид f(x) = (f 1 (x), …, f k (x)), то (3.1)–(3.2)можно также записать в виде
f 0 (x) ® min, f(x) = Q.
Геометрически задача с ограничениями типа равенств - это задача о поиске наинизшей точки графика функции f 0 над многообразием (см. рис. 3.1).
Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f 0 при ограничениях f i (x) = 0, i = 1, ..., k (или решением задачи (3.1)–(3.2)), если при всех допустимых точкахx f 0 (x*) f 0 (x). (3.3)
Если (3.3)выполняется только для допустимыхx, лежащих в некоторой окрестности V x * точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.
Постановка задачи
Пусть дана функция f (х) R n
Требуется f (х) X = R n
Стратегия поиска
x k
} , k = 0,1,...,
таких, что 
, k = 0,1,...
. Точки последовательности {x k
} вычисляются по правилу
где точка х 0 задается пользователем; величина шага t k определяется для каждого значения k из условия
Решение задачи (3) может осуществляться с использованием необходимого условия минимума с последующей проверкой достаточного условия минимума . Такой путь может быть использован либо при достаточно простой минимизируемой функции , либо при предварительной аппроксимации достаточно сложной функции 
полиномом P(t k)
(как правило, второй или третьей степени), и тогда условие замещается условием , а условие условием 
Построение последовательности { x k }
заканчивается в точке x k
, для которой , где ε
- заданное малое положительное число, или k ≥ M
, где М
- предельное число итераций, или при двукратном одновременном выполнении двух неравенств 
, 
где ε 2
- малое положительное число. Вопрос о том, может ли точка x k
рассматриваться как найденное приближение искомой точки локального минимума x *
, решается путем дополнительного исследования.
Геометрическая интерпретация метода для n=2 на рис. 4.
Метод покоординатного спуска
Постановка задачи
Пусть дана функция f (х) , ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех его точках.
f (х) на множестве допустимых решений X = R n , т.е. найти такую точку , что
Стратегия поиска
Стратегия решения задачи состоит в построении последовательности точек {x k
} , k = 0,1,...,
таких, что , k = 0,1,...
. Точки последовательности {x k
} вычисляются по циклам в соответствии с правилом
(4)
где j - номер цикла вычислений; j = 0,1,2,...; k - номер итерации внутри цикла, k = 0,1,... ,n - 1; е k +1 , k = 0,l,...,n - 1 -единичный вектор, (k +1) -я проекция которого равна 1; точка х 00 задается пользователем, величина шага t k выбирается из условия
или 
.
Если выбранное условие при текущем t k
не выполняется, шаг уменьшается вдвое и точка 
вычисляется заново. Легко видеть, что при фиксированном j за одну итерацию с номером k
изменяется только одна проекция точки х jk
, имеющая номер k + 1
, а в течение всего цикла с номером j
, т.е. начиная с k = 0
и кончая k = n -1
, изменяются все п проекций точки х j0
. После этого точке х j n
присваивается номер х j + 1,0
, и она берется за начальную точку для вычислений в j + 1
цикле. Расчет заканчивается в точке х jk
при выполнении по крайней мере одного из трех критериев окончания счета: 
, или , или двукратного выполнения неравенств .
Полученные в результате вычислений точки могут быть записаны как элементы последовательности {х l }, где l=n*j+k - порядковый номер точки,
Геометрическая интерпретация метода для п = 2 приведена на рис. 5.
4. Метод Франка-Вулфа .
Пусть требуется найти максимальное значение вогнутой функции
При условиях
Характерной особенностью этой задачи является то, что ее система ограничений содержит только линейные неравенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, благодаря чему решение исходной задачи сводится к последовательному решению задач линейного программирования.
Процесс нахождения решения задачи начинают с определения точки, принадлежащей области допустимых решений за-
270
дачи. Пусть это точка X (k)
тогда в этой точке вычисляют градиент функции (57)
И строят линейную функцию
Затем находят максимальное значение этой функции при ограничениях (58) и (59). Пусть решение данной задачи определяется точкой Z (k)
. Тогда за новое допустимое решение исходной задачи принимают координаты точки X (k +1)
:
Где λ k - некоторое число, называемое шагом вычислений и заключенное между нулем и единицей (0< λ k < 1). Это число λ k берут произвольно или определяют
таким образом, чтобы значение функции в точке X (k +1) f(X (k +1)) , зависящее от λ k , было максимальным. Для этого необходимо найти решение уравнения и выбрать его наименьший корень. Если его значение больше единицы, то следует положить λ k =1 . После определения числа λ k находят координаты точки X (k +1) вычисляют значение целевой функции в ней и выясняют необходимость перехода к новой точке X (k +2) . Если такая необходимость имеется, то вычисляют в точке X (k +1) градиент целевой функции, переходят к соответствующей задаче линейного программирования и находят ее решение. Определяют координаты точки и X (k +2) и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.
Итак, процесс нахождения решения задачи (57) - (59) методом Франка-Вулфа включает следующие этапы :
1. Определяют исходное допустимое решение задачи.
2. Находят градиент функции (57) в точке допустимого решения.
3. Строят функцию (60) и находят ее максимальное значение при условиях (58) и (59).
4. Определяют шаг вычислений.
5. По формулам (61) находят компоненты нового допустимого решения.
6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.
Метод штрафных функций.
Рассмотрим задачу определения максимального значения вогнутой функции
f (х 1 , х 2 , .... х n) при условиях g i (х 1 , х 2 , .... х n) ≤ b i (i=l, m) , х j ≥ 0 (j=1, n) , где g i (х 1 , х 2 , .... х n) - выпуклые функции.
Вместо того чтобы непосредственно решать эту задачу, находят максимальное значение функции F(х 1 , х 2 , ...., х n)= f(х 1 , х 2 , ...., х n) +H(х 1 , х 2 , ...., х n) являющейся суммой целевой функции задачи, и некоторой функции
H(х 1 , х 2 , ...., х n) , определяемой системой ограничений и называемой штрафной функцией . Штрафную функцию можно построить различными способами. Однако наиболее часто она имеет вид
А a i > 0
- некоторые постоянные числа, представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. При этом координаты последующей точки находят по формуле
Из последнего соотношения следует, что если предыдущая точка находится в области допустимых решений исходной задачи, то второе слагаемое в квадратных скобках равно нулю и переход к последующей точке определяется только градиентом целевой функции. Если же указанная точка не принадлежит области допустимых решений, то за счет данного слагаемого на последующих итерациях достигается возвращение в область допустимых
решений. При этом, чем меньше a i
, тем быстрее находится приемлемое решение, однако точность определения его снижается. Поэтому итерационный процесс обычно начинают при сравнительно малых значениях a i
и, продолжая его, эти значения постепенно увеличивают.
Итак, процесс нахождения решения задачи выпуклого программирования методом штрафных функций включает следующие этапы:
1. Определяют исходное допустимое решение.
2. Выбирают шаг вычислений.
3. Находят по всем переменным частные производные от целевой функции и функций, определяющих область допустимых решений задачи.
4. По формуле (72) находят координаты точки, определяющей возможное новое решение задачи.
5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.
6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.
Метод Эрроу - Гурвица.
При нахождении решения задач нелинейного программирования методом штрафных функций мы выбирали значения a i , произвольно, что приводило к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи методом Эрроу - Гурвица, согласно которому на очередном шаге числа a i (k) вычисляют по формуле
В качестве начальных значений a i (0) берут произвольные неотрицательные числа.
ПРИМЕР РЕШЕНИЯ
Пример 1 .
Найти локальный минимум функции
Определение точки х k
1.Зададим .
2. Положим к = 0 .
3 0 . Вычислим
4 0 . Вычислим 
. Переходим к шагу 5.
5 0 . Проверим условие 
. Переходим к шагу 6.
6 0 . Зададим t 0 = 0,5 .
7 0 . Вычислим
8 0 . Сравним 
. Имеем 
. Вывод: условие для k = 0
не выполняется. Зададим t 0 = 0,25
, переходим к повторению шагов 7, 8.
7 01 . Вычислим .
8 01 . Сравним f (х 1) и f (х 0) . Вывод: f (x 1) < f (x 0) . Переходим к шагу 9.
9 0 . Вычислим
Вывод: полагаем k =1 и переходим к шагу 3.
3 1 . Вычислим
4 1 . Вычислим 
. Переходим к шагу 5.
5 1 . Проверим условие k ≥ M: k = 1 < 10 = M . Переходим к шагу 6.
6 1 . Зададим t 1 = 0,25.
7 1 . Вычислим
8 1 . Сравним f (х 2) с f (х 1) . Вывод: f (х 2) < f (х 1). Переходим к шагу 9.
9 1 . Вычислим
Вывод: полагаем k = 2 и переходим к шагу 3.
3 2 . Вычислим
4 2 . Вычислим . Переходим к шагу 5.
5 2 . Проверим условие k ≥ M : k = 2 < 10 = М , переходим к шагу 6.
6 2 . Зададим t 2 =0,25 .
7 2 . Вычислим
8 2 . Сравним f (х 3) и f (х 2) . Вывод: f (х 3) < f (х 2) .Переходим к шагу 9.
9 2 . Вычислим 
Вывод: полагаем k = 3 и переходим к шагу 3.
3 3 . Вычислим
4 3 . Вычислим . Переходим к шагу 5.
5 3 . Проверим условие k ≥ M : k = 3<10 = М , переходим к шагу 6.
6 3 . Зададим t 3 = 0,25.
7 3 . Вычислим
8 3 . Сравним f (х 4) и f (х 3) : f (х 4) < f (х 3) .
9 3 . Вычислим 
Условия выполнены при k = 2,3 . Расчет
окончен. Найдена точка
На рис. 3 полученные точки соединены пунктирной линией.
II. Анализ точки х 4 .
Функция 
является дважды дифференцируемой, поэтому проведем проверку достаточных условий минимума в точке х 4
. Для этого проанализируем матрицу Гессе .
Матрица постоянна и является положительно определенной (т.е. H > 0
) , так как оба ее угловых минора и положительны. Следовательно, точка 
есть найденное приближение точки локального минимума , а значение 
есть найденное приближение значения f (x *) =0
. Заметим, что условие H > 0
, есть одновременно условие строгой выпуклости функции 
. Следовательно, есть найденные приближения точки глобального минимума f (x)
и ее наименьшего значения на R 2
. ■
Пример 2
Найти локальный минимум функции
I. Определение точки х k , в которой выполнен по крайней мере один из критериев окончания расчетов.
1.Зададим .
Найдем градиент функции в произвольной точке
2. Положим к = 0 .
3 0 . Вычислим
4 0 . Вычислим . Переходим к шагу 5.
5 0 . Проверим условие 
. Переходим к шагу 6.
6° . Следующая точка находится по формуле
Подставим полученные выражения для координат в
Найдем минимум функции f(t 0) по t 0 с помощью необходимых условий безусловного экстремума:
Отсюда t 0 =0.24
. Так как 
, найденное значение шага обеспечивает минимум функции f(t 0)
по t 0
.
Определим 
7 0 . Найдем
8°. Вычислим
Вывод: полагаем k = 1 и переходим к шагу 3.
3 1 . Вычислим
4 1 . Вычислим 
5 1 . Проверим условие k ≥ 1: k = 1 < 10 = М.
6 1 . Определим
7 1 . Найдем 
:
8 1 . Вычислим
Полагаем k = 2 и переходим к шагу 3.
3 2 . Вычислим
4 2 . Вычислим
5 2 . Проверим условие k ≥ M: k = 2 < 10 = M .
6 2 . Определим
7 2 . Найдем 
8 2 . Вычислим
Полагаем k =3 и переходим к шагу 3.
3 3 . Вычислим
4 3 . Вычислим .
Расчет окончен. Найдена точка
II. Анализ точки х 3 .
В примере 1.1 (гл.2 §1) было показано, что функция f (x) является строго выпуклой и, следовательно, точках3 является найденным приближением точки глобального минимума х* .
Пример 3.
Найти локальный минимум функции
I. Определение точки x jk , в которой выполнен по крайней мере один из критериев окончания расчетов.
1. Зададим
Найдем градиент функции в произвольной точке 
2. Зададим j = 0.
3 0 . Проверим выполнение условия
4 0 . Зададим k = 0.
5 0 . Проверим выполнение условия
6 0 . Вычислим
7 0 . Проверим условие 
8 0 . Зададим
9 0 . Вычислим 
, где
10 0 . Проверим условие
Вывод: полагаем и переходим к шагу 9.
9 01 . Вычислим х 01 с шагом
10 01 . Проверим условие 
11 0 . Проверим условия
Полагаем k =1 и переходим к шагу 5.
5 1 . Проверим условие
6 1 . Вычислим
7 1 . Проверим условие
8 1 . Зададим
9 1 . Вычислим
10 1 . Проверим условие 
:
11 1 . Проверим условия
Полагаем k = 2 , переходим к шагу 5.
5 2 . Проверим условие . Зададим , переходим к шагу 3.
3 1 . Проверим условие
4 1 . Зададим k = 0.
5 2 . Проверим условие
6 2 . Вычислим
7 2 . Проверим условие
8 2 . Зададим
9 2 . Вычислим
10 2 . Проверим условие 
11 2 . Проверим условия
Полагаем k =1 и переходим к шагу 5.
5 3 . Проверим условие
6 3 . Вычислим
7 3 . Проверим условия
8 3 . Зададим
9 3 . Вычислим
10 3 . Проверим условие 
11 3 . Проверим условия
Зададим k = 2 и переходим к шагу 5.
5 4 . Проверим условие 
Полагаем j = 2, х 20 = х 12 и переходим к шагу 3.
3 2 . Проверим условие
4 2 . Зададим k =0 .
5 4 . Проверим условие
6 4 . Вычислим
7 4 . Проверим условие
8 4 . Зададим
9 4 . Вычислим
10 4 . Проверим условие , перейдем к шагу 11.
11 4 . Проверим условия
Условия выполнены в двух последовательных циклах с номерами j = 2 и j -1= 1 . Расчет окончен, найдена точка
На рис. 6 полученные точки соединены пунктирной линией.
В методе покоординатного спуска мы спускаемся по ломаной, состоящей из отрезков прямых, параллельных координатным осям.
II. Анализ точки х21 .
В примере 1.1 было показано, что функция f (х)
строго выпукла, имеет единственный минимум и, следовательно, точка 
является найденным приближением точки глобального минимума.
Во всех рассмотренных выше градиентных методах последовательность точек { x k } сходится к стационарной точке функции f (x) при достаточно общих предложениях относительно свойств этой функции. В частности, справедлива теорема:
Теорема. Если функция f (x) ограничена снизу, ее градиент удовлетворяет условию Липшица () и выбор значения t n производится одним из описанных выше способов, то, какова бы ни была начальная точка х 0 :
при .
При практической реализации схемы
k =1, 2, … n .
итерации прекращаются, если для всех i , i = 1, 2, ..., n , выполнены условия типа
,
где - некоторое заданное число, характеризующее точность нахождения минимума.
В условиях теоремы градиентный метод обеспечивает сходимость по функции либо к точной нижней грани (если функция f (х) не имеет минимума; рис. 7), либо к значению функции в некоторой стационарной точке, являющейся пределом последовательности {х к }. Нетрудно придумать примеры, когда в этой точке реализуется седло, а не минимум. На практике методы градиентного спуска уверенно обходят седловые точки и находят минимумы целевой функции (в общем случае - локальные).
ЗАКЛЮЧЕНИЕ
Выше были рассмотрены примеры градиентных методов безусловной оптимизации. В результате проделанной работы можно сделать следующие выводы:
1. Более или менее сложные задачи отыскания экстремума при наличии ограничений требуют специальных подходов, методов.
2. Многие алгоритмы решения задач с ограничениями включают минимизацию без ограничений как некоторый этап.
3. Различные методы спуска отличаются друг от друга способами выбора направления спуска и длины шага вдоль этого направления.
4. Нет пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
Реальные прикладные задачи оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека.
СПИСОК ЛИТЕРАТУРЫ
1. Косоруков О.А. Исследование операций: учебник. 2003
2. Пантлеев А.В. Методы оптимизации в примерах и задачах: учеб. Пособие. 2005
3. Шишкин Е.В. Исследование операций: учеб. 2006
4. Акулич И.Л. Математическое программирование в примерах и задачах. 1986
5. Вентцель Е.С. Исследование операций. 1980
6. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения. 1988
©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-07-02
Рис.3. Геометрическая интерпретация метода наискорейшего спуска. На каждом шаге выбирается так, чтобы следующая итерация была точкой минимума функции на луче L.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче:
Другими словами, выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 3). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
Числовые примеры
Метод градиентного спуска с постоянным шагом
Для исследования сходимости метода градиентного спуска с постоянным шагом была выбрана функция:
Из полученных результатов можно сделать вывод, что при слишком большом чаге метод расходится, при слишком малом сходится медленно и точчность хуже. Надо выбирать шаг наибольшим из тех, при которых метод сходится.
Градиентный метод с дроблением шага
Для исследования сходимости метода градиентного спуска с дроблением шага (2) была выбрана функция:
Начальное приближение - точка (10,10).
Использован критерий останова:
Результаты эксперимента отражены в таблице:
|
Значение параметра |
Значение параметра |
Значение параметра |
Достигнутая точность |
Количество итераций |
Из полученных результатов можно сделать вывод об оптимальном выборе параметров: , хотя метод не сильно чувствителен к выбору параметров.
Метод наискорейшего спуска
Для исследования сходимости метода наискорейшего спуска была выбрана функция:
Начальное приближение - точка (10,10). Использован критерий останова:
Для решения одномерных задач оптимизации использован метод золотого сечения.
Метод получил точность 6e-8 за 9 итераций.
Отсюда можно сделать вывод, что метод наискорейшего спуска сходится быстрее, чем градиентный метод с дроблением шага и метод градиентного спуска с постоянным шагом.
Недостатком методом наискорейшего спуска является необходимость решать одномерную задачу оптимизации.
При программировании методов градиентного спуска следует аккуратно относится к выбору параметров, а именно
- · Метод градиентного спуска с постоянным шагом: шаг следует выбирать меньше 0.01, иначе метод расходится (метод может расходится и при таком шаге в зависимости от исследуемой функции).
- · Градиентный метод с дроблением шага не очень чувствителен к выбору параметров. Один из вариантов выбора параметров:
- · Метод наискорейшего спуска: в качестве метода одномерной оптимизации можно использовать метод золотого сечения (когда он применим).
Метод сопряжённых градиентов - итерационный метод для безусловной оптимизации в многомерном пространстве. Основным достоинством метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов. Поэтому, сначала описывается метод сопряжённых градиентов для оптимизации квадратичного функционала, выводятся итерационные формулы, приводятся оценки скорости сходимости. После этого показывается, как метод сопряжённых обобщается для оптимизации произвольного функционала, рассматриваются различные варианты метода, обсуждается сходимость.
Постановка задачи оптимизации
Пусть задано множество и на этом множестве определена целевая функция (objective function) . Задача оптимизации состоит в нахождении на множестве точной верхней или точной нижней грани целевой функции. Множество точек, на которых достигается нижняя грань целевой функции обозначается.
Если, то задача оптимизации называется безусловной (unconstrained). Если, то задача оптимизации называется условной (constrained).
Метод сопряжённых градиентов для квадратичного функционала
Изложение метода
Рассмотрим следующую задачу оптимизации:
Здесь - симметричная положительно определённая матрица размера. Такая задача оптимизации называется квадратичной. Заметим, что. Условие экстремума функции эквивалентно системе Функция достигает своей нижней грани в единственной точке, определяемой уравнением. Таким образом, данная задача оптимизации сводится к решению системы линейных уравнений Идея метода сопряжённых градиентов состоит в следующем: Пусть - базис в. Тогда для любой точки вектор раскладывается по базису Таким образом, представимо в виде
Каждое следующее приближение вычисляется по формуле:
Определение. Два вектора и называются сопряжёнными относительно симметричной матрицы B, если
Опишем способ построения базиса в методе сопряжённых градиентов В качестве начального приближения выбираем произвольный вектор. На каждой итерации выбираются по правилу:
Базисные вектора вычисляются по формулам:
Коэффициенты выбираются так, чтобы векторы и были сопряжёнными относительно А.
Если обозначить за, то после нескольких упрощений получим окончательные формулы, используемые при применении метода сопряжённых градиентов на практике:
Для метода сопряжённых градиентов справедлива следующая теорема: Теорема Пусть, где - симметричная положительно определённая матрица размера. Тогда метод сопряжённых градиентов сходится не более чем за шагов и справедливы следующие соотношения:
Сходимость метода
Если все вычисления точные, и исходные данные точны то метод сходится к решению системы не более чем за итераций, где - размерность системы. Более тонкий анализ показывает, что число итераций не превышает, где - число различных собственных значений матрицы A. Для оценки скорости сходимости верна следующая (довольно грубая) оценка:
Она позволяет оценить скорость сходимости, если известны оценки для максимального и минимального собственных значений матрицы На практике чаще всего используют следующий критерий останова:
Вычислительная сложность
На каждой итерации метода выполняется операций. Такое количество операций требуется для вычисления произведения - это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций. Суммарная вычислительная сложность метода не превышает - так как число итераций не больше n.
Численный пример
Применим метод сопряжённых градиентов для решения системы, где C помощью метода сопряжённых градиентов решение этой системы получается за две итерации. Собственные числа матрицы - 5, 5, -5 - среди них два различных, поэтому, согласно теоретической оценке число итераций не могло превышать двух
Метод сопряжённых градиентов - один из наиболее эффективных методов решения СЛАУ с положительно определённой матрицей. Метод гарантирует сходимость за конечное число шагов, а нужная точность может быть достигнута значительно раньше. Основная проблема заключается в том, что из-за накопления погрешностей может нарушаться ортогональность базисных веторов, что ухудшает сходимость
Метод сопряжённых градиентов в общем случае
Расссмотрим теперь модификацию метода сопряжённых градиентов для случая, когда минимизируемый функционал не является квадратичным: Будем решать задачу:
Непрерывно дифференцируемая в функция. Чтобы модифицировать метод сопряжённых градиентов для решения этой задачи необходимо получить для формулы, в которые не входит матрица А:
можно вычислять по одной из трёх формул:
1. - Метод Флетчера - Ривса (Fletcher-Reeves method)
- 2. - Метод Полака - Райбера (Polak-Ribi`ere method)
Если функция - квадратичная и строго выпуклая, то все три формулы дают одинаковый результат. Если - произвольная функция, то каждой из формул cоответствует своя модификация метода сопряжённых градиентов. Третья формула используется редко, так как она требует, чтобы функция и вычисления гессиана функции на каждом шаге метода.
Если функция - не квадратичная, метод сопряжённых градиентов может и не сходиться за конечное число шагов. Кроме того, точное вычисление на каждом шаге возможно только в редких случаях. Поэтому накопление погрешностей приводит к тому, что вектора перестают указывать направление убывания функции. Тогда на каком-то шаге полагают. Совокупность всех номеров, при которых принимается, обозначим за. Номера называются моментами обновления метода. На практике часто выбирают, где - размерность пространства.
Сходимость метода
Для метода Флетчера - Ривса существует теорема о сходимости, накладывающая не слишком жёсткие условия на минимизируемую функцию: Теорема. Пусть и выполняются следующие условия:
Множество ограничено
Производная удовлетворяет условию Липшица с константой в некоторой окрестности
множества M: .
Для метода Полака-Райбера доказана сходимость в предположении, что - строго выпуклая функция. В общем случае доказать сходимость метода Полака - Райбера невозможно. Напоротив, верна следующая теорема: Теорема. Предположим, что в методе Полака-Райбера значения на каждом шаге вычисляются точно. Тогда существует функция, и начальное приближение, такие что.
Тем не менее, на практике метод Полака-Райбера работает лучше. Наиболее распространённые критерии останова на практике: Норма градиента становится меньше некоторого порога Значение функции в течении m последовательных итераций почти не изменилось
Вычислительная сложность
На каждой итерации методов Полака-Райбера или Флетчера-Ривса по одному разу вычисляются функция и её градиент, решается задача одномерной оптимизации. Таким образом, сложность одного шага метода сопряжённых градиентов имеет тот же порядок, что и сложность шага метода скорейшего спуска. На практике метод сопряжённых градиентов показывает лучшую скорость сходимости.
Будем искать методом сопряжённых градиентов минимум функции
Минимум этой фнкции равен 1 и достигается в точке (5, 4). Сравним на примере этой функции методы Полака-Райбера и Флетчера-Ривса. Итерации в обоих методах прекращаются, когда на текущем шаге квадрат нормы градиента становится меньше. Для выбора используется метод золотого сечения
|
Метод Флетчера - Ривса |
Метод Полака - Райбера |
|||||
|
Число итераций |
Найденное решение |
Значение функции |
Число итераций |
Найденное решение |
Значение функции |
|
|
(5.01382198,3.9697932) |
(5.03942877,4.00003512) |
|||||
|
(5.01056482,3.99018026) |
(4.9915894,3.99999044) |
|||||
|
(4.9979991,4.00186173) |
(5.00336181,4.0000018) |
|||||
|
(4.99898277,4.00094645) |
(4.99846808,3.99999918) |
|||||
|
(4.99974658,4.0002358) |
(4.99955034,3.99999976) |
Реализовано два варианта метода сопряжённых градиентов: для минимизации квадратичного функционала, и для минимизации произвольной функции. В первом случае метод реализуется функцией vector
Методы градиентного спуска являются достаточно мощным инструментом решения задач оптимизации. Главным недостатком методов является ограниченная область применимости. В методе сопряжённых градиентов используется информация только о линейной части приращения в точке, как и в методах градиентного спуска. При этом метод сопряжённых градиентов позволяет решать квадратичные задачи за конечное число шагов. На многих других задачах метод сопряжённого градиента также превосходит метод градиентного спуска. Сходимость метода градиентов существенно зависит от того, насколько точно решается задача одномерной оптимизации. Возможные зацикливания метода устраняются с помощью обновлений. Тем не менее, если метод попадёт в локальный минимум функции, скорее всего, ему не удастся из него выбраться.
Аннотация: В данной лекции широко освещены такие методы многопараметрической оптимизации как метод наискорейшего спуска и метод Давидона – Флетчера – Пауэлла. Кроме того, проводится сравнительный анализ вышеперечисленных методов с целью определения наиболее действенного, выявляются их преимущества и недостатки; а также рассматриваются проблемы многомерной оптимизации, такие как метод оврагов и метод многоэкстремальности.
1. Метод наискорейшего спуска
Суть данного метода заключается в том, что с помощью упомянутого ранее метода покоординатного спуска осуществляется поиск из заданной точки в направлении, параллельном одной из осей, до точки минимума в данном направлении. Затем поиск производится в направлении, параллельном другой оси, и т.д. Направления, конечно, фиксированы. Кажется разумным попытаться модифицировать этот метод таким образом, чтобы на каждом этапе поиск точки минимума производился вдоль "наилучшего" направления. Не ясно, какое направление является "наилучшим", но известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство может быть обосновано следующим образом.
Предположим, что осуществляется перемещение из точки x в следующую точку х + hd , где d - некоторое направление, a h - шаг некоторой длины. Следовательно, перемещение производится из точки (x 1 , х 2 , ..., х n) в точку (x 1 + zx 1 , x 2 + zх 2 , ..., х n + zх n) , где
Изменение значений функции определяется соотношениями
| (1.3) |
С точностью до первого порядка zx i , причем частные производные вычисляются в точке x . Как следует выбрать направления d i , удовлетворяющие уравнению (1.2), чтобы получить наибольшее значение изменения функции df ? Здесь возникает задача максимизации с ограничением. Применим метод множителей Лагранжа, с помощью которого определим функцию
Величина df , удовлетворяющая ограничению (1.2), достигает максимума, когда функция
Достигает максимума. Ее производная
Следовательно,
 |
(1.6) |
Тогда di ~ df/dx i и направление d параллельно направлению V/(x) в точке х .
Таким образом, наибольшее локальное возрастание функции для заданного малого шага h имеет место, когда d есть направление Vf(x) или g(х) . Поэтому направлением наискорейшего спуска является направление
В более простом виде уравнение (1.3) можно записать так:
Где - угол между векторами Vf(x) и dx . Для заданной величины dx мы минимизируем df , выбирая , чтобы направление dx совпадало с направлением -Vf(x) .
Замечание . Направление градиента перпендикулярно в любой точке линии постоянного уровня, поскольку вдоль этой линии функция постоянна. Таким образом, если (d 1 , d 2 , ..., d n) - малый шаг вдоль линии уровня, то
И, следовательно,
 |
(1.8) |
Пример 6.8.3-1. Найти минимум функции Q(x,y) методом ГДШ.
Пусть Q(x,y) = x 2 +2y 2 ; x 0 = 2;y 0 = 1.
Проверим достаточные условия существования минимума:
Проделаем одну итерацию согласно алгоритму.
1. Q(x 0 ,y 0) = 6.
2.
При х = x 0 и y = y 0 , 
3. Шаг l k = l 0 = 0,5
Таким образом, 4 < 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.
Суть метода состоит в следующем. Из выбранной точки (x 0 ,y 0) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча (рис. 6.8.4-1). В найденной точке луч касается линии уровня. Затем из этой точки спуск проводится в направлении антиградиента (перпендикулярном линии уровня) до тех пор, пока соответствующий луч не коснется в новой точке проходящей через нее линии уровня, и т.д.
Выразим целевую функцию Q(x, y) через шаг l. При этом представим целевую функцию на определенном шаге как функцию одной переменной, т.е. величины шага
Величина шага на каждой итерации определяется из условия минимума :
Min( (l)) l k = l*(x k , y k), l >0.
Таким образом, на каждой итерации выбор шага l k предполагает решение задачи одномерной оптимизации. По способу решения этой задачи различают:
· аналитический метод (НСА);
· численный метод (НСЧ).
В методе НСА значение шага получают из условия , а в методе НСЧ величину l k находят на отрезке c заданной точностью, используя один из методов одномерной оптимизации.
Пример 6.8.4-1. Найти минимум функции Q(x,y)=x 2 + 2y 2 с точностью e=0.1, при начальных условиях: x 0 =2; y 0 =1.
Проделаем одну итерацию методом НСА .
=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .
Из условия ¢(l)=0 найдем значение l*: 
Полученная функция l=l(x,y) позволяет найти значение l. При x=2 и y=1 имеем l=0.3333.
Вычислим значения координат следующей точки:
Проверим выполнение критерия окончания итераций при k=1:
Поскольку |2*0.6666|>0.1 и |-0.3333*4|>0.1 , то условия окончания процесса итераций не выполнены, т.е. минимум не найден. Поэтому следует вычислить новое значение l при x=x 1 и y=y 1 и получить координаты следующей точки спуска. Вычисления продолжаются до тех пор, пока не выполнятся условия окончания спуска.
Отличие численного метода НС от аналитического состоит в том, что поиск значения l на каждой итерации происходит одним из численных методов одномерной оптимизации (например, методом дихотомии или методом золотого сечения). При этом в качестве интервала неопределенности служит диапазон допустимых значений l - .
