close

Вход

Забыли?

вход по аккаунту

?

Grigoreva Minimizacija kvadratichnoy funkcii

код для вставкиСкачать
Федеральное агентство по образованию
Санкт-Петербургский государственный
архитектурно-строительный университет
Факультет ГС и ЖКХ
Кафедра прикладной математики и информатики
МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ
МИНИМИЗАЦИИ КВАДРАТИЧНОЙ ФУНКЦИИ.
ПРОБЛЕМЫ СХОДИМОСТИ
МЕТОДЫ РЕШЕНИЯ
ЗАДАЧИ МИНИМИЗАЦИИ
КВАДРАТИЧНОЙ ФУНКЦИИ.
ПРОБЛЕМЫ СХОДИМОСТИ
Методические указания
Методические указания
Составитель Григорьева Ксения Владимировна
Редактор А. В. Афанасьева
Корректор А. Г. Лавров
Компьютерная верстка Н. И. Печуконис
Подписано к печати 28.12.2009 . Формат 60×84 1/16. Бум. офсетная.
Усл. печ. л. 2,1. Уч.-изд. л. 2,3. Тираж 100 экз. Заказ 165. «С» 83
Санкт-Петербургский государственный архитектурно-строительный университет.
190005, Санкт-Петербург, 2-я Красноармейская ул., 4.
Отпечатано на ризографе. 190005, Санкт-Петербург, 2-я Красноармейская ул., 5.
Санкт-Петербург
2009
36
1
ОГЛАВЛЕНИЕ
УДК 519.6
Рецензент канд. физ.-мат. наук, доцент кафедры МТМСУ факультета
ПМ-ПУ СПбГУ Г. Ш. Тамасян
Методы решения задачи минимизации квадратичной функции.
Проблемы сходимости: метод. указания / сост. К. В. Григорьева; СПб.
гос. архит.-строит. ун-т. – СПб., 2009. – 36 с.
Рассматриваются основы теории и примеры решения задачи минимизации квадратичной функции в рамках курса «Численные методы. Практикум на
ЭВМ». В качестве методов решения задачи предлагается изучить следующие
алгоритмы: метод наискорейшего градиентного спуска, метод покоординатного спуска, метод сопряженных градиентов. Приведены примеры типовых расчетов. Методические указания предназначены для студентов специальности
«Прикладная математика» очной и заочной форм обучения.
Ил. 38. Библиогр.: 3 назв.
1. Постановка задачи. Вспомогательные сведения ....................... 3
2. Свойства квадратичной функции ............................................... 7
3. Методы спуска → градиентные методы → метод
наискорейшего градиентного спуска (МНГС) ............................. 9
3.1. Общий план методов спуска ................................................ 9
3.2. Выбор направления и шага спуска. Метод
наискорейшего спуска ....................................................... 10
3.3. Метод наискорейшего градиентного спуска .....................11
3.4. Критерий окончания итераций .......................................... 12
3.5. Геометрический смысл МНГС .......................................... 12
3.6. Сходимость и проблема «оврагов» .................................. 13
3.7. Примеры .............................................................................. 14
4. Метод покоординатного спуска (МПКС) ................................ 17
4.1. Геометрическая интерпретация ......................................... 17
4.2. Примеры .............................................................................. 18
5. Метод сопряженных градиентов (МСГ) ................................. 20
5.1. Алгоритм метода ................................................................. 20
5.2. Геометрическая интерпретация ......................................... 20
5.3. Примеры .............................................................................. 21
6. Типовой расчет ........................................................................... 22
7. Практическая реализация методов минимизации
квадратичной функции средствами Microsoft Office
Excel 2007 ....................................................................................... 23
Рекомендуемая литература ............................................................ 33
© Санкт-Петербургский государственный
архитектурно-строительный университет, 2009
2
35
1. ПОСТАНОВКА ЗАДАЧИ.
ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ
Пусть Rn – n-мерное евклидово пространство.
Определение
1.1.
Задача
минимизации
функции
f : (D ⊂ R n )→ R1 при условии x ∈ X ⊂ R n называется в общем
случае задачей нелинейного программирования. Ее стандартное
обозначение
f (x ) → min .
(1.1)
x∈ X ∩ D
Если f – линейная функция, а D и X – многогранники, то (1.1)
называется задачей линейного программирования, или линейной программой. Если f – квадратичная функция, а D и X – многогранники, то (1.1) называется задачей квадратичного программирования, или квадратичной программой.
Функция f называется целевой или минимизируемой функцией.
Если X = Rn, то тогда (1.1) называется задачей безусловной минимизации. Если X ≠ Rn, то – задачей условной минимизации.
Определение 1.2. Решением задачи (1.1) будем называть либо
пару (x*, f*), если существует конечная точка минимума x*, либо
пару ({xk)∞k=1, f*), где {xk)∞k=1 X – минимизирующая последовательность со свойством
f (x k )
→ f * :== inf {f (x ), x ∈ X } . ♣1
k →∞
Конечная точка минимума существует не всегда. Например,
для выпуклой функции f (x) = ex существуют конечный инфимум
f * = 0 и минимизирующая последовательность x k = −k , но нет
конечной точки минимума. Бывает, что нет и конечного инфимума. Например, если f(x) = ln(x), D = (0, +∞), то инфимум f* = –∞
доставляется минимизирующей последовательностью x k = 1 k .
Минимизирующая последовательность существует всегда.
*
Определение 1.3. Точка x ∈ X называется точкой глобального минимума функции f на множестве X, если для всех x ∈ X
выполняется неравенство
f (x* )≤ f (x ) .
(1.2)
1
Символ окончания утверждений различных типов, доказательств, а также
примеров, когда последующий текст не имеет наименования.
34
3
Значение f (x*) называется минимальным значением функции
*
f на X. Точка x ∈ X называется точкой локального минимума
функции f, если существует такая δ – окрестность Sδ этой точки,
что для всех x ∈ Sδ выполняется неравенство (1.2). Если имеет
место f (x*) < f (x) для всех x ∈ X \{x*} или для всех x ∈ Sδ \{x*}, то
x – точка строгого глобального или локального минимума соответственно. ♣
Рекомендуемая литература
1. Васильев, Ф. П. Численные методы решения экстремальных
задач / Ф. П. Васильев. – М., 1988.
2. Пшеничный, Б. Н. Численные методы в экстремальных задачах / Б. Н. Пшеничный, Ю. М. Данилин. – М., 1975.
3. Карманов, В. Г. Математическое программирование /
В. Г. Карманов. – М., 1986.
Рис. 1.1
На рис. 1.1 изображены глобальный (c), строгий локальный (d)
и нестрогие локальные x ∈ [a, b] минимумы.
В нелинейном программировании особую роль играют выпуклые функции, так как локальный минимум выпуклой функции
является глобальным минимумом, а строгая выпуклость обеспечивает еще единственность глобального минимума.
Определение 1.4. Функция f называется выпуклой на множестве X, если ∀ x, x ∈ X , λ ∈ [0, 1], выполняется неравенство
f (λx + (1 − λ )x ) ≤ λf (x ) + (1 − λ ) f (x ). ♣
(1.3)
Если в (1.3) заменить ≤ на < при λ ∈ (0, 1), то получим определение строго выпуклой функции. ♣
Геометрический смысл этого определения заключается в том,
что график функции f на отрезке выпуклости [x, x ] лежит ниже
хорды, соединяющей точки (x, f (x )) и (x, f (x )) (рис. 1.2).
Замечание. Выполнение неравенства (1.3) влечет выпуклость
области задания функции f, так как истинность неравенства (1.3)
означает, в частности, задание функции f в точке λx + (1 − λ )x ,
которая является точкой отрезка, соединяющего произвольные
точки x и x из области задания X. Неравенство (1.3) не может
быть истинным, если функция f не определена в этих точках. Если
множество X – несвязное, то обязательно найдется точка x ∈ X ,
для которой функция f не определена. ♣
4
33
Аналогично решим пример 3.2 (рис. 7.27–7.28).
Далее будет рассмотрена задача безусловной минимизации
квадратичной функции в пространстве столбцов Rn. Напомним
следующие определения.
Рис. 7.27
Рис. 1.2
Определение 1.5. Вектор-столбец из первых частных производных функции f (x)
T
Рис. 7.28
32
 ∂f (x ) ∂f (x )
∂f (x )

f ′(x ):= 
,
, ...,
∂x2
∂xn 
 ∂x1
называется градиентом функции f (x), а вектор-столбец
g (x) = – f ΄ (x) называется антиградиентом.
Определение 1.6. Точка x, для которой выполняется равенство
f ' (x) = 0, называется стационарной точкой функции f .
Определение 1.7. Множество точек Гс, для которых целевая
функция принимает постоянное значение f (x) = c, в случае n > 2
называется поверхностью уровня, а в случае n = 2 – линией
уровня. ♣
Например, функция z = f (x1 , x 2 ) задает в трехмерном пространстве некоторую поверхность, низшая точка которой, согласно определению 1.2, есть решение задачи минимизации (рис. 1.3).
Проведем несколько плоскостей вида z = const. Линиями уровня
будут проекции на плоскость Ox1x2 линий пересечения этих плоскостей с поверхностью.
Теорема 1.1. Если в точке x градиент не равен нулю, то он
перпендикулярен к проходящей через эту точку поверхности
уровня. ♣
5
Рис. 7.24–7.25
Протянув вторую строку (рис. 7.25) вниз и построив график,
получим рис. 7.26.
Рис. 1.3
В направлении антиградиента происходит наискорейшее убывание функции, т. е. если мы делаем шаг бесконечно малой длины
в некотором направлении (см. рис. 1.3), то наибольшее убывание
функции произойдет тогда, когда этот шаг совпадет по направлению с антиградиентом. Это свойство антиградиента лежит в
основе ряда итерационных методов минимизации функций.
Рис. 7.25
Рис. 7.26
6
31
2. СВОЙСТВА
КВАДРАТИЧНОЙ ФУНКЦИИ
Определение 2.1. Квадратичная функция есть сумма квадратичной формы xT Ax, линейной формы bTx и константы:
1 T
(2.1)
x Ax + b T x + c ,
2
где A – симметричная матрица порядка n, b ∈ R n , c ∈ R 1 .
Определение 2.2. Квадратичная форма xT Ax и матрица А называются положительно определенными (ПО), если xT Ax > 0
при любом x ≠ 0 . Если же ∀x x T Ax > 0, то они положительно
полуопределены (ППО). ♣
Поведение квадратичной формы можно определить собственными числами матрицы А.
Определение 2.3. Если выполнены условия Ax = λx , где
λ – число и x ≠ 0 , то столбец x называется собственным вектором матрицы A. Скаляр λ называется собственным числом матрицы A. ♣
Полный набор всех собственных чисел матрицы A будем обозначать через Eig(A), наибольшее собственное число – через EIG(A),
наименьшее – через eig(A). Собственные числа удовлетворяют
уравнению A − λE = 0 , т. е. Eig(A) есть набор из n корней характеристического полинома A − λE степени n, где E – единичная
матрица размерности n × n.
Теорема 2.1. Если матрица A симметрична, то из ее собственных векторов можно построить ортонормированный базис
S = (e1 , K , e n ) , ei ∈ E n , i = 1, n , в котором квадратичная форма
имеет вид
f (x ) =
Рис. 7.21
Аналогично получаем решение примера 3.2 (рис. 22П).
Рис. 7.22
3. МСГ
Для МСГ будем использовать ту же схему решения, что и в
МПКС. Изменится лишь формула в диапазонах, соответствующих направлению спуска pk (рис. 7.23 и 7.24).
 y1  n
 
x Ax = (y1, ... , yn) diag [Eig(A)]  K  = ∑ λ i y i2 ,
  i =1
 yn 
T
(2.2)
Рис. 7.23
где diag[Eig(A)] – диагональная матрица, по главной диагонали
которой находятся собственные числа матрицы А. При этом, если
T
из векторов ei составить матрицу S, то x = Sy, где y = (y1 , K , y n ) ,
yi – координаты вектора x в ортонормированном базисе S, а
diag[Eig(A)]= S T AS.
30
7
Следствие 2.1. Из (2.2) следует, что для ПО матрицы A необходимо и достаточно положительности ее собственных чисел, а
для ППО – их неотрицательности. ♣
Если обозначить через m положительную оценку снизу для
Eig(A) и через M – оценку сверху для EIG(A), то имеет место следующая система неравенств, определяющая ПО квадратичной
формы:
2
2
m > 0.
(2.3)
m x ≤ x T Ax ≤ M x ,
Теорема 2.2. Пусть f (x) – дважды дифференцируема, т. е.
f (x) ∈ C 2 R n . Для того чтобы функция f (x) была выпуклой, необходимо и достаточно, чтобы ее матрица вторых производных
f ′′(x ) была ППО. ♣
Таким образом, квадратичная функция (2.1), для которой выполняется (2.3), является выпуклой. Ее производные вычисляются по формулам f ′(x ) = Ax + b и f ′′(x ) = A , поэтому имеет место
следующая теорема.
Теорема 2.3. Если матрица A – ПО, то квадратичная функция
(2.1) имеет в Rn единственную точку минимума x*, удовлетворяющую системе линейных алгебраических уравнений (СЛАУ)
Ax* + b = 0.
Очевидно, что сходимость достигается за гораздо большее количество шагов (рис. 7.18).
( )
Рис. 7.18
2. МПКС
В МПКС используется антиградиент, но само направление
спуска принципиально другое, а именно: за направление спуска
берутся координатные оси. Иначе вычисляется и шаг спуска. За
исключением этих двух переменных все остальные сохраняют те
же формулы, что и для МНГС (рис. 7.19 и 7.20).
Рис. 7.19
Рис. 7.20
Окончательный результат имеет вид, как на рис. 7.21.
8
29
3. МЕТОДЫ СПУСКА → ГРАДИЕНТНЫЕ
МЕТОДЫ → МЕТОД НАИСКОРЕЙШЕГО
ГРАДИЕНТНОГО СПУСКА (МНГС)
Определение 3.1. Методами спуска называются итерационные методы, применяемые для решения задачи минимизации
функции нескольких переменных, для которых каждая итерация
(шаг) приводит к уменьшению значения целевой функции
f (x k +1 ) < f (x k ) ∀ k ≥ 0 .
Рис. 7.16
Для примера 3.2 (далее) на том же листе также применим алгоритм МНГС (рис. 7.17).
♣
(3.1)
В численных методах индекс итерации принято размещать
сверху справа от обозначения итеративной точки, если она – векторная величина. Это позволяет сохранить обозначения компонент вектора с помощью нижнего индекса.
3.1. Общий план методов спуска
1°. Выбирается начальное приближение – некоторая точка
x0. Целесообразно использовать всю имеющуюся информацию о
поведении целевой функции f (x ), чтобы выбрать x0 поближе к
точке минимума.
2°. Пусть приближение xk к точке минимума найдено и x k ≠ x * .
Выбирается направление спуска, т. е. вектор p k ≠ 0 , такой,
что для всех достаточно малых α > 0 справедливо неравенство
f (x k + αp k ) < f (x k ) (см. п. 3.2).
3°. Определяется величина шага спуска по направлению pk,
т. е. положительное число α k > 0 , для которого выполняется
неравенство
f (x k + α k p k ) < f (x k ) (см. п. 3.2).
4°. За очередное приближение к точке минимума принимается
x k +1 = x k + α k p k .
(3.2)
Рис. 7.17
5°. Проверяется выполнение критерия окончания итераций
(см. п. 3.4 для i = k + 1). Если критерий выполняется, то итерации
прекращаем и полагаем x * ≈ x k +1 . В противном случае возвращаемся к п. 2°.
28
9
∞
Определение 3.2. Последовательность точек {xk}k=0
в методе
спуска называют траекторией спуска.
3.2. Выбор направления и шага спуска.
Метод наискорейшего спуска
Способ выбора направления спуска pk определяет конкретный
численный метод, а различные алгоритмы вычисления шага спуска αk задают варианты этого метода.
Рассмотрим, каким образом выбирается направление pk, которое обеспечивает убывание целевой функции на бесконечно
малом положительном шаге α. Предполагая непрерывность первых частных производных целевой функции, разложим ее в ряд
Тэйлора в точке xk: f (xk + αpk) = f (xk) + α (f ΄ (xk), pk) + o(α), где
(...) – скалярное произведение. Тогда если
(f ΄ (xk), pk) < 0 ,
(3.3)
то f (xk + αpk) – f (xk) < 0. Таким образом, чтобы pk было направлением спуска, необходимо и достаточно, чтобы pk составляло
острый угол с антиградиентом.
Определение 3.3. Методы, основанные на выборе в качестве
направления спуска pk антиградиента gk или – βf ΄(xk), β > 0 , называются градиентными. ♣
Градиент, как правило, меняется при переходе из точки в точку, следовательно, меняется и направление наискорейшего убывания функции. Антиградиентное направление может не являться
наилучшим из возможных направлений спуска, поскольку всегда существует направление из текущей точки непосредственно в
точку минимума (см. рис. 1.3), но мы его не знаем.
Будем рассматривать следующий способ выбора шага. Введем
функцию одной скалярной переменной Fk(α) = f (xk + αpk) и определим αk, решая задачу одномерной минимизации
Fk (α ) → min
α ≥0
Выделив диапазон A7:Q7, потянем «крестик» вниз (рис. 7.14)
до тех пор, пока не появится в столбце М запись, запрограммированная нами, «корень получен за … шагов», где количество шагов
прописывается из столбца А (рис. 7.15).
Рис. 7.14
Для полноты картины нам требуется построить график перехода от итерации к итерации и в итоге – к искомой точке минимума. Для этого воспользуемся вкладкой «Вставка» – «мастер
диаграмм» – «точечная, на которой значения соединены отрезками». Заполнив диапазон значений координат x1 и x2, выделив соответственно диапазоны J6:J10 и K6:K10, мы получим
ломаную, изображенную на рис. 7.15. Через каждую вершину отрезков ломаной можно для наглядности условно провести линии
уровня поверхности, как на рис. 7.16.
(3.4)
аналитически, например, для квадратичной функции, либо какимлибо итеративным методом.
Разложим в ряд Тэйлора в точке xk функцию
f (xk + αpk) = f (xk ) + α (f ' (xk ), pk) + 1 α2(f '' (xk) pk, pk) + o (α2).
2
Рис. 7.15
10
27
Первую строку можно считать законченной, если в ячейке Q6
мы получим значение квадратичной функции в первом приближении, для чего в эту ячейку введем соответствующую формулу
(рис. 7.10).
Рис. 7.10
Во второй строке в ячейке A7 введем формулу «=A6 + 1», а в
диапазон B7:C7 – ссылку на приближение x, полученное в первой
строке (рис. 7.11).
В силу выпуклости квадратного трехчлена с ПО матрицей А
имеет место разложение
Fk (α) = f (xk + αgk) = f (xk) – α (gk, pk) + 12 α2(Apk, pk)
где при положительном старшем коэффициенте единственная
точка минимума αk ≥ 0 может быть найдена из необходимого
условия экстремума F'k (α) = – (gk, pk) + α(Apk, pk) = 0. Тогда, независимо от направления спуска pk, для квадратичной функции
решение задачи (3.4) αk имеет вид
(pk, gk)
α =
.
(Apk, pk)
k
(3.5)
Градиентный метод, в котором на каждой итерации используется шаг, являющийся решением задачи (3.4), был предложен в
1845 г. О. Коши и называется методом наискорейшего спуска.
Отметим, что минимум по направлению не является минимумом целевой функции, если направление не указывает на точку
минимума.
3.3. Метод наискорейшего градиентного спуска
Рис. 7.11
Далее выделим E6:Q6, в правом нижнем конце диапазона появится черный «крестик» (рис. 7.12), потянув за который вниз на
одну строку, мы получим заполненную вторую строку (рис. 7.13).
Опишем алгоритм метода наискорейшего градиентного спуска
для квадратичной функции (2.1). Пусть построена точка x k ∈ R n .
1°. Вычислим gk = – (Axk + b) ∈ R n – градиентное направление
спуска.
2°. Определим α k ∈ R1 – шаг метода в данном направлении –
из формулы (3.5) при условии, что g k ≠ 0 :
αk =
Рис. 7.12
(gk, gk )
.
(Agk, gk )
Очевидно, что при подстановке αk в (3.2) построенная точка
xk+1 удовлетворяет условию (3.1).
3°. Вычисляем следующую итерацию xk+1 по формуле (3.2).
Проверяется выполнение критерия окончания итераций (см.
(3.7)–(3.9) для i = k + 1). Если критерий выполняется, то итерации
прекращаем и полагаем x * ≈ x k +1 . В противном случае возвращаемся к п. 1°. Продолжая указанные построения, получим минимизирующую f (x) последовательность {xk}.
Рис. 7.13
26
(3.6)
11
3.4. Критерий окончания итераций
Критерием прекращения процесса вычислений на i-м шаге часто выбирается близость нормы градиента к нулю
( ) < ε.
f ′ xi
(3.7)
Помимо критерия (3.7) используются также
и
x i − x i −1 < ε 1
(3.8)
f (x i )− f (x i −1 ) < ε 2 ,
(3.9)
где ε, ε 1 , ε 2 – заданные положительные числа. Нередко используют различные их сочетания, например, требуют, чтобы одновременно выполнялись условия (3.8) и (3.9) или даже все три условия
(3.7)–(3.9).
3.5. Геометрический смысл МНГС
G2:G3, соответствующий вектору b, а в формуле «мумнож» заполняем поля ввода диапазоном C2:D3, соответствующим матрице А,
и транспонированным вектором начального приближения x0.
Заметим, что вместо аргументов и констант мы вводим ссылки на соответствующие ячейки, кроме того, ссылки на константы
необходимо «фиксировать» с помощью «горячей клавиши» F4,
чтобы впоследствии при вычислениях константы свои значения
не меняли.
После того как формула будет введена, произведем одновременное нажатие клавиш «Ctrl-Shift-Enter»1 и получим числовой
результат в диапазоне E6:F6.
Аналогично введем формулу шага спуска и следующего приближения x (рис. 7.7 и 7.8).
Рис. 7.7
Из начальной точки x0 осуществляем спуск перпендикулярно
линии уровня Г0 = {x | f (x) = f (x0)} в направлении антиградиента
g0 и движемся до тех пор, пока не будет достигнуто минимальное
на луче L0 = x | x = x0 + αg0, α ≥ 0} значение функции f (рис. 3.1).
Рис. 7.8
Критерий остановки процесса будем проверять в ячейке M6 с
помощью функции «Если» (рис. 7.9, поле ввода формулы).
Рис. 3.1
Из условия (3.4) получаем F'0 (α0) = (f ' (x0 +α0g0), g0) = (g1, g0),
α0 > 0. Это равенство означает, что направление g0 и, следователь12
Рис. 7.9
1
При работе с массивами вместо клавиши «Enter» всегда используется сочетание клавиш «Ctrl-Shift-Ebter»
25
Затем создадим «заготовки» для вычислений в виде комментариев «№», «xk», «gk», «αk», «xk+1», «||gk||» и «z» (рис. 7.4, где «№» –
номер итерации; «||gk||» – евклидова норма антиградиента; «z» –
значение квадратичной функции в точке минимума, а «gk», «αk»,
«xk+1» вычисляются по соответствующим формулам: антиградиента и (3.6), (3.2)).
но, луч L0 являются касательными к линии уровня Г1 = { x | f (x) =
= f (x1)} в точке x1. Из точки x1 проводят спуск в перпендикулярном линии уровня Г1 направлении g1, пока соответствующий луч
L1 не коснется в точке x2 линии уровня, проходящей через эту точку, и т. д.
В градиентных методах спуск происходит по нормали к линии
уровня, траектория спуска носит зигзагообразный характер и градиенты в любых двух последовательных точках ортогональны.
3.6. Сходимость и проблема «оврагов»
Рис. 7.4
Заполним ячейки A6, B6 и C6 (рис. 5): номер итерации – 1, начальное приближение – (0, 0).
Рис. 7.5
Выделим ячейки E6:F6, в поле ввода формулы (рис. 7.6) поставим знак «равно»1 и воспользуемся «мастером функций» (слева
вверху на рис. 7.6). Поскольку выделен диапазон по горизонтали,
а антиградиент – это вектор-столбец, то вызываем функцию транспонирования «трансп». В нее записываем знак «–» из формулы
антиградиента, открываем и закрываем скобки, в которых записываем функцию перемножения матриц «мумнож», воспользовавшись снова «мастером функций», к ней прибавляем диапазон
Градиентный метод сходится достаточно быстро, если для минимизируемой функции f (x) поверхности уровня близки к сферам (при n = 2 – к окружностям – см. рис. 3.1). Если же линии
уровня сильно вытянуты в каком-то направлении, то по нормали
к этому направлению целевая функция меняется значительно быстрее, чем вдоль направления. Такой характер целевой функции
называется овражным (рис. 3.2). «Дно оврага» к тому же может
быть искривлено.
Если начальная точка x0 попадает на «склон оврага», то направление градиентного спуска из этой и последующих точек
будет почти перпендикулярным ко «дну оврага», хотя надо бы
двигаться вдоль «дна оврага». Из-за малых шагов процесс практически останавливается вдали от точки минимума x*, поэтому
сходимость градиентного метода может быть очень медленной.
Рис. 3.2
Рис. 7.6
1
Со знака «=» начинается ввод любой вычислительной формулы.
24
Поверхностями уровня квадратичной функции (в случае ПО)
служат n-мерные эллипсоиды с центром в точке x*. В двумерном
13
случае графику ПО квадратичной формы соответствует поверхность, которая называется эллиптическим параболоидом. Линии
уровня этой поверхности – концентрические эллипсы. Каноническое уравнение эллипса x12 a12 + x 22 a 22 = 1 , где a1 и a2 – его поn
2
луоси. Перепишем выражение (2.2) в виде xT Ax = ∑ yi
i =1
(1 λ i ).
Очевидно, что длины полуосей эллипсоида (эллипса) обратно пропорциональны квадратным корням из собственных чисел.
Если одно собственное число много меньше всех остальных, то
ему соответствует полуось, длина которой много больше длин
других полуосей, т. е. эллипсоид (эллипс) будет иметь сильно вытянутую форму. Отношение длины большей оси к длине меньшей
оси равно ν (A) = EIG(A) eig(A) – числу обусловленности матрицы А. Очевиден вывод: чем отношение EIG(A) eig(A) больше,
тем ярче выражен овражный характер квадратичной функции,
тем медленнее сходимость метода.
Теорема 3.1. Пусть А – симметричная ПО матрица и минимизируется квадратичная функция (2.1). Тогда при любом выборе
начального приближения МНГС сходится к точке x* минимума
функции (2.1) со скоростью геометрической прогрессии, знаменатель которой
7. Практическая реализация методов
минимизации квадратичной функции
средствами Microsoft Office Excel 2007
Рассмотрим реализацию методов минимизации квадратичной
функции средствами Microsoft Office Excel 2007 на примерах 3.1
и 3.2.
Для начала откроем книгу программы Microsoft Office Excel
2007 и переименуем листы 1, 2 и 3 в «МНГС», «МПКС», «МСГ»
соответственно, как показано на рис. 7.1 и 7.2.
Рис. 7.1
q = (EIG(A) − eig(A)) (EIG(A) + eig(A)).
Причем если eig(A) и EIG(A) близки, т. е. EIG(A) eig(A) ≈ 1,
то q мало, тогда метод сходится достаточно быстро. Если же
EIG(A) > eig(A), то q ≈ 1 и следует ожидать медленной сходимости метода.
Теорема 3.2. Оценка расстояния от произвольной точки
x k ∈ R n до точки минимума x* функции f (x) может быть представлена в виде
x k − x* ≤
1
Axk + b .
m
(3.10)
3.7. Примеры
Рис. 7.2
1. МНГС
На листе «МНГС» Книги 1 введем матрицу A, вектор b и соответствующие комментарии, как показано на рис. 7.3.
Пример 3.1. Решить задачу минимизации квадратичной функции f (x1 , x 2 ) = x12 + 2 x 22 − 4 x1 − 4 x 2 с помощью метода наискорейшего спуска.
Рис. 7.3
14
23
6. Типовой расчет
Пусть
−N 
 N
 N − 3
A = 
 ; b = 
 ,
 − N N + 1
 N + 5
где параметр N равен номеру студента по списку группы.
Создать программу реализации метода решения задачи минимизации (2.1). Построить линии уровня с указанием векторов
спуска. Метод определяется преподавателем.
Найти решение x* СЛАУ Ax + b = 0. Вывести точное x* и приближенное xk решение.
*
Сравнить x − x
k
k
с x −x
k −1
0
. Проверить вычисления при
различных начальных векторах x и проследить за зависимостью
k от x0. Указать скорость сходимости q.
 2 0
 симмет 0 4
Запишем функцию в виде (2.1), где матрица A = 
ричная A = AT и ПО (λ 1 = 2, λ 2 = 4 ), а вектор b = (− 4, − 4 )T . Заме2
2
тим, что f (x1 , x 2 ) = (x1 − 2 ) + 2(x 2 − 1) − 6 , поэтому точка миT
T
нимума x * = (2, 1) заранее известна. Пусть x 0 = (0, 0 ) – начальное приближение. Тогда
(g 0 , g 0 ) = 1 3 ,
T
gg00 ==−−((A
xAx
A
xAx00 ++bb))= (4, 4) , α 0 =
(AgAg00 , g 0 )
x 1 = x 0 + α 0 g 0 = (4 3 , 4 3) ,
T
A
xAx1 + b = 3232 3 ;
g 1 = −(A
xAx1 + b )== ((44 33,,−−44 33)) ,, αα11 ==11 33,,
TT
x 2 = x 1 + α 1 g 1 = (1616 9 , 8 9 ) ,
T
2
A
xAx2 + b = 3232 3 2 ;
g 2 = −(A
xAx2 + b )==((44 99,,44 99)) ,, αα11 ==11 33,,
TT
x 2 = x 1 + α 1 g 1 = (5252 2727 , 28
28 2727) ,
T
A
xAx2 + b = 3232 3 3 .
Заметим, что A
xAxkk + b = 3232 3 k k
→ 0 . Таким образом,
→∞
последовательность xk, полученная по МНГС, сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/3.
Траектория спуска представлена на рис. 3.3.
Рис. 3.3
Пример 3.2. Применение МНГС для минимизации квадратичой функции f (x1 , x 2 ) = x12 + 010 x 22 − 4 x1 − 4 x 2 с симметричной
22
15
2 0 
 (λ 1 = 2, λ 2 = 20) при x 0 = (0, 0 )T
и ПО матрицей A = 
20 
 0 20
дает последовательность приближений
(
)
g 0 = − Ax 0 + b = (4, 4 ) T , α 0 = 1 11,
x1 = x 0 + α 0 g 0 = (4 11, 4 11)T ,
(
Ax1 + b = 2 232 2 11;
)
Рис. 5.1
g = − Ax + b == ((3366 1111,,−−3366 1111)) , αα11 ==111111,,
1
1
(
x 2 = x1 + α1 g 1 = 8 0 112 , 8 112
(
) ((
),
T
TT ,
3
1
1
(
3
),
3 T
x = x + α1 g = 1204 1 1 , 412 1 1
)) , αα ==111111,,
3 TT
,
g 2 = − Ax 2 + b == 332244 11113 , ,332244 11113
2
2
нимума x , в ней вычислить антиградиент g2, β 1 = g 2
p 2 = g 2 + β1 p 1 и т. д.
Ax 2 + b = 2 234 2 112 ;
22
2
2 6
Ax +b = 2 3
5.3. Примеры
3
2 11 ;
... ... ... ... ...
A x k + b = 4 2 (9 1 1) k → 0 ,
k →∞
где x* = (2, 0.2)T. Траектория спуска изображена на рис. 3.4. Последовательность xk сходится здесь со скоростью геометрической
прогрессии, знаменатель которой q = 9/11, т. е. существенно медленнее, чем в предыдущем примере.
Пример 5.1. Применим метод сопряженных градиентов к квадратичной функции из примера 4.1 f (x ) = x12 + x1 x 2 + x 22 . Пусть
x0 = (0, 3)T, p0 = g0 = ( – 3, – 2 3)T, x1 = ( – 5 3/14, 4 3/14)T,
g1 = (6 3/14, – 3 3/14)T.
Сделаем второй шаг не по антиградиенту, а по сопряженному направлению p1. Вычислим β 0 = g 1
g0 =
9
142
. Далее
p1 = g1 + β0g0 = (75 3/142, – 60 3/142)T. Точка x2 на луче x1 + αp1
имеет координаты 3/14 ( – 5 + α2 75/14) и 3/14 ( 4 – α2 60/14).
При α2 = 14/15 обе координаты обращаются в нуль.
Согласно теореме 5.1, метод сопряженных градиентов при минимизации квадратичной функции дает точку минимума не более
чем за n шагов (у нас n = 2) независимо от выбора начальной
точки. Это означает, что направление p1 ведет в точку минимума
(0, 0)T.
Рис. 3.4
16
g1 и
21
5. МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ
(МСГ)
4. МЕТОД ПОКООРДИНАТНОГО СПУСКА
(МПКС)
5.1. Алгоритм метода
В этом методе в качестве очередного направления спуска
выбирается направление одной из координатных осей pk = ei =
= (0, ... , 0,1i, 0,...,0)T, а шаг спуска – по формуле (3.5).
Идея этого метода в том, чтобы на каждом шаге в качестве направления спуска использовать не антиградиент, а его линейную
комбинацию с прежним направлением спуска. Последовательность векторов спуска pk строится следующим образом:
0
0
1. p = g , т. е. первый шаг делается по антиградиенту;
k +1
k +1
k +1
k
gk ;
2. p = g + β k p , где β k = g
3. x k +1 = x k + α k p k , где αk находится из формулы (3.5),
k = 0, 1, 2 , ... .
Заметим, что при вычислении βk используются только градиенты, а для вычисления нового направления нужно помнить и
использовать старое направление, а не старый антиградиент. В
методе сопряженных градиентов новое и старое направления не
ортогональны.
Определение 5.1. Векторы называются сопряженными,
если они удовлетворяют условию (pi, Apj ) = 0 при любом i ≠ j ,
т. е. являются A-ортогональными. ♣
В случае минимизации положительно определенной квадратичной формы с матрицей A все направления спуска pi оказываются A-ортогональными, из чего и происходит название метода.
Теорема 5.1. Если целевая функция от n переменных представляет собой квадратичную форму, то алгоритм сопряженных
градиентов дает точку минимума не более чем за n шагов. ♣
Практически же в «овражных» случаях из-за неточности вычисления шага может потребоваться несколько больше шагов, в
некоторых случаях метод может зацикливаться.
4.1. Геометрическая интерпретация
Геометрический смысл метода состоит в движении в направлениях, параллельных координатным осям (рис. 4.1, а): точка (x0, y0)
описывает начальное приближение. Проводя спуск по координате x, попадем в точку (x1, y0). Двигаясь параллельно оси ординат,
придем в точку (x1, y1) и т. д. При движении вдоль координатной
оси идем до точки минимума, т. е. касания некоторой линии уровня.
а)
б)
Рис. 4.1
Сделав из начальной точки x0 шаг по методу наискорейшего
спуска, вычислим антиградиент g1 в новой точке x1 (рис. 5.1).
Будем использовать вместо антиградиента g1 направление
спуска p 1 = g 1 + β 0 g 0 , вдоль которого нужно дойти до точки ми-
Число шагов зависит от начального приближения и, главное, от
ориентации линий уровня относительно координатных осей. Так,
в задаче минимизации квадратичной функции при ориентации
осей эллипсов вдоль координатных осей достаточно однократного применения цикла. В овражных случаях при произвольной
ориентации относительно координатных осей даже в квадратичной задаче метод работает плохо (рис. 4.1, б).
20
17
5.2. Геометрическая интерпретация
4.2. Примеры
Пример 4.1. Рассмотрим функцию
f (x ) = x12 + x1 x 2 + x 22 ,
1 T
2 1
x Ax, где A = 
 . Собственные
2
1 2
числа матрицы A: λ 1 = 3; λ 2 = 1 . Вычислим собственные векторы
матрицы A:
1°. λ 1 = 3 ⇒
−1 1 
1

 x = 0; ⇒ − x1 + x 2 = 0; ⇒ X =  C , C ∈ E 1 , X = 2 .
 1 − 1
1
в матричном виде f (x ) =
2°. λ 2 = 1 ⇒
Рис. 4.2
1 1
1
1
1 1 x = 0; ⇒ x1 + x 2 = 0; ⇒ X =  − 1C , C ∈ E , X = 2 .


 
T
Ортонормированные собственные векторы e1 = 1 2 , 1 2
T
и e 2 = 1 2 , − 1 2 соответственно. Так как y = ε −1 x , а
2
2
Минимум достигается в точке x1 = – 1/2 и равен 3/4.
2°. Фиксируем x1 = – 1/2 и ищем минимум функции
3
1 1 
1
 x 2 −  +  x 2 +  , который достигается в точке x2 = 1/4
4
2
4
2
и равен 3/16. Получаем точку (–1/2, 1/4)T .
3°. Фиксируем x2 = 1/4 и находим x1 = – 1/8.
4°. Фиксируем x1 = – 1/8 и находим x2 = – 1/16. В точке (–1/8,
1/16) значение целевой функции равно 3/256. Так как | f (–1/8,
1/16) – f (–1/2, 1/4)| = 3/256 < 0,05, то процесс завершен.
МНГС из той же начальной точки (1, 1)T дает минимум за
T
одну итерацию, так как g0 = – (Ax0 + b)T = −(2 x1 + x 2 , x1 + 2 x 2 ) =
0
0
0
0
0
T
= (− 3, − 3) , и при α = (g , g ) / (Ag , g ) = 1/3 мы получаем точку
T
1
0
0
минимума x = x + α 0 g = (0, 0) .
С другой стороны, если взять за начальное приближение точку (0, 3 )T, которая лежит на той же линии уровня, что и точка
(1, 1)T, и первой изменять x2, а не x1, то покоординатный спуск
дает минимум за один шаг, в то время как наискорейший спуск
g0 = (– 3 , – 2 3 )T из точки (0, 3)T дает за одну итерацию точку
x1 = (– 5 3 /14, 4 3 /14)T, в которой целевая функция имеет значение 9/28. Если сделать еще один шаг по антиградиенту g1 = (6
3 /14, – 3 3 /14)T, то получим (при α1 = 5/6) точку (0, 3 3 /28)T,
значение целевой функции в ней равно 27/784. Таким образом,
после двух итераций по одной из координат отклонение от точки минимума составляет примерно 0,17, а по целевой функции –
примерно 0,034.
18
19
(
(
)
1
2
2
ε −1 = ε = 
1
то
Таким
y1 = 1
1
y = 
1
2
2
образом,
F (x ) =
1 2 ,

− 1 2 
1 2  x1  1
  = 
− 1 2  x 2  1
новые
2 (x1 + x 2 ) и y 2 = 1
)
2 (x1 + x 2 )
.
2 (x1 − x 2 )
переменные
2 (x1 − x 2 ), а
следующие:
1
(3 y12 + y 22 )= 3 (x1 + x 2 )2 + 1 (x1 − x 2 )2 .
4
4
2
Линии уровня целевой функции – эллипсы с центром в начале
координат, так как отсутствует линейная часть (рис. 4.2).
Зададим точность расчетов ε = 0,05.
T
1°. Пусть задана начальная точка x 0 = (1, 1) , f x 0 == 3. Фик-
( )
сируем x2 = 1 и решаем задачу
3
(x1 + 1)2 + 1 (x1 − 1)2 → min .
x1
4
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 129 Кб
Теги
minimizacija, kvadratichnoy, funkcii, grigoreva
1/--страниц
Пожаловаться на содержимое документа