к.р. «Градиентный метод при поиске оптимума». контр. работа.. Градиентный метод при поиске оптимума

• Название: Градиентный метод при поиске оптимума
• Анкор: к.р. «Градиентный метод при поиске оптимума
• Дата: 27.03.2022
• Размер: 231.26 Kb.
• Имя файла: контр. работа..docx
• Тип: Контрольная работа; #419759

МинОБРНАУКИ рОССИИ ФЕДЕРАЛЬНОЕ Государственное БЮДЖЕТНОЕ образовательное учреждение высшего образования «Самарский государственный технический университет»

Контрольная работа по курсу:

«Моделирование и методы планирования эксперимента в электроэнергетике и электротехнике»

На тему: «Градиентный метод при поиске оптимума»

Вариант: №15

Выполнил: студент 3-ЭТФ-ЗФ-Д1/4 Михайлов Н.А.

Проверил: Иванников Юрий Николаевич

Самара, 2022

Содержание.

Введение 3

Эвристические соображения, приводящие к градиентным методам. 8

Градиентный метод с постоянным шагом. 9

Пример исследования сходимости. 10

Теорема об условной сходимости градиентного метода с постоянным шагом. 11

Замечания о сходимости. 13

Теорема о линейной сходимости градиентного метода с постоянным шагом. 14

Об оптимальном выборе шага. 15

Градиентный метод с дроблением шага. 17

Метод наискорейшего спуска. 18

Список Используемой литературы. 20

Введение.

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

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



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



Рис.2. Геометрическая интерпретация градиентного метода

(двумерный случай)

Вначале выбирают начальную точку Если в одномерном случае из нее можно было сдвинуться только влево или вправо, то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 1, иллюстрирующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отношению к точке А (например, направления 1—3), а по другим направлениям приводит к его уменьшению (направления 5—8). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в котором целевая функция возрастает быстрее всего.

Это направление называется градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора градиента функции у =/(*,, х₂, ..., х_п) являются ее частными производными по аргументам, т.е.

&ад/(х₁,х₂,.= {ду/дху,ду/дх₂, ...,ду/дх_п}. 

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

.У' с координатами:





или в векторной форме



где X — постоянный или переменный параметр, определяющий длину рабочего шага. На второй итерации снова вычисляют вектор градиента уже для новой точки .У , после чего по аналогичной формуле переходят в точку х.

Для произвольной к-й итерации имеем



Если отыскивается не максимум, а минимум целевой функции, то на каждой итерации делается шаг в направлении, противоположном направлению градиента. Оно называется направлением антиградиента. Вместо формулы в этом случае будет



Существует много разновидностей метода градиента, различающихся выбором рабочего шага. Можно, например, переходить в каждую последующую точку при постоянной величине X, и тогда длина рабочего шага — расстояние между соседними точками их¹ ' — окажется пропорциональном модулю вектора градиента. Можно, наоборот, на каждой итерации выбирать X таким, чтобы длина рабочего шага оставалась постоянной.

Распространённые и эффективные методы

Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации

f(x) → min,

(1)

где f: R^m → R, укладываются в следующую грубую схему. Начиная с некоторого x⁰ ∈ R^m, строится последовательность {xⁿ} ⊂ R^m такая, что

f(xn+1) < f(xn)

(2)

при всех n ∈ N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xⁿ к xⁿ⁺¹) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Мы будем говорить, что метод, начиная с данного x⁰ ∈ R^m,

а) условно сходится, если последовательность {xⁿ} релаксационна и

f ′(xn) → Θ при n → ∞;

б) сходится, если

xn → x* = argmin f(x) при n → ∞;

в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q ∈ [0, 1)

||xn – x*|| ≤ Cqn;

(3)

г) сверхлинейно сходится, если для любого q ∈ (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);

д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q ∈ [0, 1) и всех n ∈ N

||xn – x*|| ≤ Cq2n.

Если эти свойства выполняются только для x⁰ достаточно близких к x*, то как всегда добавляется эпитет "локально".

Эвристические соображения, приводящие к градиентным методам.

Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xⁿ}, рекуррентно определяемая формулой

xn+1 = xn – αf ′(xn),

(4)

где α - некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xⁿ. Заменим в шаре B(xⁿ, ε) с центром в точке xⁿ функцию f ее линейным (вернее, афинным) приближением:

f(x) ≈ φ(x) ≝ f(xn) + (f ′(xn), x – xn)

(функция φ аппроксимирует f в окрестности точки xⁿ с точностью o(x – xⁿ)). Разумеется, (линейная) безусловная задача φ(x) → min неразрешима, если f ′(xⁿ) ≠ Θ. В окрестности же B(xⁿ, ε) функция φ имеет точку минимума. Эту точку естественно взять за следующее приближение xⁿ⁺¹.

Градиентный метод с постоянным шагом.

В общем случае число α в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:

xn+1 = xn – αnf ′(xn).

(5)

Именно методы, задаваемые формулой (5), называются градентными. Если αⁿ = α при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом α.)

Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида {x ∈ R^m: f(x) = c}. Каждому значению c отвечает своя линия уровня (см. рис. 5).


Рис. 5.

Пример исследования сходимости.

Изучим сходимость градиентного метода с постоянным шагом на примере функции

f(x) = |x|p,

где p > 1 (случай p ≤ 1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xⁿ градиентного метода имеют вид:

xn+1 = xn – αp|xn|p–1sign xn.

(6)

Пределом этой последовательности может быть только 0. Действительно, если x** = lim_n→∞ xⁿ ≠ 0, то, переходя к пределу в (6) при n → ∞, получаем противоречащее предположению x** ≠ 0 равенство

x** = x** – αp|x**|p–1sign  x**,

откуда x** = 0. Очевидно также, что если x⁰ = 0, то и xⁿ = 0 при всех n.

Покажем, что если p < 2, то при любом шаге α > 0 и любом начальном приближении x⁰ (за исключением не более чем счетного числа точек) приближения (6) не являются сходящимися. Для этого заметим, что если 0 < |xⁿ| < (2/αp)^1/2(2–p), то

|xn+1| > |xn|.

(7)

Поэтому, если xⁿ не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.

Теорема об условной сходимости градиентного метода с постоянным шагом.

Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f ′ удовлетворяет условию Липшица:

||f ′(x) – f ′(y)|| ≤ Λ ||x – y|| при всех x, y ∈ Rm.

Тогда при α ∈ (0, 2/Λ) градиентный метод с постоянным шагом условно сходится.

Д о к а з а т е л ь с т в о.  Положим zⁿ = –αf ′(xⁿ) и обозначим f(xⁿ + tzⁿ) через φ(t). Тогда, как легко видеть,

φ′(t) = (f ′(xn + tzn), zn)

и поэтому по формуле Ньютона — Лейбница для функции φ

f(xn+1) – f(xn) = f(xn + zn) – f(xn) = φ(1) – φ(0) =

=  ∫ 1 0 φ′(s) ds =  ∫ 1 0 (f ′(xn+ szn), zn) ds.

Добавив и отняв (f ′(xn), zn) = ∫01(f ′(xn), zn) dsи воспользовавшись неравенством (x, y) ≤ ||x|| · ||y||, получим

f(xn+1) – f(xn) = (f ′(xn), zn) +  ∫ 1 0 (f ′(xn + szn) – f ′(xn), zn) ds ≤

≤ (f ′(xn), –αf ′(xn)) +  ∫ 1 0 ||f ′(xn + szn) – f ′(xn)|| · ||zn|| ds.

Учитывая условие Липшица для f ′, эту цепочку можно продолжить:

f(xn+1) – f(xn) ≤ –α||f ′(xn)||2 + Λ ||zn||2 ∫ 1 0 s ds = = – α||f ′(xn)||2 +  Λα2 2 ||f ′(xn)||2 = –α||f ′(xn)||2 ( 1 –  Λα 2 ) .

(8)

Поскольку 1 – Λα/2 > 0, последовательность {f(xⁿ)} не возрастает и, следовательно, релаксационность {xⁿ} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xⁿ)} сходится. Поэтому, в частности, f(xⁿ⁺¹) – f(xⁿ) → 0 при n → ∞. Отсюда и из (8) получаем

||f ′(xn)||2 ≤ α–1 ( 1 –  Λα 2 ) –1 [f(xn) – f(xn+1)] → 0 при n → ∞.

Замечания о сходимости.

Подчеркнем, что теорема 3.5 не гарантирует сходимости метода, но лишь его условную сходимость, причем, локальную. Например, для функции f(x) = (1 + x²)^–1 на R последовательность {xⁿ} градиентного метода с постоянным шагом, начинающаяся с произвольного x⁰ стремится к ∞.

Поскольку в теореме 3.5 градиент непрерывен, любая предельная точка последовательности {xⁿ} является стационарной. Однако эта точка вовсе не обязана быть точкой минимума, даже локального. Например, рассмотрим для функции f(x) = x²sign x градиентный метод с шагом α ∈ (0, 1/2). Тогда, как легко видеть, если x⁰ > 0, то xⁿ → 0 при n → ∞. Точка же x = 0 не является локальным минимумом функции f.

Заметим также, что описанный метод не различает точек локального и глобального минимумов. Поэтому для того, чтобы сделать заключение о сходимости xⁿ к точке x* = argmin f(x) приходится налагать дополнительные ограничения, гарантирующие, в частности, существование и единственность решения задачи (1). Один вариант таких ограничений описывается ниже.

Теорема о линейной сходимости градиентного метода с постоянным шагом.

Пусть выполнены условия теоремы 3.5 и, кроме того, f дважды непрерывно дифференцируема и сильно выпукла с константой λ. Тогда при α ∈ (0, 2/Λ) градиентный метод с шагом α сходится со скоростью геометрической прогрессии со знаменателем q = max{|1 – αλ|, |1 – αΛ |}:

||xn – x*|| ≤ qn||x0 – x*||.

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

F(y) = F(x) +  ∫ 1 0 F ′[x + s(y – x)](y– x) ds,

или, для x = x* и y = xⁿ, учитывая, что f ′(x*) = Θ,

f ′(xn) =  ∫ 1 0 f ′′[x* + s(xn – x*)](xn – x*) ds

(9)

(здесь мы, как и выше, воспользовались задачей 2.3). Далее, в силу утверждения (2.5) из п. 2.3 f ′′(x) ≤ Λ при всех x ∈ R^m. Кроме того (см. задачу 2.15), по условию f ′′(x) ≥ λ при тех же x. Поэтому, так как

λ||h||2 ≤ (f ′′[x* + s(xn –x*)]h, h) ≤ Λ ||h||2,

выполнено неравенство

λ||h||2 ≤  ( ( ∫ 1 0 f ′′[x* + s(xn –x*)] ds ) h, h )  ≤ Λ ||h||2.

(10)

Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на R^m, обозначим его Lⁿ. Неравенство (10) означает, что λ ≤ Lⁿ ≤ Λ. В силу (9) градиентный метод (4) записывается в виде

xn+1 = xn – αLn(xn – x*).

Но тогда

||xn+1 – xn|| = ||xn – x* –αLn(xn – x*)|| = = ||(I – αLn)(xn – x*)|| ≤ ||I – αLn|| · ||xn – x*||.

Спектр σ(I – αLⁿ) оператора I – αLⁿ состоит из чисел вида σ_i = 1 –αλ_i, где λ_i ∈ σ(Lⁿ). В силу (10) и неравенства (2.3),

1 – αλ ≥ σi ≥ 1 – αΛ,

и следовательно (см. неравенство (2.4))

||I – αLn|| ≤ max{|1 –αλ|, |1 – αΛ |} = q.

Таким образом,

||xn+1 – xn|| ≤ q||xn – x*||.

Из этого неравенства и задачи 3.1 вытекает утверждение теоремы.

Об оптимальном выборе шага.

Константа q, фигурирующая в теореме 3.7 и характеризующая скорость сходимости метода, зависит от шага α. Нетрудно видеть, что величина

q = q(α) = max{|1 – αλ|, |1 – αΛ |}

минимальна, если шаг α выбирается из условия |1 – αλ| = |1 – αΛ | (см. рис. 7), т. е. если α = α* = 2/(λ+ Λ). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной

q = q* =  Λ – λ Λ + λ .

Рис. 7.

Напомним (см. п. 2.3), что в качестве λ и Λ могут выступать равномерные по x оценки сверху и снизу собственных значений оператора f ′′(x). Если λ << Λ, то q* ≈ 1 и метод сходится очень медленно. Геометрически случай λ << Λ соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 8). Простейшим примером такой функции может служить функция на R², задаваемая формулой

f(x1, x2) = λx21+ Λ x22с λ << Λ.

Рис. 8.

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

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

Градиентный метод с дроблением шага.

В этом варианте градиентного метода величина шага αⁿ на каждой итерации выбирается из условия выполнения неравенства

f(xn+1) = f(xn – αnf ′(xn)) ≤ f(xn) – εαn||f ′(xn)||2,

(11)

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

Можно показать, что в условиях теоремы 3.7 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора α на каждом шаге, заменяя ее на проблему выбора параметров ε, δ и α⁰, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.

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

Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xⁿ будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x ∈ R^m: x = xⁿ – αf ′(xⁿ); α ≥ 0}:

αn = argminα∈[0, ∞)f(xn – αf ′(xn)).

(12)

Рис. 9.

Другими словами, αⁿ выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 9). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция φ: α → f(xⁿ – αf ′(xⁿ)) достигает минимума при α = αⁿ, точка αⁿ является стационарной точкой функции φ:

0 = φ′(αn) =  d dα f(xn – αf ′(xn)) | α=αn =

= (f ′(xn – αnf ′(xn)), –f ′(xn)) = –(f ′(xn+1), f ′(xn)).

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

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

Список используемой литературы.

1. 
   Макаричев Ю.А., Иванников Ю.Н. М 30 Методы планирование эксперимента и обработки данных: учеб. пособие / Макаричев Ю.А., Иванников Ю.Н. – Самара: Самар. гос. техн. ун-т, 2016
   
2. 
   Геминтерн В. И., Каган Б. М. Методы оптимального проектирования. – М.: Энергия, 2006.
   
3. 
   Сборник задач по математике для вузов. Методы оптимизации/ Под ред. А. В. Ефимова – М.: Наука, 2010.
   
4. 
   Интрилигатор М. Математические методы оптимизации и экономическая теория. – М.: Прогресс, 2015.
   
5. 
   Шуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 2017.