Методы безусловной оптимизации

 

1. Метод Коши

 

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

,

Ñf = - градиент функции f(x)

Алгоритм метода выглядит следующим  образом:

x(k + 1) = x(k) - a(k)×Ñf(x(k)),  где Ñf (x) – градиент.

Значение a(k) на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума f(x) вдоль направления градиента Ñf(x(k)). Если в качестве a(k) взять некоторое положительное число, то получится простейший градиентный алгоритм:

f(k + 1) = x(k) - a×Ñf(x(k))

Одно из главных достоинств метода Коши является его устойчивость, так  как всегда выполняется условие

f(x(k + 1))  £ f(x(k))

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

 

Нахождение минимума целевой функции методом Коши.

 

Исходные  данные:

 

Вычислим компоненты градиента:

Итерация 1:

Новое приближение определим по формуле:

Подставляя эти значения в выражение  целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

 

Итерация 2:

Новое приближение определим по формуле:

Подставляя эти значения в выражение  целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

 

Итерация 3:

Новое приближение определим по формуле:

Подставляя эти значения в выражение  целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Итерация 4:

Новое приближение определим по формуле:

Подставляя эти значения в выражение  целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Решение поставленной задачи методом  Коши представлено на рисунке 5.

Рисунок 5 – Решение задачи методом Коши

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

 

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

x(k+1) = x(k) – α(k) V2f(x(k))-1 Vf(x(k)), где 

- гессиан (матрица Гессе)

 

В случае, когда гессиан положительно определён, направление по методу Ньютона оказывается  направлением спуска.

 

Нахождение минимума целевой функции методом Ньютона.

 

Исходные  данные:

 

.

 

.

Из формулы

,

Получаем:

, что совпадает с точным решением.

 

Решение поставленной задачи методом Ньютона  представлено на рисунке 6.

Рисунок 6 – Решение задачи методом  Ньютона

 

 

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

 

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

Операции  аргумента проводятся по формуле

                        x(k + 1) = x(k) + a(k)×s(x(k))

Направление поиска на каждой итерации определяется с помощью формулы

                        s(k) = -g(k) + ×s(k - 1)

В этом случае направление s(k)  будет C - сопряжено  со всеми ранее построенными направлениями  поиска.

Если  функция f(x1, x2, ... , xN) квадратичная, то для  нахождения точки экстремума требуется  определить N-1 таких направлений  и провести поиски вдоль каждой прямой.  Если f(x) не является квадратичной, то количество поисков возрастет.

Используемые  в методе формулы:

Градиент  квадратичной функции:

Vf(x) = Vg(x) = Cx + b = g(x).

Изменение градиента при переходе от точки  х(0) к точке х(1):

Δg(x) = g(x(1)) – g(x(0)) = C(x(1) – x(0))

Δg(x) = CΔx

Изменения аргумента:

x-(k+1) = x(k) – α(k)s(x(k)).

Направление поиска:

s(k) = -g(k) + ∑ γ(i) s(i) , s(0) = -g(0), γ(i) =

s(k) = -g(k) + *s(k+1)           (рекуррентная формула Флетчера-Ривса)

 

Нахождение минимума целевой функции  методом сопряжённых градиентов.

 

Исходные данные:

 

Шаг 1:

.

.

 

Шаг 2: поиск  вдоль прямой

.

.

.

 

.

.

.

 

Шаг 3: k = 1:

 

Шаг 4: поиск  вдоль прямой

Таким образом, - искомая точка.

Решение поставленной задачи методом сопряжённых  градиентов представлено на рисунке 7.

Рисунок 7 – Решение задачи методом сопряжённых градиентов

4. Квазиньютоновский метод

 

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

                                               x(k+1) = x(k) + a(k)×s(k)

Направление поиска определяется выражением

s(k) = -A(k)×Ѧ(x(k)),  где A(k) - матрица порядка N*N (метрика)

Матрица A – вычисляется по формуле

           A(k+1) = A(k) +Ac(k), где 

           Ac(k) = ,      (1)

где Dg(k-1) = g(k) - g(k-1)   изменение градиента на предыдущем шаге.

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

 

Нахождение минимума целевой функции  Квазиньютоновским методом:

 

Исходные данные:

 

 

Шаг 1.

Положим .

 

Шаг 2. Поиск  вдоль прямой приводит к результату, полученному в предыдущем методе:

.

 

Шаг 3.

,

 

Шаг 4. Поиск  вдоль прямой.

Решение поставленной задачи квазиньтоновским методом представлено на рисунке  8.

Рисунок 8 – решение задачи квазиньтоновским методом

 

Заключение

 

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

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

 

Список литературы

 

1. Амосов А. А. , Дубинский Ю.  А., Копченова Н. В. Вычислительные  методы для инженеров: Учеб. пособие.  –  М.: Высш. шк., 1994.

2. Лесин В. В., Лисовец Ю. П.  Основы методов оптимизации. –   М.: Изд-во МАИ, 1998.

3. Пантелеев А. В.,  Летова Т.  А. Методы оптимизации в примерах  и задачах. –  М.: Высш. шк., 2002.

4. Общие требования к структуре,  оформлению и представлению курсовых  проектов и работ. – Киров: ВятГТУ,2004.