Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

ВВЕДЕНИЕ

Метод безусловной оптимизации широко используется при моделировании, при решении задач управления, при решении задач идентификации и др.

В теории управления эти методы, как правило, являются вспомогательными.

Например, в теории адаптивных систем широко применяется процедура градиентного метода. В теории нейронных сетей при настройке нейронных моделей часто используются метод наискорейшего спуска, метод Ньютона, квазиньютоновские методы и метод сопряженных градиентов. Кроме этого, безусловная оптимизация используется при решении задач связанных с оптимизацией химико-технологических систем при оперативном управлении в АСУТП.

Такие задачи рассматриваются в рамках дисциплины оптимизации систем управления.

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

АНАЛИТИЧЕСКИЙ ОБЗОР

Цели работы

Главной целью является создание лабораторного практикума по методам оптимизации. Второй целью является изучение пакета MATLAB. Также целью является изучение методов оптимизации.

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

В работе исследовались четыре метода:

1. Простой градиентный алгоритм

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

3. Метод Ньютона

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

1.2 Рассмотрение методов оптимизации

1.2.1 Градиентные методы. Простой градиентный метод и метод наискорейшего спуска

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

Рисунок 1 – Линии равного уровня

При проектировании систем автоматического управления часто приходится сталкиваться с задачей выбора некоторых параметров х⁺ из условия минимума некоторого критерия качества функционирования системы F. В соответствии с этим рассмотрим задачу нахождения вектора х⁺ = (x₁⁺, x₂⁺, . . ., x_n⁺) из условия

F (x⁺) = min_y F (у),

где F (у) — F (y₁ у₂ . . у_п) — функция векторного переменного у, определяющая связь минимизируемого критерия F с управляемыми параметрами у = (у_1, у₂, . .., у_п).

Исторически первым подходом к решению этой задачи является аналитический подход, основанный на использовании необходимых условий минимума. Как известно, эти условия

(1)

сводят исходную задачу к решению системы n нелинейных уравнений относительно n компонент вектора х⁺ = (x₁⁺,x₂⁺,. . .,x_n⁺). Эти уравнения могут иметь сложный вид и допускать не единственное решение. После нахождения корней уравнения (1) необходимо исследовать характер поверхности функции в окрестности точки x⁺, чтобы выделить локальные точки минимума. Аналитический метод минимизации оказывается эффективным обычно только в тех случаях, когда известно аналитическое выражение минимизируемой функции F(у). Практически при оптимизации систем автоматического управления более целесообразно применять численные методы минимизации.

Старейшим численным методом решения этой задачи является градиентный метод, алгоритм которого имеет, вид

xⁱ⁺¹=xⁱ-a_i , i=0, 1, 2,…, (2)

где a- значение шага на i-й итерации.

Точка х⁰ называется начальным приближением метода.

Градиентный метод является типичным представителем линейных методов. Как следует из равенства (2), очередное приближение x^i+l получается из предыдущего х¹ путем движения в направлении антиградиента. Это направление наиболее быстрого убывания функции в окрестности точки х¹, если предположить, что здесь функция достаточно точно аппроксимируется линейной функцией.

Одним из недостатков всех линейных методов, в том числе и градиентных, является зависимость итерационной последовательности от выбранной системы координат и, в частности, от масштабов переменных функции. Пусть, например, при использовании формулы градиентного метода (2) была получена итерационная последовательность {xⁱ}. Затем была введена новая система координат, причем координаты новой системы у и старой системы х связаны соотношением

Aу = х,

где A — неособенная матрица размерности [n, n]. В пространстве переменных y градиентный метод минимизации функции

F (x) = F (Ау) = Ф (у)

будет иметь вид

(3)

Предположим, что в пространстве у градиентный метод осуществляется с теми же значениями шага , что и в пространстве x, причем начальное приближение у⁰ естественным образом согласуется с приближением x⁰:

x⁰ = Ay⁰.

Произведем пересчет последовательности точек {yⁱ} в пространство параметров х. Соответствующие точки обозначим x^~i:

x^~i=Ayⁱ (4)

Подставляя в равенство (3) выражение для производной функции Ф (у):

и учитывая формулу (4), получим рекуррентное соотношение для последовательности {xⁱ} в следующем виде:

(5)

где знак * означает операцию транспонирования матрицы.

Сравнивая формулы (2) и (5), получаем, что в общем случае изменение системы координат изменяет итерационную последовательность, получаемую в процессе применения градиентного метода. В частности, из соотношения (5) видно существенное влияние масштабов для оптимизируемых параметров. Итерационная последовательность {xⁱ} будет полностью совпадать с последовательностью {xⁱ} только в том случае, если

АА* = Е, (6)

где E — единичная матрица. Как известно из линейной алгебры , матрица A, удовлетворяющая условию (6), называется ортогональной, а соответствующее преобразование — ортогональным. Геометрически ортогональное преобразование соответствует повороту системы координат в пространстве.

Из равенства (6) видно, что процедура вычисления обратной матрицы для ортогональной матрицы сводится просто к операции транспонирования:

А^-1 = А*.

Из формулы (5) следует, что применение градиентного метода имеет столько же оснований, что и использование метода, основанного на соотношении

, (i = 0,1,2,...), (7)

где В — произвольная симметричная положительно определенная матрица. Действительно, так как для такой матрицы всегда можно найти неособенную матрицу С, удовлетворяющую условию

СС* = В,

то итерационную процедуру (7) можно рассматривать как обычный градиентный метод в пространстве параметров z, связанных с параметрами х посредством соотношения

х = Сz.

Наиболее широко распространены две модификации градиентного метода:

Простой градиентный метод, или метод простой итерации, где размер шага остается постоянным в течение всей итерационной процедуры:

, = = const. (8)

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

, i=0, 1, 2, …

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

, (9)

где Q — симметричная положительно определенная матрица.

Введем новую систему переменных у = (у₁ у₂, . . у_п), связанных с исходными переменными x посредством ортогонального преобразования А:

х = Ау; АА* = Е.

В новой системе координат функция F (x), выраженная через переменные у, имеет вид

Ф (y) = F(Ay) =

y*A*QAy.

Выберем ортогональное преобразование А из условия приведения матрицы A*QA к диагональному виду. В линейной алгебре доказывается возможность и предлагаются методы решения подобной задачи. Полученную таким образом диагональную матрицу обозначим Λ. Диагональные элементы матрицы Λ будем обозначать λ_1, λ_2,…, λ_n. Как известно, эти параметры называются собственными значениями матрицы Q.

Особый интерес представляют минимальное собственное значение m = min{λ_1, λ_2,…, λ_n } и максимальное собственное значение М = max {λ_1, λ_2,…, λ_n }. Вследствие положительной определенности матрицы Q значения т и М должны быть положительными:

A*QA =Λ

В этом случае функция Ф (у) имеет существенно более простой вид

В соответствии с этим простой градиентный метод применительно к этой функции Ф (у) определит следующую итерационную, последовательность точек {yⁱ}:

i= 0, 1, 2,...; k=1, 2,... п. (10)

Как было показано выше, если матрица А ортогональная и имеет место равенство х⁰ = А у⁰, то точки итерационной последовательности {yⁱ} находятся в простом соответствии с точками итерационной последовательности {xⁱ }, полученной применением простого градиентного метода к функции (9):

х¹ = Ау¹, .

Отсюда следует, что модуль вектора хⁱ совпадает с модулем вектора уⁱ:

x^i*xⁱ=y^i*A^*Ayⁱ=y^i*yⁱ. (11)

Из равенства (10) легко получить выражение компонент вектора y^i+l через компоненты у⁰:

i=0,1,2…; k=1, 2,…, n. (12)

Анализируя равенство (12), можно заключить, что когда о значении начального приближения у⁰ ничего неизвестно, естественно выбирать значение шага градиентного метода из условия

Решая это уравнение, получим

, (13)

_k ^.

Используя равенства (11), (12) и решение (13), нетрудно получить оценки скорости сходимости:

Заметим, что так как для рассматриваемого случая функция F(x) достигает своего минимума в точке х⁺= 0 и минимальное значение F(0) = 0, то окончательные оценки скорости сходимости простого градиентного метода при оптимальном способе выбора шага имеют следующий вид:

(14)

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

Из оценок (14) следует, что для квадратичной функции F(х), определяемой формулой (9), итерационная последовательность {xⁱ}, построенная на основе простого градиентного метода с оптимальным значением величины шага, сходится к истинной точке минимума х⁺ = 0 по закону геометрической прогрессии с знаменателем Соответствующее значение функции при этом убывает также по закону геометрической прогрессии с знаменателем Это означает, что простой градиентный метод сходится тем быстрее, чем меньше отличаются величины максимального и минимального собственных значений.

Отношение р = называют коэффициентом обусловленности матрицы Q. Если значение р велико, то матрица считается плохо обусловленной, если р≈1, матрица хорошо обусловлена. Подставляя выражение для р в формулу для знаменателя геометрической прогрессии k, получим связь k и р:

Отсюда для плохо обусловленных матриц имеет место приближенное равенство

K ≈1−

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

. (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, соответствующие каждому варианту.

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

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

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

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

№

Матрица кв.формы

Вектор линейной формы

Преобразование координат

a= 0.77 0

0 0.77

b= 1

S= 0.05 1

0.3 0.1

a= 4 0

0 0.77

b= 1

S= 0.05 1

0.3 0.1

a= 1.25 0.65

0.65 1.25

b= 0.75

0.3

S= -0.5 1

-0.3 0.1

a= 1.5 0.65

0.65 1.5

b= 0.75

0.3

S= 0.05 1

0.3 0.1

a= 1.9 0.6

0.6 1.9

b= 0.65

0.4

S= -0.5 -1

-0.4 -0.1

a= 1.9 0.5

0.5 1.9

b= 0.7

0.4

S= -0.5 -1

-0.4 -0.1

a= 1.54 0.6

0.6 1.54

b= 0.7

0.4

S= 0.05 1

0.3 0.1

a= 1.3 0.4

0.4 1.3

b= 0.75

0.3

S= -0.05 1

-0.3 0.1

Исследование простого градиентного метода 📙 Дипломная → 🆔 7272