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

ВВЕДЕНИЕ

 

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. Цели работы

Главной целью  является создание лабораторного практикума по методам оптимизации. Второй целью  является изучение пакета 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.

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

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

, = = const. (8)

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

,   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=

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

K ≈1−

.

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