Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ

Цель работы: Написать программу для минимизации функции одной переменной методом золотого сечения и функции двух переменных методами Хука–Дживса и градиентного спуска.

Теоретические основы

Одномерная минимизация

Метод золотого сечения

Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод золотого сечения. Он состоит в построении последовательности отрезков [а0, b0], [а1, b1], …, стягивающихся к точке пересечения графика функции f(x) с осью x. На каждом шаге, за исключением первого, вычисление значения функции f(x) проводится лишь один раз. Эта точка, называемая золотым сечением, выбирается специальным образом.

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Рисунок 2 – Метод золотого сечения

Поясним сначала идею метода геометрически, а затем выведем необходимые соотношения. На первом шаге процесса внутри отрезка [а0, b0] (рис. 2а) выбираем две внутренние точки х1и х2и вычисляем значения целевой функции f(x1) и f(x2). Поскольку в данном случае Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , очевидно, что решение расположено на одном из прилегающих к x1 отрезков [а0, x1] пли [x1, x2]. Поэтому отрезок [x2, b0] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке [а1, b1] (рис. 2б), где а1 = а0, b1= х2. Нужно снова выбрать две внутренние точки, но одна из них (x1) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку х3, вычислить значение f(х3) и провести сравнение. Поскольку здесь Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , ясно, что решение находится на отрезке [х3, b1].Обозначим этот отрезок [а2, b2], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс повторяется до тех пор, пока длина очередного отрезка [аn, bn] не станет меньше заданной величины Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru .

Теперь рассмотрим способ размещения внутренних точек на каждом отрезке [аk, bk].Пусть длина интервала неопределенности равна l, а точка деления делит его на части l1, l2: Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Из этого соотношения можно найти точку деления, определив отношение Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru :

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Поскольку нас интересует только положительное решение, то

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Отсюда: Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Поскольку заранее неизвестно, в какой последовательности (l1и l2 или l2 и l1)делить интервал неопределенности, то рассматриваются внутренние точки, соответствующие двум этим способам деления.

На рис. 3а точки деления x1, x2выбираются с учетом полученных значений для частей отрезка. В данном случае имеем:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

После первого шага оптимизации получается новый интервал неопределенности – отрезок [а1, b1](рис. 2). Точка x1делит этот отрезок в требуемом отношении, при этом

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Вторая точка деления х3 выбирается на таком же расстоянии от левой границы отрезка, т. е. Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . И снова интервал неопределенности уменьшается до размера:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Тогда координаты точек деления у и z отрезка.[ak, bk]на k+1–м шаге оптимизации (у < z):

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

При этом длина интервала неопределенности равна:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Процесс заканчивается при выполнении условия Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru .

Многомерная минимизация

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

Общая задача нелинейного программирования без ограничений состоит в минимизации функции Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , заданной во всем n–мерном евклидовом пространстве. Функция Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru называется целевой функцией.

Как правило, численные методы нахождения экстремума состоят в построении последовательности векторов Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , удовлетворяющих условию: Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . Методы построения таких последовательностей называются методами спуска. В этих методах элементы последовательности Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru вычисляются по формуле:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

где Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – направление спуска; Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – длина шага в этом направлении.

Как известно, градиент функции в некоторой точке Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru направлен в сторону наискорейшего локального возрастания функции. Следовательно, спускаться нужно в направлении, противоположном градиенту. Вектор, противоположный градиенту, называется антиградиентом. Выбирая антиградиент в качестве направления спуска, приходят к итерационному процессу вида:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , (2)

где Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Все методы спуска, в которых вектор Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru совпадает с антиградиентом, называются градиентными методами. Они отличаются друг от друга только способом выбора шага. Наиболее употребительны метод наискорейшего спуска и метод дробления шага.

В методе наискорейшего спуска величина Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru определяется из условия

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru ,

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

Если Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – ограниченная снизу, непрерывно дифференцируемая функция и для некоторой начальной точки Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru множество Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru также ограничено, то для метода наискорейшего спуска последовательность Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru либо сходится к точке минимума при Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , либо достигает точки минимума за конечное число шагов.

Процесс (2) с дроблением шага протекает следующим образом. Выбираем некоторое начальное значение Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . Общих правил выбора Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru нет: если есть информация о расположении точки минимума, то точку Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru выбираем в этой области. Затем выбираем некоторое Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru и на каждом шаге процесса (2) проверяем условие монотонности Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . Если это условие нарушается, то Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru дробим до тех пор, пока монотонность не восстановится. Для окончания счета используем критерий:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

В этом случае полагаем Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru .

Здесь Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Рисунок 3 – Метод градиентного спуска

Метод Хука–Дживса

Процедура Хука–Дживса представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу.

Исследующий поиск. Для проведения исследующего поиска необходимо знать величину шага, которая может быть различной для разных координатных направлений и изменяться в процессе поиска. Исследующий поиск начинается в некоторой исходной точке. Если значение целевой функции в пробной точке не превышает значение в исходной точке, то шаг поиска рассматривается как успешный. В противном случае надо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой значения целевой функции. После перебора всех n– координат исследующий поиск завершается. Полученную в результате точку называют базовой точкой.

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

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

Как только движение по образцу не приводит к уменьшению целевой функции, точка Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , то она рассматривается как новая базовая точка Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . С другой стороны, если исследующий поиск неудачен, необходимо вернуться в точку Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru и провести исследующий поиск с целью выявления нового направления минимизации. В конечном итоге возникает ситуация, когда такой поиск не приводит к успеху. В этом случае требуется уменьшить величину шага путем введения некоторого множителя и возобновить исследующий поиск. Поиск завершается, когда величина шага становится достаточно малой. Последовательность точек, получаемую в процессе реализации метода, можно записать в следующем виде:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – текущая базовая точка,

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – предыдущая базовая точка,

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – точка, построенная при движении по образцу,

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru – следующая (новая) базовая точка.

Приведенная последовательность характеризует логическую структуру поиска по методу Хука–Дживса.

Алгоритм метода:

1. Выбрать начальную базисную точку b1 и шаг длиной h1 для каждой переменной Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

2. Вычислить f(х) в базисной точке b1 с целью получения сведений о локальном поведении функции f(х). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(х) в базисной точке b1, находится следующим образом:

а) Вычисляется значение функции f(b1) в базисной точке b1.

б) Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , где Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . В противном случае вычисляется значение функции Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , и если ее значение уменьшилось, то b1 заменяем на Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru и т. д. Когда будут рассмотрены все n переменных, мы будем иметь новую базисную точку b2.

в) Если Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

г) Если Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , то производится поиск по образцу.

3. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

а) Разумно двигаться из базисной точки b2 в направлении Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru , поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

В общем случае:

Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru

б) Затем исследование следует продолжать вокруг точки Лабораторная работа №8 МИНИМИЗАЦИЯ ФУНКЦИИ - student2.ru .

в) Если наименьшее значение на шаге 3б) меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3 (bi+2), после чего следует повторить шаг 3а). В противном случае, не производить поиск по образцу из точки b2 (bi+1), а продолжить исследования в точке b2 (bi+1).

4. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Задание

1. Написать программу для минимизации функции ¦(x) методом золотого сечения;

2. Написать программу для минимизации функции ¦(x1, х2) методами Хука–Дживса и градиентного спуска.

Контрольные вопросы

Наши рекомендации