Варианты метода сопряженных градиентов без точного линейного поиска

Плоткин Артем Владимирович

Варианты метода сопряженных градиентов без точного линейного поиска

Плоткин Артем Владимирович. Варианты метода сопряженных градиентов без точного линейного поиска. Научный руководитель В. Н. Малоземов. Направление математика, механика, кафедра исследования операций. Использовано 12 источников. В рамках работы проведен обзор и численное сравнение различных вариантов метода сопряженных градиентов. С помощью метода сопряженных градиентов решена задача о построении контрпримеров для неравенства Шапиро. Доказана теорема о сходимости геометрического варианта метода сопряженных градиентов при точном линейном поиске. Установлено свойство убывания целевой функции в геометрическом варианте метода сопряженных градиентов при неточном линейном поиске. Плоткин, А. В. Варианты метода сопряженных градиентов без точного линейного поиска: выпускная квалификационная работа бакалавра. / Плоткин Артем Владимирович. — СПБ., 2016. — 30 с. — Библиогр.: с. 30.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36555f1be77c40d58cf8

UUID: 52023ba3-43a1-4dff-97a5-f2dd4abb55ee

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 10

Плоткин Артем Владимирович

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 893438 bytes

Поделиться работой

Санкт-Петербургский государственный университет Прикладная математика и информатика Исследование операций и принятие решений в задачах оптимизации, управления и экономики Плоткин Артем Владимирович Варианты метода сопряженных градиентов без точного линейного поиска Бакалаврская работа Научный руководитель: д. ф.-м. н., профессор В. Н. Малоземов Рецензент: к. ф.-м. н., научный сотрудник М. В. Долгополик Санкт-Петербург 2016

Saint Petersburg State University Applied Mathematics and Computer Science Operation Research and Decision Making in Optimisation, Control and Economics Problems Plotkin Artem Vladimirovich Variants of gonjugate gradient method without exact linear search Bachelor’s Thesis Scientific Supervisor: Professor V. N. Malozemov Reviewer: Research fellow M. V. Dolgopolik Saint Petersburg 2016

3 Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Глава 1. О методе сопряженных градиентов . . . . . . . . . . . . . . . . . 5 1.1. Минимизация квадратичной функции . . . . . . . . . . . . . . . . . . . . 5 1.2. Общая задача безусловной минимизации . . . . . . . . . . . . . . . . . . 6 1.3. Обновление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4. Линейный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5. Параметр сопряженности . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Глава 2. Сходимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1. Условия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Теорема Зойтендейка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Глава 3. Численные эксперименты и их анализ . . . . . . . . . . . . . . . 14 3.1. Целевая функция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2. Численные эксперименты . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3. Анализ результатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Глава 4. Минимизация циклической функции . . . . . . . . . . . . . . . . 20 4.1. Неравенство Шапиро . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2. Постановка задачи и метод решения . . . . . . . . . . . . . . . . . . . . . 20 4.3. Начальное приближение . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.4. Результаты вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Глава 5. Геометрический вариант метода сопряженных градиентов . . 25 5.1. Особенности геометрического варианта . . . . . . . . . . . . . . . . . . . 25 5.2. Сходимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Введение Метод сопряженных градиентов применяется для решения задач безусловной ми нимизации. Метод имеет длительную историю развития, начальный этап которого был подробно описан Голубом и О’Лири в обзорной статье [10]. Первая работа в данной области принадлежит Хестенсу и Штифелю и датируется 1952 годом [1]. В этой работе метод споряженных градиентов применялся для решение систем линейных уравнений. В 1964-м году Флетчер и Ривз [9] впервый использовали метод сопряженных градиентов для минимизации гладких функций. Развитие метода продолжается и сейчас: разрабатываются новые варианты метода, исследуются вопросы сходимости. Достоинствами метода сопряженных градиентов являются его простота и низкие затраты памяти, что делает его особенно эффективным при решении задач большой размерности. В данной работе представлен обзор и сравнение различных вариантов метода со пряженных градиентов. Большое внимание уделяется наиболее эффективным способам осуществления линейного поиска. Исследуются вопросы сходимости. На примере зада чи о минимизации циклической функции проверяется эффективность работы метода.

5 Глава 1 О методе сопряженных градиентов 1.1. Минимизация квадратичной функции Рассмотрим задачу минимизации квадратичной функции 1 𝑄(𝑥) = ⟨𝐴𝑥, 𝑥⟩ − ⟨𝑏, 𝑥⟩ → min𝑛 , 𝑥∈R 2 (1.1) где матрица 𝐴 симметрична и положительно определена. Функция 𝑄 строго выпукла на R𝑛 , и условие 𝑄′ (𝑥) = 0 служит критерием оптимальности для поставленной задачи. В 1952-м году Хестенс и Штифель предложили эффективный метод решения за дачи (1.1), который получил название метод сопряженных градиентов [1]. Опишем вычислительную схему данного метода. Нулевой шаг. Возьмем произвольное начальное приближение 𝑥1 ∈ R𝑛 и вычислим значение градиента 𝑔1 = 𝑄′ (𝑥1 ) = 𝐴𝑥1 − 𝑏. Если 𝑔1 = O, то 𝑥1 — решение задачи (1.1). В противном случае задаем направление 𝑑1 = −𝑔 1 . 𝑘-й шаг. Пусть имеются 𝑥𝑘 , 𝑑𝑘 и 𝑔𝑘 ̸= O. Вычислим следующее приближение 𝑥𝑘+1 по формуле ⟨𝑔𝑘 , 𝑔𝑘 ⟩ , ⟨𝐴𝑑𝑘 , 𝑑𝑘 ⟩ (1.2) 𝑥𝑘+1 = 𝑥𝑘 + 𝛼𝑘 𝑑𝑘 . (1.3) 𝛼𝑘 = Далее найдем значение градиента 𝑔𝑘+1 = 𝑄′ (𝑥𝑘+1 ) = 𝑔𝑘 + 𝛼𝑘 𝐴𝑑𝑘 . Если 𝑔𝑘+1 = O, то 𝑥𝑘+1 — решение задачи (1.1). В противном случае вычисляем следующее направление 𝑑𝑘+1 по формуле 𝛽𝑘 = ||𝑔𝑘+1 ||2 , ||𝑔𝑘 ||2 𝑑𝑘+1 = −𝑔𝑘+1 + 𝛽𝑘 𝑑𝑘 . (1.4) (1.5) Не позднее 𝑘 = 𝑛 метод найдет решение поставленной задачи. Коэффициент 𝛼𝑘 облада ет экстремальным свойством: минимум функции 𝑄(𝑥𝑘 + 𝛼𝑑𝑘 ) достигается при 𝛼 = 𝛼𝑘 . Данный факт позволяет сформулировать вычислительную схему метода без использо вания матрицы 𝐴. Более подробный обзор метода сопряженных градиентов для решения задачи (1.1) можно найти в [2].

6 1.2. Общая задача безусловной минимизации Предположение о том, что любая гладкая функция 𝑓 в окрестности локального минимума хорошо аппроксимируется выпуклой квадратичной, привело к идеи исполь зования метода сопряженных градиентов для решения общей задачи безусловной ми нимизации 𝑓 (𝑥) → min𝑛 , 𝑥∈R (1.6) где функция 𝑓 : R𝑛 → R непрерывно дифференцируема и ограничена снизу. Градиент целевой функции будем обозначать через 𝑔(𝑥). Опишем вычислительную схему метода сопряженных градиентов для решения за дачи (1.6). Нулевой шаг. Возьмем произвольное начальное приближение 𝑥1 ∈ R𝑛 и вычислим значение градиента 𝑔1 = 𝑔(𝑥1 ). Если 𝑔1 = O, то 𝑥1 — решение задачи (1.6). В противном случае задаем направление 𝑑1 = −𝑔1 . 𝑘-й шаг. Пусть имеются 𝑥𝑘 , 𝑑𝑘 . Вычислим следующее приближение 𝑥𝑘+1 по формуле 𝑥𝑘+1 = 𝑥𝑘 + 𝛼𝑘 𝑑𝑘 , (1.7) где 𝛼𝑘 — приближенное решение задачи одномерной минимизации 𝑓 (𝑥𝑘 + 𝛼𝑑𝑘 ) → min . 𝛼>0 (1.8) Далее найдем значение градиента 𝑔𝑘+1 = 𝑔(𝑥𝑘+1 ). Если 𝑔𝑘+1 = O, то 𝑥𝑘+1 — решение задачи (1.1). В противном случае вычисляем следующее направление 𝑑𝑘+1 по формуле 𝑑𝑘+1 = −𝑔𝑘+1 + 𝛽𝑘 𝑑𝑘 . (1.9) Коэффициент 𝛽𝑘 называется параметром сопряженности. Каждый вариант метода сопряженных градиентов имеет свое определение этого параметра. Однако, в случае, когда 𝑓 — строго выпуклая квадратичная функция, а линейный поиск, решающий за дачу (1.8), находит точный минимум, все варианты параметра 𝛽𝑘 эквивалентны. 1.3. Обновление Будем говорить, что выполняется свойство убывания, если ⟨𝑔𝑘 , 𝑑𝑘 ⟩ < 0. (1.10)

7 Если данное свойство нарушается, то может и не существовать 𝛼 > 0 такого, что 𝑓 (𝑥𝑘 + 𝛼𝑑𝑘 ) < 𝑓 (𝑥𝑘 ). Чтобы бороться с этим явлением, метод сопряженных градиен тов время от времени обновляют: берут текущее приближение 𝑥𝑘 в качестве начально го. На практике обновление делают каждые 𝑛 итераций или при нарушении свойства убывания. 1.4. Линейный поиск Рассмотрим подробнее задачу одномерной минимизации (1.8) и различные вари анты линейного поиска для ее решения. Будем предполагать, что 𝑑𝑘 является направ лением убывания. Введем функцию 𝜙(𝛼) = 𝑓 (𝑥𝑘 + 𝛼𝑑𝑘 ) и перепишем задачу (1.8) в упрощенном виде: 𝜙(𝛼) → min . 𝛼>0 (1.11) Отметим, что 𝜙′ (𝛼) = ⟨𝑔(𝑥𝑘 + 𝛼𝑑𝑘 ), 𝑑𝑘 ⟩. Перейдем к описанию различных вариантов решения этой задачи. Точный поиск. Наилучшим выбором для значения 𝛼𝑘 является первая стационарная точка функции 𝜙(𝛼): 𝛼𝑘 = min{𝛼 > 0 | 𝜙′ (𝛼) = 0}. (1.12) ⟨𝑔𝑘+1 , 𝑑𝑘 ⟩ = 0. (1.13) Тогда выполняется условие Из формулы (1.9) и условия (1.13) следует, что при таком выборе 𝛼𝑘 условие убывания выполняется для всех 𝑘 > 1. Однако использование такого поиска очень затратно и редко применяется на практике. Кроме того, условий гладкости и ограниченности це левой функции снизу недостаточно для существования стационарной точки функции 𝜙(𝛼). На практике применяется линейный поиск, основывающийся на выборе 𝛼𝑘 , кото рое удовлетворяет некоторым условиям. Перечислим наиболее часто используемые из них. Условие Армихо. 𝜙(𝛼) 6 𝜙(0) + 𝜇𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩, где 0 < 𝜇 < 1 — фиксированный параметр. (1.14)

8 Рис. 1.1. Условие Армихо. Условие Гольдштейна. 𝜙(0) + (1 − 𝜇)𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩ 6 𝜙(𝛼) 6 𝜙(0) + 𝜇𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩, где 0 < 𝜇 < 1 2 (1.15) — фиксированный параметр. Рис. 1.2. Условие Гольдштейна. Стандартные условия Вулфа. 𝜙(𝛼) 6 𝜙(0) + 𝜇𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩, (1.16) 𝜙′ (𝛼) > 𝜈⟨𝑔𝑘 , 𝑑𝑘 ⟩, (1.17) где 0 < 𝜇 < 𝜈 < 1 — фиксированные параметры.

9 Рис. 1.3. Стандартные условия Вулфа. Усиленные условия Вулфа. 𝜙(𝛼) 6 𝜙(0) + 𝜇𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩, |𝜙′ (𝛼)| 6 −𝜈⟨𝑔𝑘 , 𝑑𝑘 ⟩, (1.18) (1.19) где 0 < 𝜇 < 𝜈 < 1 — фиксированные параметры. Рис. 1.4. Усиленные условия Вулфа. Теорема 1. Пусть функция 𝑓 непрерывно дифференцируема и ограничена снизу на R𝑛 , и выполняется условие убывания. Тогда существует непустой интервал 𝛼, удо влетворяющий стандартным и усиленным условиям Вулфа. Доказательство. Рассмотрим луч 𝑙(𝛼) = 𝜙(0) + 𝜇𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩, 𝛼 > 0. Такой луч пересекает график функции 𝜙(𝛼). Пусть 𝛼′ является абсциссой первой точки пересечения. Тогда

10 выполняется 𝜙(𝛼′ ) = 𝜙(0) + 𝜇𝛼⟨𝑔𝑘 , 𝑑𝑘 ⟩. (1.20) По теореме Лагранжа о среднем значении существует 𝛼′′ ∈ (0, 𝛼′ ), при котором выпол няется 𝜙(𝛼′ ) = 𝜙(0) + 𝛼′ 𝜙′ (𝛼′′ ). (1.21) 𝜙′ (𝛼′′ ) = 𝜇⟨𝑔𝑘 , 𝑑𝑘 ⟩ > 𝜈⟨𝑔𝑘 , 𝑑𝑘 ⟩. (1.22) 𝜙(𝛼′′ ) < 𝜙(0) + 𝜇𝛼⟨𝑔𝑑 , 𝑑𝑘 ⟩, (1.23) 𝜈⟨𝑔𝑘 , 𝑑𝑘 ⟩ < 𝜙(𝛼′′ ) < 0. (1.24) Тогда Получили, что для 𝛼′′ верно Из полученных неравенств и гладкости функции 𝑓 следует выполнение стандартных и усиленных условий Вулфа в некоторой окрестности 𝛼′′ . Для условий Армихо и Гольдштейна такой результат очевиден. Подробности реа лизации описанных выше вариантов линейного поиска можно найти в [3]. 1.5. Параметр сопряженности Введем обозначение 𝑦𝑘 = 𝑔𝑘+1 − 𝑔𝑘 и перечислим различные варианты выбора параметра сопряженности 𝛽𝑘 в порядке их появления:

11 𝛽𝑘𝐻𝑆 = ⟨𝑔𝑘+1 , 𝑦𝑘 ⟩ ⟨𝑑𝑘 , 𝑦𝑘 ⟩ 𝛽𝑘𝐹 𝑅 = Хестенс, Штифель (1952 г.) ||𝑔𝑘+1 ||2 ||𝑔𝑘 ||2 Флетчер, Ривз (1964 г.) 𝛽𝑘𝑃 𝑅 = ⟨𝑔𝑘+1 , 𝑦𝑘 ⟩ ||𝑔𝑘 ||2 Полак, Рибьер (1969 г.) 𝛽𝑘𝐶𝐷 = ||𝑔𝑘+1 ||2 ⟨−𝑑𝑘 , 𝑔𝑘 ⟩ Флетчер (1987 г.) 𝛽𝑘𝐿𝑆 = ⟨𝑔𝑘+1 , 𝑦𝑘 ⟩ ⟨−𝑑𝑘 , 𝑔𝑘 ⟩ Лиу, Стори (1991 г.) 𝛽𝑘𝐷𝑌 = ||𝑔𝑘+1 ||2 ⟨𝑑𝑘 , 𝑦𝑘 ⟩ Дай, Юань (1999 г.) Хагер, Жанг (2005 г.) 𝛽𝑘𝐻𝑍 ⟨ ⟩ ||𝑦𝑘 ||2 𝑔𝑘+1 = 𝑦𝑘 − 2𝑑𝑘 , ⟨𝑑𝑘 , 𝑦𝑘 ⟩ ⟨𝑑𝑘 , 𝑦𝑘 ⟩ Таблица 1.1. Варианты параметра 𝛽𝑘 .

12 Глава 2 Сходимость 2.1. Условия Анализ сходимости метода сопряженных градиентов осуществляется при более строгих условиях на целевую функцию: Условие 1. Множество уровня ℒ = {𝑥 ∈ R𝑛 | 𝑓 (𝑥) 6 𝑓 (𝑥1 )}, где 𝑥1 — начальное приближение, ограничено. Условие 2. В некоторой окрестности 𝒩 множества ℒ функция 𝑓 непрерывно диф ференцируема, и ее градиент 𝑔(𝑥) удовлетворяет условию Липшица: существует кон станта 𝐿 > 0 такая, что ||𝑔(𝑥) − 𝑔(𝑦)|| 6 𝐿||𝑥 − 𝑦|| ∀𝑥, 𝑦 ∈ 𝒩 . Данных условий достаточно, чтобы гарантировать существования стационарной точки функции 𝜙(𝛼), что позволяет использовать точный линейный поиск (1.12). Будем говорить, что метод сопряженных градиентов сходится, если выполняется условие lim ||𝑔𝑘 || = 0. (2.1) 𝑘→∞ 2.2. Теорема Зойтендейка Основным инструментом в доказательстве сходимости того или иного варианта метода сопряженных градиентов является теорема Зойтендейка. Для ее формулировки нам потребуется ввести угол Θ𝑘 между −𝑔 𝑘 и 𝑑𝑘 : cos Θ𝑘 = ⟨−𝑔 𝑘 , 𝑑𝑘 ⟩ . ||𝑔𝑘 ||||𝑑𝑘 || (2.2) Теорема 2 (Зойтендейк). Пусть функция 𝑓 удовлетворяет Условиям 1, 2. Рассмот рим итеративный метод вида (1.7). Пусть условие убывания выполняется для всех 𝑘 > 1, а значение 𝛼𝑘 удовлетворяет стандартным условиям Вулфа (1.16), (1.17). То гда существует константа 𝑐 > 0 такая, что 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > 𝑐 cos2 Θ𝑘 ||𝑔𝑘 ||2 ∀𝑘 > 1. (2.3)

13 Доказательство. Из условия (1.17) получаем ⟨𝑔𝑘+1 − 𝑔𝑘 , 𝑑𝑘 ⟩ > (𝜈 − 1)⟨𝑔𝑘 , 𝑑𝑘 ⟩. (2.4) ⟨𝑔𝑘+1 − 𝑔𝑘 , 𝑑𝑘 ⟩ 6 𝛼𝑘 𝐿||𝑑𝑘 ||2 . (2.5) Из Условия 2 также имеем Комбинируя эти два неравенства, получим 𝛼𝑘 > 𝜈−1 ⟨𝑔𝑘 , 𝑑𝑘 ⟩, 𝐿 (2.6) что совместно с условием (1.16) приводит к 𝜇(1 − 𝜈) ⟨𝑔𝑘 , 𝑑𝑘 ⟩2 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > . 𝐿 ||𝑑𝑘 ||2 (2.7) Используя выражение (2.2), перепишем этот результат в виде 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > 𝑐 cos2 Θ𝑘 ||𝑔𝑘 ||2 , (2.8) где 𝑐 = 𝜇(1 − 𝜈)/𝐿 > 0. Следствие 1. Пусть выполняются предположения Теоремы 2. Тогда ∞ ∑︁ cos2 Θ𝑘 ||𝑔𝑘 ||2 < ∞. (2.9) 𝑖=1 Доказательство. Верность (2.9) следует из неравенства (2.3) и ограниченности функ ции 𝑓 снизу. Замечание 1. Вывод теоремы Зойтендейка остается справедливым, если 𝛼𝑘 вычис ляется точным поиском (1.12). Доказательство. Действительно, пусть 𝑥𝑘+1 = 𝑥𝑘 + 𝛼𝑘 𝑑𝑘 , где 𝛼𝑘 находится точным поиском (1.12). Если 𝛼𝑘 удовлетворяет стандартным условиям Вулфа, то неравенство (2.8) выполняется. Если же неравенство (1.16) нарушается, то найдется 𝛼′ < 𝛼𝑘 , удо влетворяющее стандартным условиям Вулфа, для которого верно неравенство (2.8). Но 𝑓 (𝑥𝑘+1 ) < 𝑓 (𝑥𝑘 + 𝛼′ 𝑑𝑘 ), а значит 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘 + 𝛼′ 𝑑𝑘 ) > 𝑐 cos2 Θ𝑘 ||𝑔𝑘 ||2 . (2.10) Доказательство сходимости различных вариантов метода сопряженных градиентов можно найти в [4], [11], [12].

14 Глава 3 Численные эксперименты и их анализ 3.1. Целевая функция Рассмотрим на примере функции Стайблински-Танга поведение различных вари антов метода сопряженных градиентов. Функция задается выражением 𝑛 𝑓 (𝑥) = 1 ∑︁ 4 𝑥 − 16𝑥2𝑖 + 5𝑥𝑖 . 2 𝑖=1 𝑖 (3.1) Глобальным минимум достигается в точке (𝜂, . . . , 𝜂), где 𝜂 ≈ −2.904. Использовать данную функцию будем при 𝑛 = 2, чтобы наглядно проиллюстрировать результаты. 250 200 150 100 50 0 -50 -100 5 5 0 0 -5 -5 Рис. 3.1. Функция Стайблински-Танга при 𝑛 = 2.

15 3.2. Численные эксперименты Сравнивались методы Флетчера-Ривза, Хестенса-Штифеля, Полака-Рибьера и Ха гера-Жанга. Линейный поиск удовлетворял усиленным условиям Вулфа с параметрами 𝜇 = 0.4, 𝜈 = 0.6. Обновление методов происходило только при нарушении свойства убы вания. Метод останавливался на итерации 𝑘, если выполнялось условие ||𝑔𝑘 || < 10−6 . 5 FR HS PR HZ 4 3 2 1 0 -1 -2 -3 -4 -5 -5 -4 -3 -2 -1 0 1 2 3 4 Рис. 3.2. Сравнение методов: начальное приближение (0.1, -1). Метод FR HS PR HZ Число итераций 239 19 12 17 5

16 5 FR HS PR HZ 4 3 2 1 0 -1 -2 -3 -4 -5 -5 -4 -3 -2 -1 0 1 2 3 4 5 Рис. 3.3. Сравнение методов: начальное приближение (0.1, -1.1). Метод FR HS PR HZ Число итераций - 23 15 19 Метод Флетчера-Ривза не добился требуемой точности за 1000 итераций.

17 5 FR HS PR HZ 4 3 2 1 0 -1 -2 -3 -4 -5 -5 -4 -3 -2 -1 0 1 2 3 4 Рис. 3.4. Сравнение методов: начальное приближение (0, -1). Метод FR HS PR HZ Число итераций 86 15 15 22 5

18 3.3. Анализ результатов Как видно из полученных результатов, метод Флетчера-Ривза склонен делать боль шое количество итераций, незначительно уменьшая значение целевой функции. -0.5 -1 -1.5 -2 -2.5 -3 -3.5 -4 -4.5 -4.5 -4 -3.5 -3 -2.5 -2 -1.5 -1 Рис. 3.5. Поведение метода Флетчера-Ривза. В статье [5] Пауэлл следующим образом аргументировал такое поведение метода Флетчера-Ривза. Предположим, что используется точный линейный поиск (1.12). Сле довательно, выполняется условие (1.13).

19 Тогда верны следующие равенства 𝛽𝑘 ||𝑑𝑘 || = tg Θ𝑘+1 ||𝑔𝑘+1 ||, (3.2) ||𝑑𝑘 || = sec Θ𝑘 ||𝑔𝑘 ||. (3.3) Выражая 𝑑𝑘 из (3.2), (3.3) и используя определение 𝛽𝑘𝐹 𝑅 , получим tg Θ𝑘+1 = sec Θ𝑘 ||𝑔𝑘+1 || ||𝑔𝑘+1 || > tg Θ𝑘 . ||𝑔𝑘 || ||𝑔𝑘 || (3.4) Если угол Θ𝑘 ≈ 𝜋2 , то направление 𝑑𝑘 почти перпендикулярно −𝑔𝑘 и метод совершает совсем небольшой шаг в этом направлении. Тогда ||𝑔𝑘+1 − 𝑔𝑘 || ≈ 0, а значит ||𝑔𝑘+1 || ||𝑔𝑘 || ≈ 1. Используя неравенство (3.4) приходим к выводу, что угол Θ𝑘+1 ≈ 𝜋2 . Такая особенность метода делает его особенно требовательным к обновлению.

20 Глава 4 Минимизация циклической функции Применим метод сопряженных градиентов для решения конкретной задачи. 4.1. Неравенство Шапиро Рассмотрим циклическую функцию вида 𝐹𝑛 (𝑥) = 𝑥1 𝑥2 𝑥𝑛−1 𝑥𝑛 + + ... + + , 𝑥2 + 𝑥3 𝑥3 + 𝑥 4 𝑥𝑛 + 𝑥1 𝑥1 + 𝑥2 (4.1) где 𝑥𝑖 > 0, 𝑖 ∈ 1 : 𝑛, и все знаменатели отличны от нуля. В 1954 г. Г. Шапиро выдвинул гипотезу о том, что при 𝑛 > 3 справедливо следую щее неравенство: 𝐹𝑛 (𝑥) > 𝑛 . 2 (4.2) На тот момент у него имелось доказательство только для случаев 𝑛 = 3 и 𝑛 = 4. Отметим важное свойство этого неравенства: Лемма 1. Если неравенство Шапиро неверно при некотором 𝑛 = 𝑘, то оно неверно и при 𝑛 = 𝑘 + 2. 𝑘 . Рассмотрим 𝑥′′ = (𝑥′1 , . . . , 𝑥′𝑛 , 𝑥′1 , 𝑥′2 ). Заметим, что 2 𝑘+2 ′′ ′ 𝐹𝑘+2 (𝑥 ) = 𝐹𝑘 (𝑥 ) + 1, следовательно, 𝐹𝑘+2 (𝑥′′ ) < . 2 Доказательство. Пусть 𝐹𝑘 (𝑥′ ) < Гипотеза Шапиро вызвала широкий интерес математиков, но только к 1989 г. кол лективными усилиями удалось установить, что неравенство Шапиро верно дня четных 𝑛 6 12 и нечетных 𝑛 6 23. Для 𝑛 = 14 и 𝑛 = 25 неравенство нарушается, а значит, по доказанной лемме, нарушается и для всех четных 𝑛 > 14 и нечетных 𝑛 > 25. 4.2. Постановка задачи и метод решения Задача заключалась в поиске значений 𝑥, при которых нарушается неравенство Шапиро в случаях 𝑛 = 14 и 𝑛 = 25. Для этого рассмотрим экстремальную задачу следующего вида: 𝐹𝑛 (𝑥) → min, 𝑥𝑖 > 0, 𝑖 ∈ 1 : 𝑛. (4.3)

21 Стоит отметить, что при 𝑛 > 3 для всех векторов 𝑥 с положительными компонентами справедлива оценка Дринфельда 𝐹𝑛 (𝑥) > 𝑐 𝑛 , 2 (4.4) где 𝑐 = 0.989 [6]. Сделаем замену 𝑥𝑖 = 𝑦𝑖2 и перейдем к задаче безусловной минимизации 𝐺𝑛 (𝑦) = 2 𝑦𝑛−1 𝑦12 𝑦22 𝑦𝑛2 + + . . . + → min𝑛 . + 𝑦∈R 𝑦22 + 𝑦32 𝑦32 + 𝑦42 𝑦𝑛2 + 𝑦12 𝑦12 + 𝑦22 (4.5) Данная задача решалась методом Хестенса-Штифеля. Линейным поиск удовлетво рял условию Армихо (1.14) с параметром 𝜇 = 0.5. Обновление происходило каждые 𝑛 итераций или при нарушении свойства убывания. Метод останавливался на итерации 𝑘, если выполнялось условие ||𝑔𝑘 || < 10−6 . 4.3. Начальное приближение Запуск алгоритма из случайных начальных приближений редко приводил к тому, 𝑛 что в получившихся точках значение функции было меньше . Однако анализ успеш 2 ных случаев при 𝑛 = 14 позволил сделать предположение о структуре решения. На этом основании начальное приближение выбиралось следующим: 𝑦0 = [𝑝, 𝑠1 , . . . , 𝑝, 𝑠7 ], где 𝑝 — случайная величина, равномерно распределенная на отрезке [0.7, 0.9], а 𝑠𝑖 — независимые случайные величины, равномерно распределенные на отрезке [0, 0.2]. Ал горитм был запущен 10000 раз из точек такого вида и каждый раз получалась точка, 𝑛 значение функции в которой было меньше . 2 При 𝑛 = 25 успеха удалось добиться, когда в качестве начального приближения брались точки вида 𝑦0 = [𝑝, 𝑠1 , . . . , 𝑝, 𝑠12 , 𝑝], где 𝑝 и 𝑠𝑖 — такие же случайные величины, что и при 𝑛 = 14. Алгоритм был снова 10000 раз запущен из точек указанного вида и вновь в каждом случае привел к реше нию. Стоит отметить, что значение функции в точках, взятых в качестве начального 𝑛 приближения, для 𝑛 = 14 очень близко к , а для 𝑛 = 25 уже достаточно сильно 2 𝑛 отличается от . 2

22 4.4. Результаты вычислений Было получено большое количество значений 𝑥, при которых 𝐹𝑛 (𝑥) < 𝑛 для 𝑛 = 14 2 и 𝑛 = 25. Многие из них были приведены к целочисленному виду. 1. 𝑛 = 14 ∙ 𝑥 = [78, 7, 75, 8, 71, 6, 70, 3, 71, 1, 74, 1, 77, 3], 𝐹14 (𝑥) = 6.99996; ∙ 𝑥 = [73, 8, 70, 6, 68, 3, 69, 1, 72, 1, 75, 3, 76, 7], 𝐹14 (𝑥) = 6.99994; ∙ 𝑥 = [74, 6, 72, 3, 73, 1, 76, 1, 79, 3, 80, 7, 77, 8], 𝐹14 (𝑥) = 6.99991. 2. 𝑛 = 25 ∙ 𝑥 = [39, 39, 38, 28, 36, 19, 35, 11, 35, 4, 39, 0, 46, 0, 55, 0, 65, 0, 77, 12, 79, 29, 68, 38, 53], 𝐹25 (𝑥) = 12.49896; ∙ 𝑥 = [49, 48, 47, 35, 44, 23, 43, 13, 44, 5, 48, 0, 57, 0, 68, 0, 80, 0, 95, 15, 97, 36, 83, 47, 65], 𝐹25 (𝑥) = 12.49885; ∙ 𝑥 = [43, 43, 41, 30, 39, 20, 38, 12, 39, 5, 43, 0, 51, 0, 60, 0, 71, 0, 84, 13, 86, 32, 74, 41, 57], 𝐹25 (𝑥) = 12.49881. F(x) 7.0045 ||F'(x)|| 0.3 7.004 0.25 7.0035 7.003 0.2 7.0025 0.15 7.002 7.0015 0.1 7.001 7.0005 0.05 7 0 6.9995 0 50 100 150 200 250 0 50 100 150 Рис. 4.1. Случай 𝑛 = 14. Первое начальное приближение. 200 250

23 F(x) 7.0035 ||F'(x)|| 0.25 7.003 0.2 7.0025 7.002 0.15 7.0015 0.1 7.001 7.0005 0.05 7 0 6.9995 0 50 100 150 200 0 250 50 100 150 200 250 200 250 Рис. 4.2. Случай 𝑛 = 14. Второе начальное приближение. F(x) 7.0025 ||F'(x)|| 0.15 7.002 7.0015 0.1 7.001 7.0005 0.05 7 0 6.9995 0 50 100 150 200 250 0 50 100 150 Рис. 4.3. Случай 𝑛 = 14. Третье начальное приближение.

24 F(x) 13 ||F'(x)|| 1.4 12.95 1.2 12.9 1 12.85 12.8 0.8 12.75 0.6 12.7 12.65 0.4 12.6 0.2 12.55 12.5 0 0 5 10 15 20 25 30 35 40 45 50 0 5 10 15 20 25 30 35 40 45 50 Рис. 4.4. Случай 𝑛 = 25. До 50-й итерации. F(x) 12.5015 ||F'(x)|| 0.06 12.501 0.05 12.5005 0.04 12.5 0.03 12.4995 0.02 12.499 0.01 12.4985 12.498 50 100 150 200 0 50 100 Рис. 4.5. Случай 𝑛 = 25. После 50-й итерации. 150 200

25 Глава 5 Геометрический вариант метода сопряженных градиентов 5.1. Особенности геометрического варианта Рассмотрим геометрический вариант метода сопряженных градиентов, описанный в [7], и применим его для решения задачи (1.6). В этом варианте направление 𝑑𝑘 задается правилом 𝑑𝑘+1 = (1 − 𝜆𝑘 )−𝑔 𝑘+1 + 𝜆𝑘 𝑑𝑘 , ||𝑔𝑘+1 ||2 𝜆𝑘 = ||𝑔𝑘+1 ||2 + ||𝑑𝑘 ||2 (5.1) Метод имеет геометрическую интерпретацию. Пусть треугольник, натянутый на вектора −𝑔 𝑘+1 , 𝑑𝑘 , невырожден. Рассмотрим треугольники △𝐴𝐵𝐷 и △𝐴𝐶𝐷, изобра женные на рис. 5.1. Тогда ||𝑔𝑘+1 ||2 𝑆△𝐴𝐵𝐷 = . 𝑆△𝐴𝐶𝐷 ||𝑑𝑘 ||2 (5.2) Рис. 5.1. Геометрический вариант метода. Доказательство. Используя формулу (5.1) и теорему синусов, получим 𝑆△𝐴𝐵𝐷 𝐵𝐴 𝐵𝐷 sin ∠𝐴𝐵𝐷 ||𝑔𝑘+1 || ||𝑔𝑘+1 ||2 ||𝑑𝑘 || ||𝑔𝑘+1 ||2 = = = . 𝑆△𝐴𝐶𝐷 𝐶𝐴 𝐶𝐷 sin ∠𝐴𝐶𝐷 ||𝑑𝑘 || ||𝑑𝑘 ||2 ||𝑔𝑘+1 || ||𝑑𝑘 ||2 (5.3)

26 5.2. Сходимость Заметим, что формула (5.1), как и (1.9), гарантирует выполнение свойства убыва ния для 𝑘 > 1, если используется точный поиск (1.12). Данный факт позволяет исполь зовать Замечание 1 для доказательства сходимости геометрического варианта метода сопряженных градиентов при точном поиске (1.12). Теорема 3. Пусть функция 𝑓 удовлетворяет Условиям 1, 2. Если в геометрическом варианте метода сопряженных градиентов значение 𝛼𝑘 вычисляется точным линей ным поиском (1.12), то lim ||𝑔𝑘 || = 0. (5.4) 𝑘→∞ Доказательство. Пусть утверждение (5.4) неверно, тогда существует константа 𝜀 > 0 такая, что ||𝑔𝑘 ||2 > 𝜀 > 0 ∀𝑘 > 1. (5.5) 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > 𝑐 cos2 Θ𝑘 ||𝑔𝑘 ||2 , (5.6) Воспользуемся Замечанием 1 где 𝑐 > 0. Из формулы (5.1) и условия (1.13) получаем cos2 Θ𝑘 ||𝑔𝑘 ||2 = ||𝑑𝑘 ||2 . (5.7) 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > 𝑐||𝑑𝑘 ||2 . (5.8) 𝜀 𝑘 (5.9) Тогда из (5.6) следует Докажем по индукции, что ||𝑑𝑘 ||2 > ∀𝑘 > 1. При 𝑘 = 1 неравенство верно. Сделаем индукционный переход от 𝑘 к 𝑘 + 1. Воспользо вавшись формулой (5.1) и условием (1.13), получим выражение для ||𝑑𝑘+1 ||2 ||𝑑𝑘+1 ||2 = ||𝑔𝑘+1 ||2 ||𝑑𝑘 ||2 = ||𝑔𝑘+1 ||2 + ||𝑑𝑘 ||2 1 ||𝑑𝑘 ||2 1 1 + ||𝑔𝑘+1 ||2 (5.10) Далее, в силу индукционного предположения и утверждения (5.5), имеем 1 ||𝑑𝑘 ||2 1 > 1 + ||𝑔𝑘+1 ||2 𝑘 𝜀 1 + 1 𝜀 = 𝜀 , 𝑘+1 (5.11) а значит ||𝑑𝑘+1 ||2 > 𝜀 . 𝑘+1 (5.12)

27 Возвращаясь к (5.8), получим 𝑓 (𝑥𝑘 ) − 𝑓 (𝑥𝑘+1 ) > 𝑐 𝜀 𝑘 ∀𝑘 > 1, (5.13) из чего следует lim 𝑓 (𝑥𝑘 ) = −∞, 𝑘→∞ (5.14) что противоречит условию ограниченности функции 𝑓 снизу. Если же линейный поиск выполняется неточно, то выполнение свойства убывания для всех 𝑘 > 1 требует доказательства. Лемма 2. Пусть вектора −𝑔 𝑘+1 ̸= O, 𝑑𝑘 ̸= O такие, что |⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩| 6 𝑐||𝑑𝑘 ||2 , где 𝑐 ∈ (0, 1). Тогда 𝑑𝑘+1 ̸= O и выполняется неравенство ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩ 𝑐2 + 1 . 6 ||𝑑𝑘+1 ||2 1−𝑐 (5.15) Доказательство. Из формулы (5.1) находим ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩ = (1 − 𝜆𝑘 )||𝑔𝑘+1 ||2 + 𝜆𝑘 ⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = (︀ )︀ = 𝜆𝑘 ||𝑑𝑘 ||2 + ⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ . (5.16) ||𝑑𝑘+1 ||2 = (1 − 𝜆𝑘 )2 ||𝑔𝑘+1 ||2 + 𝜆2𝑘 ||𝑑𝑘 ||2 + 2𝜆𝑘 (1 − 𝜆𝑘 )⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = (︀ )︀ = 𝜆𝑘 ||𝑑𝑘 ||2 + 2(1 − 𝜆𝑘 )⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ . (5.17) Покажем, что ||𝑑𝑘+1 ||2 > 0. Пусть, напротив, ||𝑑𝑘+1 ||2 = 0, тогда ||𝑑𝑘 ||2 + 2(1 − 𝜆𝑘 )⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = 0. (5.18) Поделив на ||𝑑𝑘 ||2 > 0, получим 1+ 2⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = 0, ||𝑔𝑘+1 ||2 + ||𝑑𝑘 ||2 (5.19) что равносильно 2⟨𝑔𝑘+1 , 𝑑𝑘 ⟩ = ||𝑔𝑘+1 ||2 + ||𝑑𝑘 ||2 . (5.20) Но такое равенство возможно лишь в случае 𝑔𝑘+1 = 𝑑𝑘 , что противоречит условию |⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩| 6 𝑐||𝑑𝑘 ||2 . (5.21) Используя выражения (5.16), (5.17), получим ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩ ||𝑑𝑘 ||2 + ⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = = ||𝑑𝑘+1 ||2 ||𝑑𝑘 ||2 + 2(1 − 𝜆𝑘 )⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ ||𝑑𝑘 ||2 + ⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = . ||2 ||𝑑𝑘 ||2 + 2 ||𝑔𝑘+1||𝑑||2𝑘+||𝑑 ⟨−𝑔 , 𝑑 ⟩ 𝑘+1 𝑘 2 𝑘 || Пусть |⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩| = 𝑐1 ||𝑑𝑘 ||2 , где 𝑐1 ∈ [0, 𝑐]. Рассмотрим два случая. (5.22)

28 1. ⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = 𝑐1 ||𝑑𝑘 ||2 > 0. Используя выражение (5.22), получим ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩ ||𝑑𝑘 ||2 + 𝑐1 ||𝑑𝑘 ||2 6 = 1 + 𝑐1 6 1 + 𝑐. ||𝑑𝑘+1 ||2 ||𝑑𝑘 ||2 (5.23) 2. ⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩ = −𝑐1 ||𝑑𝑘 ||2 < 0. Используя выражение (5.22), получим ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩ ||𝑑𝑘 ||2 − 𝑐1 ||𝑑𝑘 ||2 = 6 2 𝑘 || ||𝑑𝑘+1 ||2 ||𝑑𝑘 ||2 − 2 𝑐2 ||𝑑𝑘||𝑑 𝑐 ||𝑑𝑘 ||2 ||2 +||𝑑𝑘 ||2 1 1 1 − 𝑐1 𝑐21 + 1 𝑐2 + 1 = = 6 . 1 1 − 𝑐1 1−𝑐 1 − 𝑐2𝑐 2 +1 (5.24) 1 Осталось заметить, что 1+𝑐6 𝑐2 + 1 . 1−𝑐 (5.25) Равенство в (5.15) достигается, когда 𝑔𝑘+1 = 𝑐𝑑𝑘 . Теорема 4. Зафиксируем 𝑐 ∈ (0, 1). Пусть в геометрическом варианте метода со пряженных градиентов значение 𝛼𝑘 удовлетворяет условию (1.19) с параметром 𝜈 6 𝑐(1 − 𝑐) . Тогда свойство убывания выполняется для всех 𝑘 > 1. 𝑐2 + 1 Доказательство. Докажем по индукции, что неравенство 0 < ⟨−𝑔𝑘 , 𝑑𝑘 ⟩ 6 𝑐2 + 1 ||𝑑𝑘 ||2 . 1−𝑐 (5.26) выполняется при всех 𝑘 > 1. При 𝑘 = 1 неравенство верно. Сделаем индукционный переход от 𝑘 к 𝑘 + 1. Из условия (1.19) и индукционного предположения получим |⟨−𝑔𝑘+1 , 𝑑𝑘 ⟩| 6 𝜈⟨−𝑔𝑘 , 𝑑𝑘 ⟩ 6 𝑐(1 − 𝑐) 𝑐2 + 1 ||𝑑𝑘 ||2 = 𝑐||𝑑𝑘 ||2 . 𝑐2 + 1 1 − 𝑐 (5.27) Из полученного неравенства и выражения (5.16) получим 0 < ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩, (5.28) 𝑐2 + 1 ||𝑑𝑘+1 ||2 . ⟨−𝑔𝑘+1 , 𝑑𝑘+1 ⟩ 6 1−𝑐 (5.29) а из Леммы 2 Следствие 2. Пусть в методе сопряженных градиентов 𝑑𝑘+1 вычисляется по фор √ муле (5.1), а значение 𝛼𝑘 удовлетворяет условию (1.19) с параметром 𝜈 6 12 ( 2 − 1). Тогда свойство убывания выполняется для всех 𝑘 > 1. √ 𝑐(1 − 𝑐) Доказательство. Максимум функции 2 , 𝑐 ∈ (0, 1) равен 12 ( 2 − 1) и достигается 𝑐 +1 √ при 𝑐 = 2 − 1. Воспользовавшись Теоремой 4, получим требуемый результат.

29 Заключение 1. В рамках данной работы проведен обзор и численное сравнение различных вари антов метода сопряженных градиентов. 2. С помощью метода сопряженных градиентов решена задача о построении контр примеров для неравенства Шапиро. 3. Доказана теорема о сходимости геометрического варианта метода сопряженных градиентов при точном линейном поиске. 4. Установлено свойство убывания целевой функции в геометрическом варианте ме тода сопряженных градиентов при неточном линейном поиске. Предварительные результаты опубликованы в [8].

30 Список литературы 1. Hestenes M. R., Stiefel E. Method of Conjugate Gradients for Solving Linear Systems // Journal of Research of the National Bureau of Standards. 1952. Vol. 49. P. 409–436. 2. Малозёмов В. Н. О методе сопряжённых градиентов. Семинар «DHA & CAGD». Избранные доклады. 28.04.2012. URL: http://dha.spb.ru/reps12.shtml#0428. 3. Nocedal J., Wright S. J. Numerical Optimization. 2nd edition. Springer, 2006. P. 664. 4. Pytlak R. Conjugate Gradient Algorithms in Nonconvex Optimization. Springer, 2009. P. 478. 5. Powell M. J. D. Restart Procedures of the Conjugate Gradient Method // Mathematical Programming. 1977. Vol. 12. P. 241–254. 6. Малозёмов В. Н. Циклические функции и экстремальные задачи. Семинар «CNSA & NDO». Избранные доклады. 27.08.2015. URL: http://www.apmath.spbu.ru/cnsa/ reps15.shtml#0827. 7. Малозёмов В. Н. Варианты метода сопряжённых градиентов. Семинар «CNSA & NDO». Избранные доклады. 29.10.2015. URL: http://www.apmath.spbu.ru/cnsa/ reps15.shtml#1029. 8. Плоткин А. В. Минимизация циклической функции // Процессы управления и устойчивость. Vol. 3 (19). 2016. (принята в печать). 9. Fletcher R., Reeves C. M. Function Minimization by Conjugate Gradients // Computer Journal. 1964. Vol. 7. P. 149–154. 10. Golub G. H., O’Leary D. P. Some History of the Conjugate Gradient Methods and Lanczos Algorithms: 1948–1976 // SIAM Rev. 1989. Vol. 31. P. 50–102. 11. Hager W. W., Zhang H. A Survey of Nonlinear Conjugate Gradient Methods // Pacific Journal of Optimization. 2006. Vol. 2. P. 335–358. 12. Dai Y. H. Nonlinear Conjugate Gradient Methods. Wiley Encyclopedia of Operations Research and Management Science. 15.02.2011.

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв