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


СУРГУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ХАНТЫ – МАНСИЙСКОГО АВТОНОМНОГО ОКРУГА – ЮГРЫ
ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
Факультет информационных технологий
Кафедра автоматизированных систем обработки информации и управления
РЕФЕРАТ
На тему: «Методы минимизации квадратичных функционалов.
Метод покоординатного спуска.»
по курсу “Методы оптимизации”
Выполнил: студент группы 1192
Кияшко Кирилл Игоревич
Проверил профессор:
Галкин Валерий Алексеевич

Сургут, 2013
ОГЛАВЛЕНИЕ
TOC \o "1-3" \h \z \u ВВЕДЕНИЕ PAGEREF _Toc356135880 \h 2МЕТОД ПОКООРДИНАТНОГО СПУСКА PAGEREF _Toc356135881 \h 3ЗАКЛЮЧЕНИЕ PAGEREF _Toc356135882 \h 9СПИСОК ЛИТЕРАТУРЫ PAGEREF _Toc356135883 \h 10

ВВЕДЕНИЕСуществуют методы оптимизации, которые для своей реализации требуют вычисления первых или вторых производных минимизируемой функции. Однако в практических задачах нередко встречаются случаи, когда минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление ее производных с нужной точностью требует слишком большого объема работ, много машинного времени. В таких случаях желательно иметь методы минимизации, которые требуют лишь вычисления значения функции. Одним из таких методов является метод покоординатного спуска (метод Гаусса-Зейделя).

МЕТОД ПОКООРДИНАТНОГО СПУСКАРассмотрим следующую задачу:
QUOTE . (1)
Обозначим QUOTE – единичный координатный вектор, у которого i-я координата равна 1, остальные равны нулю, i = 1,…,n. Пусть u0 – некоторое начальное приближение, а QUOTE – некоторое положительное число, являющееся параметром метода. Допустим, что нам уже известны точка uk ϵ En и число QUOTE при каком-либо QUOTE . Положим:
QUOTE , (2)
где QUOTE означает целую часть числа QUOTE . Условие (2) обеспечивает циклический перебор координатных векторов QUOTE , т. е.

Вычислим значение функции QUOTE в точке QUOTE и проверим неравенство
QUOTE (3)
Если (3) выполняется, то примем:
QUOTE . (4)
В том случае, если (3) не выполняется, вычисляем значение функции J(u) в точке QUOTE и проверяем неравенство:
QUOTE . (5)
В случае выполнения неравенства (5) положим:
QUOTE . (6)
Назовем QUOTE -ю итерацию удачной, если справедливо хотя бы одно из неравенств (3) или (5). Если QUOTE -я итерация неудачная, т. е. не выполняются оба неравенства (3) и (5), то полагаем:

Здесь λ, 0<λ<1 – фиксированное число, являющееся параметром метода. Условия (7) означают, что если за один цикл из n итераций при переборе направлений всех координатных осей QUOTE с шагом QUOTE реализовалась хотя бы одна удачная итерация, то длина шага QUOTE не дробится и сохраняется на протяжении по крайней мере следующего цикла из n итераций. Если же среди последних n итераций не оказалось ни одной удачной итерации, то шаг QUOTE дробится. Таким образом, если на итерации с номером QUOTE произошло дробление QUOTE , то
QUOTE
при всех i=1,…,n. Метод покоординатного спуска для задачи (1) описан.
Заметим, что хотя метод (2) – (7) для своей реализации не требует знания градиента минимизируемой функции. Оказывается, если функция QUOTE не является гладкой, то метод покоординатного спуска может не сходиться ко множеству решений задачи (1).
Описанный выше метод покоординатного спуска нетрудно модифицировать применительно к задаче минимизации функции на параллелепипеде:
QUOTE
(9)
где QUOTE – заданные числа, QUOTE . А именно, пусть k-е приближение QUOTE uk ϵ U и число QUOTE при некотором QUOTE уже найдены. Выберем вектор QUOTE согласно формуле (2), составим точку QUOTE и проверим условия:

Если оба условия (10) выполняются, то следующее приближение QUOTE определяем по формулам (4). Если же хотя бы одно условие (10) не выполняется, то составляем точку QUOTE uk - αkpk и проверяем условия:

В случае выполнения обоих условий (11) следующее приближение определяем по формулам (6), а если хотя бы одно из условий (11) не выполняется, то следующее приближение находится по формулам (7).
Существуют и другие варианты метода покоординатного спуска. Можно, например, строить последовательность QUOTE {uk}по правилу:
QUOTE , (12)
где QUOTE определяется согласно (2), а QUOTE – условиями:
QUOTE (13)
Метод (12), (13) имеет смысл применять в том случае, когда величина QUOTE из (13) находится в явном виде. Так будет, если функционал QUOTE J(u) квадратичный, т е.
QUOTE (14)
где A– симметричная положительно определенная матрица, QUOTE . Нетрудно убедиться, что для функции (14) метод (12), (13) приводит к хорошо известному методу Зейделя из линейной алгебры. [1]
Рассмотрим еще один вариант описания метода Гаусса-Зейделя.
Пусть требуется найти наименьшее значение целевой функции QUOTE . В качестве начального приближения выберем в п-мерном пространстве некоторую точку M0 с координатами QUOTE . Зафиксируем все координаты функции и, кроме первой. Тогда QUOTE – функция одной переменной x1. Решая одномерную задачу оптимизации для этой функции, мы от точки M0 перейдем к точке QUOTE , в которой функция и принимает наименьшее значение по координате x1 при фиксированных остальных координатах. В этом состоит первый шаг процесса оптимизации, состоящий в спуске по координате x1.
Зафиксируем теперь все координаты, кроме x2, и рассмотрим функцию этой переменной QUOTE . Снова решая одномерную задачу оптимизации, находим ее наименьшее значение при QUOTE , т.е. в точке QUOTE . Аналогично проводится спуск по координатам QUOTE , а затем процедура снова повторяется от x1 до xn и т.д. В результате этого процесса получается последовательность точек M0,M1,…, в которых значения целевой функции составляют монотонно убывающую последовательность QUOTE На любом k-м шаге этот процесс можно прервать, и значение QUOTE принимается в качестве наименьшего значения целевой функции в рассматриваемой области.
Таким образом, метод покоординатного спуска сводит задачу о нахождении наименьшего значения функции многих переменных к многократному решению одномерных задач оптимизации по каждому проектному параметру.
Данный метод легко проиллюстрировать геометрически для случая функции двух переменных QUOTE , описывающей некоторую поверхность в трехмерном пространстве. На рисунке 1 нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка QUOTE описывает начальное приближение. Проводя спуск по координате х, попадем в точку QUOTE . Далее, двигаясь параллельно оси ординат, придем в точку QUOTE и т.д.

Рисунок 1 – Геометрическая интерпретация метода покоординатного спуска для целевой функции QUOTE .
Важным здесь является вопрос о сходимости рассматриваемого процесса оптимизации. Другими словами, будет ли последовательность значений целевой функции QUOTE сходиться к наименьшему ее значению в данной области? Это зависит от вида самой функции и выбора начального приближения.[2]

ЗАКЛЮЧЕНИЕХотя скорость сходимости метода покоординатного спуска, вообще говоря, невысокая, благодаря простоте каждой итерации, скромным требованиям к гладкости минимизируемой функции этот метод довольно широко применяется на практике.
Для функции двух переменных очевидно, что метод неприменим в случае наличия изломов в линиях уровня. Это соответствует так называемому оврагу на поверхности. Здесь возможен случай, когда спуск по одной координате приводит на “дно” оврага. Тогда любое движение вдоль любой координаты ведет к возрастанию функции, соответствующему подъему на “берег” оврага. Поскольку поверхности типа “оврага” встречаются в инженерной практике, то при использовании метода покоординатного спуска следует убедиться, что решаемая задача не имеет этого недостатка.
Для гладких функций при удачно выбранном начальном приближении (в некоторой окрестности минимума) процесс сходится к минимуму. К достоинствам метода покоординатного спуска следует также отнести возможность использования простых алгоритмов одномерной оптимизации.
Существуют и другие методы минимизации, использующие лишь значения функции и не требующие для своей реализации вычисления производных. Например, используя вместо производных их разностные аппроксимации, можно построить модификации, требующие вычисления лишь значений функции в подходящим образом выбранных точках.
Другой подход для минимизации негладких функций, основанный лишь на вычислении значений функции, дает метод случайного поиска. Метод поиска глобального минимума также относится к методам, не требующим вычисления производных минимизируемой функции.

СПИСОК ЛИТЕРАТУРЫВасильев, Ф.П. Численные методы решений экстремальных задач / Ф.П. Васильев. – Москва: Наука, 1988. – 551с.
Денисова, Э.В. Основы вычислительной математики / Э.В. Денисова, А.В. Кучер. – Санкт-Петербург: НИУ ИТМО, 2010. – 164 с.

Приложенные файлы

  • docx 7951831
    Размер файла: 167 kB Загрузок: 0

Добавить комментарий