Методы одномерной оптимизации

Метод сканирования основан на табулировании функции в некотором интервале [a,b] значений функции с шагом h:

h = (b-a)/n (28)

где n – количество интервалов разбиения. Последовательно определяются значений функции f(x) во всех точках разбиения аргумента и запоминается наименьшее значение функции R_м и положение минимума (х_м) (см. рис. 2).

R_м

x_м

а

b

h

Рис. 2. Метод сканирования

Если в качестве шага сканирования выбрать заданную точность определения положения минимума e, как это сделано в программе 12, то с этой точностью и получим искомое решение.

В программе 12 реализован метод сканирования одномерной функции R =f(x). Построением графика функции f(x) решается задача отделения одного экстремума. При желании, сканирование можно повторить с новым диапазоном поиска минимума. Эту же программу можно использовать для нахождения максимумов, если в программе сканирования в операторе while x £ b знак £ заменить на ³. В общем же случае любую программу находящую минимум функции можно превратить в программу поиска максимума, если выражение для функции заключить в скобки и поставить перед ними знак минус.

Программа 12

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

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

(29)

где S – количество вычислений функции, за которое начальная длина L диапазона, в котором находится минимум целевой функции, уменьшается до l.

(30)

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

Метод дихотомии заключается в следующем. Начальный диапазон поиска делится пополам: х = (a + b)/2. Затем определяют с какой стороны от х находится минимум. Сравнивают значения функции R (x+e) и R (x-e), где e – некоторая малая величина, выбираемая в начале программы, которая в конце процедуры окажется погрешностью определения минимума. На рис. 3 минимум оказался слева, далее поиск продолжают в диапазоне новых значений a,b,причем b=x, а величина a остается прежней.

Рис. 3. Метод

дихотомии

Таким образом степень сжатия на каждом шаге оптимизации равна 2, при этом число вычислений функции равно 2, следовательно К =1. То есть эффективность метода дихотомии в 2 раза выше, чем сканирования.

Программа 13

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

Можно показать, что отношение малой части отрезка к целому равно

В методе золотого сечения первоначальный отрезок (a, b) делится на части точками х ₁ и х ₂, причем обе точки делят отрезок в золотом соотношении с разных сторон:

Затем сравнивают значения целевой функции R(X ₁) и R(x ₂). Если R(X ₁) > R(x ₂), то минимум функции, очевидно, находится в интервале (X ₁, b). Если наоборот, R(X ₂) > R(x ₁), то минимум надо искать в диапазоне (a, X ₂), как это показано на рисунке. На втором шаге новый диапазон поиска также делится в золотом соотношении с двух сторон. И здесь оказывается, что вычислять значение функции R(x ₂) на втором шаге не надо – оно уже было вычислено как R(X ₁) на первом шаге. Можно показать, что Z(1-Z)(b-a)=(1-Z-Z)(b-a), если
Z – “золотое отношение”.

Степень сжатия интервала поиска в этом методе составляет

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

Программа 14

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

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

Программа 15

Из листинга программ 12–15 видно, что в пределах заданной точности все методы дают одинаковые результаты.

Контрольные вопросы к главе 4

1. Дайте определение понятию «оптимизация».

2. Как математически формулируется задача оптимизации?

3. Приведите примеры задач оптимизации.

4. Что называют целевой функцией? Приведите примеры.

5. Назовите параметры какой-либо задачи оптимизации в области химии.

6. Как называют оптимизацию с одним параметром?

7. Назовите математические трудности решения задач оптимизации.

8. Чем отличаются условные задачи оптимизации от безусловных?

9. Что обозначает термин «линейное программирование»?

10. Сформулируйте задачу одномерной оптимизации.

11. Чем отличается поиск минимума от поиска максимума?

12. Поясните алгоритм метода сканирования.

13. Какими действиями можно программу поиска минимума одномерной функции методом сканирования превратить в программу поиска максимума той же функции?

14. Как рассчитать коэффициент эффективности алгоритма оптимизации?

15. Поясните алгоритм метода дихотомии.

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

17. Каков алгоритм метода поиска минимума одномерной функции методом золотого сечения?

18. Объясните, почему метод золотого сечения более эффективен, чем метод дихотомии?

19. Какие встроенные функции используются в MathCad для решения задач одномерной и многомерной оптимизации?

20. Как можно задать точность вычисления экстремумов в MathCad?

Расчетная многовариантная задача № 4

Найдите 2-3 экстремума функции f(x) с точностью, указанной в таблице методом сканирования, дихотомии, золотого сечения и с помощью встроенных функций MathCad.

Таблица 5

№ вар.	Функция f(x)	Точность корня
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001
		0.001
		0.0001
		0.00001
		0.000001

Форма записи отчета в лабораторном журнале:

Дата: ___. Занятие № __. Тема: «Оптимизация». Вариант ___.
Получены 3 экстремума с точностью 0.0001:

Граница экстремум [a,b] Положение экстремума

[-1, 0] х_min= - 0.23456

[0, 1.5] х_max = 1.23457

[1.5, 3] х_min = 1.98371

Варианты творческих заданий

1. Проведите аппроксимацию табличных данных Y= f (X) полиномом, причем выбор оптимальной степени полинома проведите одним из методов, описанных в этой главе.

2. Проведите аппроксимацию табличных данных Y= f (X) нелинейной функцией, минимизируя сумму квадратов отклонений (нелинейный МНК) одним из методов, описанных в этой главе. Функцию и табличные данные можно взять у преподавателя.

Дата добавления: 2015-07-19