Исследование простого градиентного метода

 .                   (15)

Сравнение формул (14) и (15) показывает, что оценка скорости сходимости обоих методов практически совпадает. Наблюдается полное совпадение по скорости убывания значения функции, а скорость убывания модуля вектора ошибки |хⁱ — х⁺| в простом градиентном методе даже несколько выше, так как имеет место неравенство

.

Однако в  тех случаях, когда отсутствует  априорная информация относительно минимизируемой функции F (х), метод наискорейшего спуска может оказаться предпочтительным, так как он гарантирует всегда ту же скорость сходимости, что и простой градиентный метод с оптимальным выбором шага α⁰, зависящего от параметров т и М.[1]

 

1.2.2 Метод Ньютона

Это итерационный численный  метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции производится при помощи отыскания стационарной точки, т.е. точки , удовлетворяющей уравнению , которое решается методом Ньютона.

Если  – точка, полученная на k-м шаге, то функция аппроксимируется своим уравнением касательной:

,

а точка  выбирается как пересечение этой прямой с осью , т.е.

.

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

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

Когда начальная точка  итераций достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.

Хороший способ гарантировать  глобальную сходимость этого метода состоит в комбинировании его  с другим методом для быстрого получения хорошей аппроксимации  искомого оптимума. Тогда несколько  итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности. [2]

 

 

1.2.3 Метод сопряженных градиентов

Метод сопряженных  градиентов, предложенный Хестеном и  Штифелем в 1952г., является одним из эффективнейших современных методов безусловной минимизации функций. Как будет показано ниже, этот метод можно рассматривать как оптимальную реализацию градиентного метода применительно к квадратичной функции. Метод сопряженных градиентов дает точное решение задачи минимизации произвольной квадратичной функции за  или меньшее число шагов, где n – число переменных. При этом метод сводит исходную задачу к последовательности задач минимизации функции одной переменной и в процессе его применения необходимо вычислять только значения градиента исходной функции. Реализация этого метода практически не сложнее реализации метода наискорейшего спуска.

Выведем основные расчетные  соотношения метода сопряженных  градиентов. Пусть требуется найти точку минимума x⁺ для квадратичной формы q(x), определяемой выражением

q(x)= x^*Ax+b^*x+c,                                           (16)

где А – положительно определенная симметричная матрица. Зададимся точкой начального приближения х⁰ и построим первое приближение вида

x¹ = x⁰ – α

 

где α₀ -  выбирается из равенства

q(x⁰ – α₀s¹)=

 

Обозначим через sⁱ вектор, определяющий направление движения на i-м шаге. В общем случае, если , то (i+1)-е приближение будем строить следующим образом:

                    (17)

где параметры 𝛼_i и β_jⁱ (j = 1, 2,…, i; i = 0, 1, 2,…) определяются из условия минимума:

.        (18)

Если  , то в соответствии с положительной определенностью матрицы А точка  xⁱ есть точка минимума функции и итерационная процедура считается законченной. Из равенства (16) и (17) легко привести рекуррентное соотношение для градиентов функции в последующих итерациях:

.     (19)

 

Учитывая выражение  функции q(x) и положительную определенность матрицы A преобразуем условие (18) к виду

.

 Очевидно, что из условия следует , поэтому вышеприведенное условие можно представить в виде

              (20)

Сопоставляя равенство (19) и тождество

,

которое следует  из формулы (17), получим   

Иначе говоря, при реализации итерационной процедуры (17) векторы градиентов в различных итерациях взаимно ортогональны. Это указывает на конечность данной процедуры, так как в n-мерном пространстве не может существовать более чем n взаимно ортогональных векторов, то есть итерационная процедура должна закончиться не более чем за n шагов. Условие (20) при j=1, 2,…,i можно так же представить в виде

.

Следовательно,

.                                       (21)

Это означает, что  направление движения в различных  итерациях процедуры (17) взаимно А-ортогональны.

Используя равенство (21), определим параметры и вектор Sⁱ⁺¹:

Отсюда, используя  формулу (19), получим выражение для искомых параметров:

.

Принимая во внимание условие ортогональности, окончательно получим:

 j=1, 2,…, i — 1;

                                  (22)

Выражение для  параметра а_{ можно получить, подставляя формулы (17) и (19) в условие (20):

Следовательно,

                                              (23)

Из формул (22) и (23) следует

                                         .  (24)

Подставляя  выражения (22), (23), (24) в формулу (17), получим окончательные соотношения для метода сопряженных градиентов:

x^i+l = хⁱ − α_isⁱ⁺¹,  i = 0,1,2,...,

где

                              (25)

Расчетные формулы (25) могут оказаться неудобными, так как для их использования требуется знание матрицы вторых производных А при вычислении а_i. Учитывая выражение (18), можно представить формулы (25) в виде:

x^i+l = хⁱ − α_isⁱ⁺¹,  i = 0,1,2,...;

;

В эти формулы  матрица А не входит, но при реализации рекуррентной последовательности требуется вычисление градиента функции q (x) и определение точки минимума функции q (х) в направлении sⁱ⁺¹.

Из последних  соотношений следует, что рассматриваемый  метод может быть применен к функции  произвольного типа. Анализ сходимости показывает, что метод сопряженных градиентов имеет примерно такую же широкую область сходимости, что и метод наискорейшего спуска, но скорость сходимости квадратичная. В случае применения метода к неквадратичным функциям целесообразно время от времени производить «обновление» метода, т. е. после ряда итераций (порядка п) в точке x^k вновь выбирать       .

Метод сопряженных градиентов относится к группе методов сопряженных направлений. Другие методы этой группы являются более сложными в реализации, но имеют повышенную скорость сходимости.

Все перечисленные  методы характеризуются одним существенным недостатком: они позволяют найти только локальный минимум. Легко показать, что если функция выпуклая, т. е. для любых точек х¹ и х² и произвольного 0≤ λ≤1 имеет место неравенство

F (𝜆х¹ + (1 — λ) х²) ≤ 𝜆F (х¹) + (1 — 𝜆) F (х²),                 (26)

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

Единственная возможность нахождения глобального экстремума заключается в применении вышеизложенных локальных методов при различных точках начального приближения х⁰. После проведения достаточного числа процедур поиска локальных минимумов следует выбрать точку с минимальным значением функции. [1]

 

1.2.4 Функция Розенброка

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

С целью сравнения  эффективности различных алгоритмов разработаны специальные (так называемые тестовые) функции, имеющие "неприятные" для методов поиска экстремума особенности. Одна из самых известных - функция Розенброка (автора многих популярных алгоритмов поиска экстремума).

Формула, определяющая функцию Розенброка:

Эта функция имеет  крайне пологий изогнутый овраг, что сильно затрудняет поиск минимума (значение аргументов в точке минимума очевидны: x* =1, y* = 0 (при этом f(x*,y*) = 0 ). Благодаря "неприятным" для методов поиска экстремума особенностям функция Розенброка часто используется для испытания сходимости различных алгоритмов и для их сравнения. [3]

 

1.3 Постановка задачи

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

В работе предполагается создать лабораторный практикум по безусловной оптимизации для студентов технических вузов. В частности для СПбГТИ(ТУ). Лабораторный практикум содержит восемь вариантов, а значит, он может проводиться среди восьми человек, либо среди восьми бригад, содержащих не более трех человек. Длительность занятия составляет два академических часа. Студентам предоставляется возможность исследования работы методов безусловной оптимизации, таких как: простой градиентный метод, метод наискорейшего спуска, метод Ньютона, метод сопряженных градиентов.

 

 

 

2. МЕТОДИКА ПРОВЕДЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ

 

Для выполнения лабораторной работы созданы  программы в пакете MATLAB, соответствующие каждому варианту.

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

1. Целевая функция в виде квадратичной формы

Зададимся целевой функцией в виде суммы квадратичной и линейной формы f=x'ax+b'x

 

Таблица 1 – Варианты для квадратичной формы

№	Матрица кв.формы	Вектор линейной формы	Преобразование  координат
1	a=    0.77      0          0      0.77	b=   1        1	S=   0.05      1        0.3     0.1
2	a=   4      0          0      0.77	b=   1        1	S=   0.05      1        0.3    0.1
3	a=   1.25   0.65       0.65   1.25	b=   0.75        0.3	S=   -0.5      1        -0.3    0.1
4	a=   1.5   0.65        0.65   1.5	b=   0.75        0.3	S=   0.05      1        0.3     0.1
5	a=   1.9      0.6        0.6      1.9	b=   0.65        0.4	S=   -0.5      -1        -0.4  -0.1
6	a=   1.9      0.5        0.5      1.9	b=   0.7        0.4	S=  -0.5      -1       -0.4  -0.1
7	a=   1.54 0.6        0.6    1.54	b=   0.7        0.4	S=   0.05      1        0.3     0.1
8	a=   1.3      0.4        0.4   1.3	b=   0.75        0.3	S=   -0.05     1       -0.3    0.1