МЕТОД ПОКООРДИНАТНОГО СПУСКА

РЕФЕРАТ

На тему: «Методы минимизации квадратичных функционалов.

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

по курсу “Методы оптимизации”

Выполнил: студент группы 1192

Кияшко Кирилл Игоревич

Проверил профессор:

Галкин Валерий Алексеевич

Сургут, 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ. 2

МЕТОД ПОКООРДИНАТНОГО СПУСКА.. 3

ЗАКЛЮЧЕНИЕ. 9

СПИСОК ЛИТЕРАТУРЫ.. 10

ВВЕДЕНИЕ

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

МЕТОД ПОКООРДИНАТНОГО СПУСКА

Рассмотрим следующую задачу:

. (1)

Обозначим – единичный координатный вектор, у которого i-я координата равна 1, остальные равны нулю, i = 1,…,n. Пусть u₀ – некоторое начальное приближение, а – некоторое положительное число, являющееся параметром метода. Допустим, что нам уже известны точка u_k ϵ Eⁿ и число при каком-либо . Положим:

, (2)

где означает целую часть числа . Условие (2) обеспечивает циклический перебор координатных векторов , т. е.

Вычислим значение функции в точке и проверим неравенство

(3)

Если (3) выполняется, то примем:

. (4)

В том случае, если (3) не выполняется, вычисляем значение функции J(u) в точке и проверяем неравенство:

. (5)

В случае выполнения неравенства (5) положим:

. (6)

Назовем -ю итерацию удачной, если справедливо хотя бы одно из неравенств (3) или (5). Если -я итерация неудачная, т. е. не выполняются оба неравенства (3) и (5), то полагаем:

Здесь λ, 0<λ<1 – фиксированное число, являющееся параметром метода. Условия (7) означают, что если за один цикл из n итераций при переборе направлений всех координатных осей с шагом реализовалась хотя бы одна удачная итерация, то длина шага не дробится и сохраняется на протяжении по крайней мере следующего цикла из n итераций. Если же среди последних n итераций не оказалось ни одной удачной итерации, то шаг дробится. Таким образом, если на итерации с номером произошло дробление , то

при всех i=1,…,n. Метод покоординатного спуска для задачи (1) описан.

Заметим, что хотя метод (2) – (7) для своей реализации не требует знания градиента минимизируемой функции. Оказывается, если функция не является гладкой, то метод покоординатного спуска может не сходиться ко множеству решений задачи (1).

Описанный выше метод покоординатного спуска нетрудно модифицировать применительно к задаче минимизации функции на параллелепипеде:

(9)

где – заданные числа, . А именно, пусть k-е приближение u_k ϵ U и число при некотором уже найдены. Выберем вектор согласно формуле (2), составим точку и проверим условия:

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

В случае выполнения обоих условий (11) следующее приближение определяем по формулам (6), а если хотя бы одно из условий (11) не выполняется, то следующее приближение находится по формулам (7).

Существуют и другие варианты метода покоординатного спуска. Можно, например, строить последовательность {u_k}по правилу:

, (12)

где определяется согласно (2), а – условиями:

(13)

Метод (12), (13) имеет смысл применять в том случае, когда величина из (13) находится в явном виде. Так будет, если функционалJ(u) квадратичный, т е.

(14)

где A– симметричная положительно определенная матрица, . Нетрудно убедиться, что для функции (14) метод (12), (13) приводит к хорошо известному методу Зейделя из линейной алгебры. [1]

Рассмотрим еще один вариант описания метода Гаусса-Зейделя.

Пусть требуется найти наименьшее значение целевой функции . В качестве начального приближения выберем в п-мерном пространстве некоторую точку M0 с координатами . Зафиксируем все координаты функции и, кроме первой. Тогда – функция одной переменной x1. Решая одномерную задачу оптимизации для этой функции, мы от точки M0 перейдем к точке , в которой функция и принимает наименьшее значение по координате x1 при фиксированных остальных координатах. В этом состоит первый шаг процесса оптимизации, состоящий в спуске по координате x1.

Зафиксируем теперь все координаты, кроме x2, и рассмотрим функцию этой переменной . Снова решая одномерную задачу оптимизации, находим ее наименьшее значение при , т.е. в точке . Аналогично проводится спуск по координатам , а затем процедура снова повторяется от x1 до xn и т.д. В результате этого процесса получается последовательность точек M0,M1,…, в которых значения целевой функции составляют монотонно убывающую последовательность На любом k-м шаге этот процесс можно прервать, и значение принимается в качестве наименьшего значения целевой функции в рассматриваемой области.

Таким образом, метод покоординатного спуска сводит задачу о нахождении наименьшего значения функции многих переменных к многократному решению одномерных задач оптимизации по каждому проектному параметру.

Данный метод легко проиллюстрировать геометрически для случая функции двух переменных , описывающей некоторую поверхность в трехмерном пространстве. На рисунке 1 нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка описывает начальное приближение. Проводя спуск по координате х, попадем в точку . Далее, двигаясь параллельно оси ординат, придем в точку и т.д.

Рисунок 1 – Геометрическая интерпретация метода покоординатного спуска для целевой функции .

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

Поиск по сайту: