Программа Градиентным Методом

Градиентные методы.. Мэн- цзы. В этом параграфе изучается класс так называемых градиентных методов приближенного решения задач оптимизации. Доказываются теоремы сходимости, описываются простейшие модификации. Общие соображения и определения. Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации. Начиная с некоторого x. Rm, строится последовательность {xn} ⊂ Rm такая, что.

1. Для каждого рассматриваемого метода приводятся блок – схема алгоритма, программа на языке “MATLAB” и. Градиентные методы решения задач вогнутого программирования..
2. Работу скачали: 152 чел. Градиентные методы. Антиградиент (и градиент) ортогонален поверхности уровня f(X) в точке X. Если в (1.2) ввести направление..
3. Нужно воспроизвести это решение в моей программе. Я включил в. Градиентный метод практически неработоспособен. МатЛаб.

. В программе реализованы следующие задачи: Расчёт градиентным методом найскорейшего спуска. Расчёт методом покоординатного&nbsp. Так же в работе был составлен алгоритм моделирования, на основе которого была написана программа для проведения исследований градиентным методом..

N. Такие последовательности иногда называют , а методы построения релаксационных последовательностей — или . Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn+1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному). Мы будем говорить, что метод, начиная с данного x. Rm. а) , если последовательность {xn} релаксационна и. C > 0 и q ∈ [0, 1)г) , если для любого q ∈ (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3). C > 0 и q ∈ [0, 1) и всех n ∈ NЕсли эти свойства выполняются только для x. З а д а ч а  3. 1*.

Пусть при некотором q ∈ [0, 1). N. Докажите, что метод линейно сходится.

З а д а ч а  3. 2*. Пусть при некотором C1 > 0. C1 xn –x* 2, n ∈ Nи x.

Докажите, что метод квадратично сходится. Будем говорить, что на данной последовательности метод (или имеет p- ый порядок сходимости). C. xn+1 – x* ≤ C xn – x* p. Эвристические соображения, приводящие к градиентным методам. Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции.

Этот факт позволяет надеяться, что последовательность {xn}, рекуррентно определяемая формулой. К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B(xn, ε) с центром в точке xn функцию f ее линейным (вернее, афинным) приближением. Разумеется. (линейная) безусловная задача φ(x) → min неразрешима, если f ′(xn) ≠ Θ (см. В окрестности же.

B(xn, ε) функция φ имеет точку минимума. Эту точку естественно взять за следующее приближение xn+1. З а д а ч а  3. 3.

Покажите, что. argminx ∈ B(xn, ε)f(x) задается формулой. Градиентный метод с постоянным шагом. В общем случае число α в формуле (4) может на каждом шаге (т. е.

Именно методы, задаваемые формулой (5), называются . Если αn = α при всех n, то получающийся метод называется (с шагом α.). Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня.

Rm: f(x) = c}. Каждому значению c отвечает своя линия уровня (см. Рис. 5. З а д а ч а  3. Докажите, что касательная к линии. R2 → R ортогональна к градиенту.

Как обобщить это. Геометрическая интерпретация градиентного метода с постоянным. На каждом шаге мы сдвигаемся по. Рис. 6. 3. 4. Один пример исследования сходимости.

Изучим сходимость градиентного метода с постоянным шагом на примере функции. Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xn градиентного метода имеют вид. Пределом этой последовательности может быть только 0. Действительно, если x** =limn→∞xn ≠ 0, то, переходя к пределу в. Очевидно также, что если x. Покажем, что если p < 2, то при любом шаге α > 0 и любом начальном приближении x.

Для этого заметим, что если 0 < xn < (2/αp)1/2(2–p), то. Поэтому, если xn не обращается в нуль, то она не может. З а д а ч а  3. 5. Докажите. Таким образом, осталось доказать (7). В силу (6). xn+1 = xn – αp xn p–1 ·sign xn . Остается заметить, что если 0 < xn < (2/αp)1/(2–p), то, как нетрудно видеть, 1 – αp xn p–2·sign  xn > 1, что и требовалось. З а д а ч а  3. 6.

Покажите, что число начальных точек x. Если p = 2, т. е. Поэтому, если α ∈ (0, 1), то 1 – 2α < 1, а следовательно. Если же α ≥ 1, то. З а д а ч а  3. 7.

Докажите, что если p > 2, то градиентный метод (6) сходится при αp x. Таким образом, есть функции, для которых градиентный метод не сходится даже при сколь угодно малом шаге α и есть функции, для которых он сходится только при достаточно малых шагах. В следующих пунктах мы приведем ряд теорем о сходимости градиентного метода. Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f ′ удовлетворяет условию Липшица.

Rm. Тогда при α ∈ (0, 2/Λ) градиентный метод с постоянным шагомусловно сходится. Д о к а з а т е л ь с т в о. Положим zn = –αf ′(xn) и обозначим f(xn + tzn) через φ(t). Тогда, как легко видеть.

Ньютона — Лейбница для функции φ. Добавив и отняв (f ′(xn), zn) = ∫0. Учитывая условие Липшица для f ′, эту цепочку можно продолжить. Поскольку 1 – Λα/2 > 0. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xn)} сходится.

Поэтому, в частности, f(xn+1) – f(xn) → 0 при n → ∞. Отсюда и из (8) получаем.

Замечания о сходимости. Подчеркнем, что теорема 3. Например, для функции f(x) =(1 + x. R последовательность {xn}градиентного метода с постоянным шагом, начинающаяся с произвольного x. З а д а ч а  3. 8.

Докажите. Поскольку в теореме 3. Однако эта точка вовсе не обязана быть точкой. Например, рассмотрим для функции f(x) = x. Тогда, как легко видеть, если x. Точка же x = 0 не является локальным минимумом функции f. Заметим также, что описанный метод не различает точек локального и глобального минимумов.

Поэтому для того, чтобы сделать заключение о сходимости xn к точке x* = argmin f(x) приходится налагать дополнительные ограничения, гарантирующие, в частности, существование и единственность решения. Один вариант таких ограничений описывается ниже. Пусть выполнены условия теоремы 3. Тогда приα ∈ (0, 2/Λ)градиентный метод с шагом α сходится со скоростью геометрической прогрессии со знаменателемq = max{ 1 – αλ , 1 – αΛ }.

Д о к а з а т е л ь с т в о. Решение x* = argmin  f(x) существует и единственно в силу теорем 2. Для функции F(x) = f ′(x) воспользуемся аналогом формулы Ньютона — Лейбница.

F(y) = F(x) + ∫1. F ′[x + s(y – x)](y– x) ds,или, для x = x* и y = xn, учитывая, что f ′(x*) = Θ,f ′(xn) = ∫1. Далее, в силу утверждения (2. Rm. Кроме того (см. Поэтому, так как. Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор.

Rm, обозначим его Ln. Неравенство (1. 0) означает, что λ ≤ Ln ≤ Λ. В силу (9) градиентный метод (4) записывается в виде.

Ln(xn – x*). Но тогда. Ln(xn – x*) == (I – αLn)(xn – x*) ≤ I – αLn  ·  xn – x* . Спектр σ(I – αLn) оператора I – αLn состоит из чисел вида σi =1 –αλi, где λi ∈ σ(Ln). В силу (1. 0) и неравенства (2. I – αLn ≤ max{ 1 –αλ , 1 – αΛ } = q. Таким образом. xn+1 – xn ≤ q xn – x* . Из этого неравенства и задачи 3.

Константа q, фигурирующая в теореме 3. Нетрудно видеть, что величина. При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной. Рис. 7. Напомним (см. Если λ < < Λ, то q* ≈ 1 и метод сходится очень медленно. Геометрически случай λ < < Λ соответствует функциям с сильно вытянутыми линиями уровня (см. Простейшим примером такой функции может служить функция на R2, задаваемая формулой.

Рис. 8. Поведение итераций градиентного метода для этой функции изображено на рис. Число μ = Λ/λ (характеризующее, грубо говоря, разброс собственных значений оператора f ′′(x)) называют f.

Если μ > > 1, то функции называют или . Для таких функций градиентный метод сходится медленно. Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Мы опишем сейчас два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.

В этом варианте градиентного метода величина шага αn на каждой итерации выбирается из условия выполнения неравенства. Условие (1. 1) гарантирует (если, конечно, такие αn удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого αn обычно оформляют так. Выбирается число δ ∈ (0, 1) и некоторый начальный шаг α0.

Теперь для каждого n полагают αn = α0 и делают шаг градиентного метода. Если с таким αn условие (1. Если же (1. 1) не выполняется, то умножают αn на δ ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (9) не будет выполняться. В условиях теоремы 3. З а д а ч а  3. 9. Докажите (воспользуйтесь неравенством (8)).

З а д а ч а  3. 1. Сходится ли градиентный метод с дроблением шага для функции f(x) = x pпри p ∈ (1, 2)? Можно показать, что в условиях теоремы 3. Описанный алгоритм избавляет нас от проблемы выбора α на каждом шаге, заменяя ее на проблему выбора параметров ε, δ и α0, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента. Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е.

L ={x ∈ Rm: x = xn – αf ′(xn); α ≥ 0}. Рис. 9. Другими словами, αn выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. Такой вариант градиентного метода называется методом. Заметим, кстати, что в этом методе направления соседних шагов ортогональны.

В самом деле, поскольку функция φ: α → f(xn – αf ′(xn)) достигает минимума при α = αn, точка αn является стационарной точкой функции φ. Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации (1. Такие задачи будут обсуждаться ниже.

Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом. В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.