Министерство образования и науки Российской Федерации

Министерство образования и науки Российской Федерации

ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина»

ИРИТ — РТФ

Кафедра «Информационные технологии»

МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

Методические указания по дисциплине

«Методы оптимизации»

Методические указания предназначены для студентов направления 230100 - ИиВТ, изучающих дисциплину «Методы оптимизации». В методических указаниях рассмотрен ряд методов безусловной оптимизации функции одной переменной.

СОДЕРЖАНИЕ

Введение
Постановка задачи
Численные методы безусловной оптимизации
Метод перебора
Алгоритмс Свена
Метод поразрядного поиска
Метод половинного деления
Трехточечная схема половинного деления
Метод золотого сечения
Метод Фибоначчи
Задание на выполнение лабораторной работы

ВВЕДЕНИЕ

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

ПОСТАНОВКА ЗАДАЧИ

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

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

Задача 1:

Задача 2:

При этом решение задачи 2 можно свести к решению задачи 1:

;

Аналитическое решение задачи безусловной оптимизации функции одной переменной основано на том, что если функция f (x) имеет в точке непрерывные производные до второго порядка включительно; и , а , то – точка локального минимума; если же , а , то – точка локального максимума.

ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Пусть требуется решить задачу . Применение численных методов

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

1. Нахождение отрезка, внутри которого находится только одна точка экстремума;

2. Вычисление локального минимума, принадлежащего заданному отрезку с необходимой точностью.

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

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

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

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

Эффективность алгоритма определяется способом выбора критерия. Используются следующие критерии:

1. Контроль значения целевой функции ;

2. Контроль расстояния между соседними точками ;

3. Контроль значения вектора градиента .

Удачная работа алгоритма определяется выбором:

1. Вектора начального приближения ;

2. Параметрами

3. Выбором величины шага h, перемещения вдоль заданного направления.

f(x)

- слишком

-слишком маленький

x

На рисунке шаг - мал, поиск оптимального решения пойдет достаточно долго, а шаг - велик, точка экстремума пропущена.

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

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

Функция f(x) называется унимодальной на отрезке [a, b], если

1. имеет единственную точку минимума x* на этом отрезке

2. f(x) монотонно убывает на [a, x*], возрастает на [x*, b].

Решение задачи оптимизации идет в два этапа: 1 этап – этап поиска начального интервала неопределенности ; 2 этап – этап уточнения положения точки минимума.

Существуют две различные стратегии выбора точек, в которых осуществляется вычисление значения функции.

1) Если все точки задаются заранее – это пассивная стратегия

2) Если пробные точки выбираются с учетом результатов предыдущих измерений – последовательная стратегия.

МЕТОД ПЕРЕБОРА

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

Разобьем отрезок [ a, b ] на n равных частей точками деления:

Вычислив значения в точках , путем сравнения найдем точку , где m - это число от 0 до n, такую, что , для всех i от 0 до n.

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

а b

Стратегия выбора - пассивная стратегия.

АЛГОРИТМ СВЕННА

Исходные данные: - начальная точка; D - длина шага. (k+1)-ая точка определяется по рекуррентной формуле: x^k+1 = x^k + 2^k ´ D, k = 0, 1, 2,...

Знак D определяется путём сравнения значений f(x₀), f(x₀ - êD ê), f(x₀ + êD ê). Рассмотрим четыре ситуации:

Ситуация 1:

Ситуация 2:

Ситуация 3:

Ситуация 4:

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

Схема алгоритма:

1) Выбираем

2) Вычисляем

3) Проводим сравнение . Если ситуация 3, то начальный интервал неопределенности найден , переход к п.6.

Если ситуация 4, то функция не является унимодальной, переход к п.7.

Если ситуация 1, то , переход к п.4.

Если ситуация 2, то , переход к п.4

4)

5) Если и , то , переход к п.4. Если и , то , переход к п.4. Если и , то , переход к п.6. Если и , то переход к п.6.

6) Интервал [a,b] неопределенности найден, переход к п.8.

7) Интервал неопределенности не найден.

8) Конец алгоритма.

Эффективность поиска зависит от величины шага D. Если шаг поиска D велик - получаем грубые оценки координат граничных точек. Если шаг поиска D мал - для вычисления граничных точек может потребоваться большой объём вычислений.

МЕТОД ПОРАЗРЯДНОГО ПОИСКА

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

Схема алгоритма:

1)

2)

3)

4) Если , то направление поиска выбрано удачно, переход к п. 5, в противном случае

если , то , иначе

переход к п.6

5)

Если , то переходим к п.3, иначе – к п. 6

6) Если , то переходим к п. 8, иначе к п. 7

7) , меняем направление движения (знак «-») и переходим к п. 3

8)

МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ

x

В методе половинного деления вычисляется середина отрезка [ a,b ], т.е. точка .

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

1. если , то

2. если , то .

.

Схема алгоритма:

1) - допустимое число итераций,

2)

3)

4)

5) Если , то

Если , то

6) Если , то переходим к п. 7, иначе k=k+1 и если , то переходим к п. 2, иначе – к п. 8

7) и к п. 9

8) Превышено и к п. 9

9) Завершение

ТРЕХТОЧЕЧНАЯ СХЕМА ПОЛОВИННОГО ДЕЛЕНИЯ

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

Схема алгоритма:

1)

2)

3)

4)

5) Если , то

Если , то

6) Если , то переходим к п. 7, иначе k=k+1 и если , то переходим к п. 3, иначе – к п. 8

7) и к п. 9

8) Превышено и к п. 9

9) Завершение

МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

Метод золотого сечения — метод поиска значений действительнозначной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации. Метод золотого сечения используется для нахождения безусловного минимума унимодальных функций f(x).

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

Точки расположены по симметричной схеме таким образом, чтобы отношение длины исключаемого подинтервала к величине интервала оставалось постоянным. Схема поиска, при которой пробные точки делят интервал в данном отношении называется поиском с помощью метода Золотого Сечения.

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

Схема алгоритма:

1) Задаем a,b, погрешность и количество итераций .

2)

3) Ищем точки и значения функции в этих точках:

4) Если

5) Если

6)M=M+1

7)Если , то к пункту 8 иначе, если то к пункту 9, иначе к пункту 4.

8) , к пункту 10

9)Превышено количество итераций.

10) конец алгоритма.

МЕТОД ФИБОНАЧЧИ

Ещё один метод -- метод Фибоначчи. В методе Фибоначчи должно быть предварительно определено общее число точек, в которых будут производиться вычисления. Это число может быть определено на основании требований точности.

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

Каждое последующее число равно сумме двух предыдущих.

Начальный интервал [a₀, b₀] после нескольких шагов уменьшился до [a_k, b_k]. При этом выбираются две точки x₁^* и x₂^*, определяемые равенствами:

1.

Если f(x₁^k) < f(x₂^k), то следующий интервал неопределённости [a_k+1, b_k+1] = [a_k, x₂^k].

2. Если f(x₁^k) > f(x₂^k), то следующий интервал неопределённости [a_k+1, b_k+1] = [a₁^k, b_k].

Последние точки определяются следующим образом:

где x - произвольное малое положительное число.

При заданном количестве точек, в которых производится оценивание, поиск Фибоначчи является оптимальным в определённом точном математическом смысле (минимаксная стратегия).

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

Схема алгоритма:

1. Задаем a, b, l, где l –желаемая длина конечного интервала. Также задаем - константу различимости на последней итерации.
2. найти количество вычислении, как наименьшее целое число, при котором неравенство выполняется.
3. Вычисляются числа ряда Фибоначчи
4. K =1

1. Если , то

переход к пункту 7.

1. Если

1. Если то к пункту 4.

Если ,то .

1. 

Если , то ,

1. Конец алгоритма.

Пример работы алгоритма, реализованного в MATLAB:

Введите f=1./x+sqrt(x)

Введите а=1

Введите b=2

Введите m0=6

Введите погрешность=0.01

x0 =1.5882

Задание на выполнение лабораторной работы

1. Реализовать в пакете MATLAB алгоритмы поиска экстремума функции одной переменной.

Метод	Варианты	Бригады (2 человека)
Алгоритм Свенна	1-25
Метод поразрядного поиска	1-25
Метод половинного деления		1-6
Трехточечная схема половинного деления		7-12
Метод золотого сечения		1-6
Алгоритм Фибоначчи		7-12

2. Тестирование произвести на нескольких функций .

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

4. Сравнение методов, их достоинства и недостатки проводить при одинаковых значениях исходных данных.

Дата добавления: 2015-08-27