WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
Федеральное агентство по образованию Санкт-Петербургский государственный архитектурно-строительный университет Факультет ГС и ЖКХ Кафедра прикладной математики и информатики МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ КВАДРАТИЧНОЙ ФУНКЦИИ.

ПРОБЛЕМЫ СХОДИМОСТИ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ КВАДРАТИЧНОЙ ФУНКЦИИ.

ПРОБЛЕМЫ СХОДИМОСТИ Методические указания Методические указания Составитель Григорьева Ксения Владимировна Редактор А. В. Афанасьева Корректор А. Г. Лавров Компьютерная верстка Н. И. Печуконис Подписано к печати 28.12.2009. Формат 6084 1/16. Бум. офсетная.

Усл. печ. л. 2,1. Уч.-изд. л. 2,3. Тираж 100 экз. Заказ 165. «С» 83 Санкт-Петербургский государственный архитектурно-строительный университет.

190005, Санкт-Петербург, 2-я Красноармейская ул., 4.

Отпечатано на ризографе. 190005, Санкт-Петербург, 2-я Красноармейская ул., 5.

Санкт-Петербург 2009 36 1 УДК 519.6 ОГЛАВЛЕНИЕ Рецензент канд. физ.-мат. наук, доцент кафедры МТМСУ факультета ПМ-ПУ СПбГУ Г. Ш. Тамасян 1. Постановка задачи. Вспомогательные сведения....................... 3 Методы решения задачи минимизации квадратичной функции.

2. Свойства квадратичной функции............................................... 7 Проблемы сходимости: метод. указания / сост. К. В. Григорьева; СПб.

3. Методы спуска градиентные методы метод гос. архит.-строит. ун-т. – СПб., 2009. – 36 с.

наискорейшего градиентного спуска (МНГС)............................. 9 3.1. Общий план методов спуска................................................ 9 Рассматриваются основы теории и примеры решения задачи минимизации квадратичной функции в рамках курса «Численные методы. Практикум на 3.2. Выбор направления и шага спуска. Метод ЭВМ». В качестве методов решения задачи предлагается изучить следующие наискорейшего спуска....................................................... 10 алгоритмы: метод наискорейшего градиентного спуска, метод покоординатно3.3. Метод наискорейшего градиентного спуска.....................го спуска, метод сопряженных градиентов. Приведены примеры типовых расчетов. Методические указания предназначены для студентов специальности 3.4. Критерий окончания итераций.......................................... «Прикладная математика» очной и заочной форм обучения.

3.5. Геометрический смысл МНГС.......................................... Ил. 38. Библиогр.: 3 назв.

3.6. Сходимость и проблема «оврагов».................................. 3.7. Примеры.............................................................................. 4. Метод покоординатного спуска (МПКС)................................ 4.1. Геометрическая интерпретация......................................... 4.2. Примеры.............................................................................. 5. Метод сопряженных градиентов (МСГ)................................. 5.1. Алгоритм метода................................................................. 5.2. Геометрическая интерпретация......................................... 5.3. Примеры.............................................................................. 6. Типовой расчет........................................................................... 7. Практическая реализация методов минимизации квадратичной функции средствами Microsoft Office Excel 2007....................................................................................... Рекомендуемая литература............................................................ © Санкт-Петербургский государственный архитектурно-строительный университет, 2 1. ПОСТАНОВКА ЗАДАЧИ.

ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ Пусть Rn – n-мерное евклидово пространство.

Определение 1.1. Задача минимизации функции x X Rn f : (D Rn) Rпри условии называется в общем случае задачей нелинейного программирования. Ее стандартное обозначение f (x) minD.

(1.1) xX Если 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), f*), где {xk) X – минимизирующая последовательk=1 k=ность со свойством k. f (x ) f* := inf{f (x), x X} = k Конечная точка минимума существует не всегда. Например, для выпуклой функции f (x) = ex существуют конечный инфимум f* = xk =, но нет и минимизирующая последовательность -k конечной точки минимума. Бывает, что нет и конечного инфимума. Например, если f(x) = ln(x), D = (0, +), то инфимум kf* = – доставляется минимизирующей последовательностью x = 1 k.

Минимизирующая последовательность существует всегда.

x* X Определение 1.3. Точка называется точкой глобальx X ного минимума функции f на множестве X, если для всех выполняется неравенство f (x*) f (x). (1.2) Символ окончания утверждений различных типов, доказательств, а также примеров, когда последующий текст не имеет наименования.

34 Значение f (x*) называется минимальным значением функции Рекомендуемая литература x* X f на X. Точка называется точкой локального минимума функции f, если существует такая – окрестность S этой точки, 1. Васильев, Ф. П. Численные методы решения экстремальных что для всех x S выполняется неравенство (1.2). Если имеет задач / Ф. П. Васильев. – М., 1988.



место f (x*) < f (x) для всех x X \{x*} или для всех x S \{x*}, то 2. Пшеничный, Б. Н. Численные методы в экстремальных за x – точка строгого глобального или локального минимума соот- дачах / Б. Н. Пшеничный, Ю. М. Данилин. – М., 1975.

ветственно. 3. Карманов, В. Г. Математическое программирование / В. Г. Карманов. – М., 1986.

Рис. 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) ление строго выпуклой функции.

Геометрический смысл этого определения заключается в том, [x, x] что график функции f на отрезке выпуклости лежит ниже хорды, соединяющей точки и (рис. 1.2).

(x, f (x)) (x, f (x)) Замечание. Выполнение неравенства (1.3) влечет выпуклость области задания функции f, так как истинность неравенства (1.3) означает, в частности, задание функции f в точке x + (1- )x, которая является точкой отрезка, соединяющего произвольные x точки x и из области задания X. Неравенство (1.3) не может быть истинным, если функция f не определена в этих точках. Если x X множество X – несвязное, то обязательно найдется точка, для которой функция f не определена.

4 Аналогично решим пример 3.2 (рис. 7.27–7.28). Далее будет рассмотрена задача безусловной минимизации квадратичной функции в пространстве столбцов Rn. Напомним следующие определения.

Рис. 7.Рис. 1.Определение 1.5. Вектор-столбец из первых частных производных функции f (x) T f (x), f (x),..., f (x) f (x):= x1 x2 xn называется градиентом функции f (x), а вектор-столбец g (x) = – f (x) называется антиградиентом.

Определение 1.6. Точка x, для которой выполняется равенство f ' (x) = 0, называется стационарной точкой функции f.

Определение 1.7. Множество точек Г, для которых целевая Рис. 7.с функция принимает постоянное значение f (x) = c, в случае n > называется поверхностью уровня, а в случае n = 2 – линией уровня.

Например, функция z = f (x1, x2 ) задает в трехмерном пространстве некоторую поверхность, низшая точка которой, согласно определению 1.2, есть решение задачи минимизации (рис. 1.3).

Проведем несколько плоскостей вида z = const. Линиями уровня будут проекции на плоскость Ox1x2 линий пересечения этих плоскостей с поверхностью.

Теорема 1.1. Если в точке x градиент не равен нулю, то он перпендикулярен к проходящей через эту точку поверхности уровня.

32 Рис. 7.24–7.Протянув вторую строку (рис. 7.25) вниз и построив график, получим рис. 7.26.

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

Рис. 7.6 2. СВОЙСТВА КВАДРАТИЧНОЙ ФУНКЦИИ Определение 2.1. Квадратичная функция есть сумма квадратичной формы xT Ax, линейной формы bTx и константы:

f (x)= xT Ax + bT x + c, (2.1) n Рис. 7.где A – симметричная матрица порядка n,,.

b R c RОпределение 2.2. Квадратичная форма xT Ax и матрица А называются положительно определенными (ПО), если xT Ax > Аналогично получаем решение примера 3.2 (рис. 22П).

x 0 x xT при любом. Если же Ax > 0, то они положительно полуопределены (ППО).

Поведение квадратичной формы можно определить собственными числами матрицы А.

Определение 2.3. Если выполнены условия Ax = x, где – число и x 0, то столбец x называется собственным вектором матрицы A. Скаляр называется собственным числом матрицы A.

Полный набор всех собственных чисел матрицы A будем обозначать через Eig(A), наибольшее собственное число – через EIG(A), Рис. 7.eig(A) наименьшее – через. Собственные числа удовлетворяют уравнению A - E = 0, т. е. Eig(A) есть набор из n корней характеристического полинома A - E степени n, где E – единичная матрица размерности n n.

3. МСГ Теорема 2.1. Если матрица A симметрична, то из ее собственных векторов можно построить ортонормированный базис Для МСГ будем использовать ту же схему решения, что и в n,, в котором квадратичная форма МПКС. Изменится лишь формула в диапазонах, соответствую- S = (e1, K, en ) ei E, i = 1, n имеет вид щих направлению спуска pk (рис. 7.23 и 7.24).

y1 n xT Ax = (y1,..., yn) diag [Eig(A)] (2.2) K = yi2, i yn i= где diag[Eig(A)] – диагональная матрица, по главной диагонали которой находятся собственные числа матрицы А. При этом, если T y = (y1,K, yn ) из векторов ei составить матрицу S, то x = Sy, где, yi – координаты вектора x в ортонормированном базисе S, а T Рис. 7.23 diag[Eig(A)]= S AS.

30 Следствие 2.1. Из (2.2) следует, что для ПО матрицы A необ- Очевидно, что сходимость достигается за гораздо большее коходимо и достаточно положительности ее собственных чисел, а личество шагов (рис. 7.18).

для ППО – их неотрицательности.

Если обозначить через m положительную оценку снизу для Eig(A) и через M – оценку сверху для EIG(A), то имеет место следующая система неравенств, определяющая ПО квадратичной формы:





M x, m > 0.

m x xT Ax (2.3) Теорема 2.2. Пусть f (x) – дважды дифференцируема, т. е.

f (x). Для того чтобы функция f (x) была выпуклой, неC (Rn) обходимо и достаточно, чтобы ее матрица вторых производных f (x) была ППО.

Рис. 7.Таким образом, квадратичная функция (2.1), для которой выполняется (2.3), является выпуклой. Ее производные вычисляют ся по формулам f (x)= Ax + b и f (x)= A, поэтому имеет место следующая теорема.

Теорема 2.3. Если матрица A – ПО, то квадратичная функция 2. МПКС (2.1) имеет в Rn единственную точку минимума x*, удовлетворяющую системе линейных алгебраических уравнений (СЛАУ) В МПКС используется антиградиент, но само направление Ax* + b = 0.

спуска принципиально другое, а именно: за направление спуска берутся координатные оси. Иначе вычисляется и шаг спуска. За исключением этих двух переменных все остальные сохраняют те же формулы, что и для МНГС (рис. 7.19 и 7.20).

Рис. 7.Рис. 7.Окончательный результат имеет вид, как на рис. 7.21.

8 3. МЕТОДЫ СПУСКА ГРАДИЕНТНЫЕ МЕТОДЫ МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКА (МНГС) Определение 3.1. Методами спуска называются итерационные методы, применяемые для решения задачи минимизации функции нескольких переменных, для которых каждая итерация (шаг) приводит к уменьшению значения целевой функции.

f (xk +1)< f (xk ) k 0 (3.1) В численных методах индекс итерации принято размещать Рис. 7.16 сверху справа от обозначения итеративной точки, если она – векторная величина. Это позволяет сохранить обозначения компонент вектора с помощью нижнего индекса.

Для примера 3.2 (далее) на том же листе также применим ал3.1. Общий план методов спуска горитм МНГС (рис. 7.17).

1°. Выбирается начальное приближение – некоторая точка x0. Целесообразно использовать всю имеющуюся информацию о f (x) поведении целевой функции, чтобы выбрать x0 поближе к точке минимума.

2°. Пусть приближение xk к точке минимума найдено и xk x*.

pk Выбирается направление спуска, т. е. вектор, такой, что для всех достаточно малых > 0 справедливо неравенство k f (xk + p )< f (xk ) (см. п. 3.2).

3°. Определяется величина шага спуска по направлению pk, т. е. положительное число > 0, для которого выполняется k неравенство k (см. п. 3.2).

f (xk + k p )< f (xk ) 4°. За очередное приближение к точке минимума принимается. (3.2) xk +1 = xk + k pk 5°. Проверяется выполнение критерия окончания итераций (см. п. 3.4 для i = k +1). Если критерий выполняется, то итерации прекращаем и полагаем x* xk +1. В противном случае возвращаемся к п. 2°.

Рис. 7.28 Определение 3.2. Последовательность точек {xk}k=0 в методе Выделив диапазон A7:Q7, потянем «крестик» вниз (рис. 7.14) спуска называют траекторией спуска. до тех пор, пока не появится в столбце М запись, запрограммированная нами, «корень получен за … шагов», где количество шагов 3.2. Выбор направления и шага спуска.

прописывается из столбца А (рис. 7.15).

Метод наискорейшего спуска Способ выбора направления спуска pk определяет конкретный численный метод, а различные алгоритмы вычисления шага спуска k задают варианты этого метода.

Рассмотрим, каким образом выбирается направление pk, коРис. 7.торое обеспечивает убывание целевой функции на бесконечно малом положительном шаге. Предполагая непрерывность пер- Для полноты картины нам требуется построить график перевых частных производных целевой функции, разложим ее в ряд хода от итерации к итерации и в итоге – к искомой точке миниТэйлора в точке xk: f (xk + pk) = f (xk) + (f (xk), pk) + o(), где мума. Для этого воспользуемся вкладкой «Вставка» – «мастер (...) – скалярное произведение. Тогда если диаграмм» – «точечная, на которой значения соединены отрезками». Заполнив диапазон значений координат x1 и x2, вы(f (xk), pk) < 0, (3.3) делив соответственно диапазоны J6:J10 и K6:K10, мы получим то f (xk + pk) – f (xk) < 0. Таким образом, чтобы pk было направ- ломаную, изображенную на рис. 7.15. Через каждую вершину отлением спуска, необходимо и достаточно, чтобы pk составляло резков ломаной можно для наглядности условно провести линии острый угол с антиградиентом. уровня поверхности, как на рис. 7.16.

Определение 3.3. Методы, основанные на выборе в качестве направления спуска pk антиградиента gk или – f (xk), > 0, называются градиентными.

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

Будем рассматривать следующий способ выбора шага. Введем функцию одной скалярной переменной Fk() = f (xk + pk) и определим k, решая задачу одномерной минимизации Fk () min (3.4) аналитически, например, для квадратичной функции, либо какимлибо итеративным методом.

Разложим в ряд Тэйлора в точке xk функцию f (xk + pk) = f (xk ) + (f ' (xk ), pk) + 1 2(f '' (xk) pk, pk) + o (2).

2 Рис. 7.10 Первую строку можно считать законченной, если в ячейке Q6 В силу выпуклости квадратного трехчлена с ПО матрицей А мы получим значение квадратичной функции в первом прибли- имеет место разложение жении, для чего в эту ячейку введем соответствующую формулу Fk () = f (xk + gk) = f (xk) – (gk, pk) + 1 2(Apk, pk) (рис. 7.10).

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.