Сравнительный анализ методов оптимизации (стр. 2 из 6)

Рисунок 1 – Результат выполнения программы (Метод дихотомии).

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

Метод золотого сечения. Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и х2 , обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1–t (рис. 2.7).

Рис. 2.7. Определение пробных точек в методе золотого сечения

Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2¢ = 1–t нового отрезка [0; т]. Чтобы точки х2 = t, и х2¢ = 1–t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство

или

откуда находим положительное значение

…

Таким образом,

х1 = 1–t =

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

;

В таблице 2 приведено решение задания по варианту.

Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х1 и х2 по формулам (2.15). Вычислить f (x1) и f (x2). Положить

Шаг 2. Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) £ f (x2) то положить b=x2 , x2=x1 , f (x2) £ f (x1), x1=b–t(b–a) и вычислить f (x1), иначе – положить a=x1, x1= x2 , f (x1) = f (x2), x2=b+t(b–a) и вычислить f (x2). Положить en = ten и перейти к шагу 2.

Шаг 4. Окончание поиска: положить

Результаты вычислений на остальных итерациях представлены в таблице 2 .

Таблица 2 - Метод золотого сечения

№ шага	a	b	x1	x2	F(x1)	F(x2)
1	2.7	3.9	3.1584	3.4416	-5.7694	1.79829	0.370820393
2	2.7	3.4416	2.98329	3.1583	-3.1542	-5.7698	0.229179607
3	2.9833	3.4416	3.158365	3.26652	-5.76957	-4.22659
4	2.98329	3.266546	3.09148	3.15833	-5.58444	-5.769704
5	3.09148	3.26652	3.15835	3.199661	-5.76962	-5.43999
6	3.09148	3.19966	3.13281	3.15834	-5.8039	-5.76967
7	3.09148	3.15834	3.11702	3.132801	-5.7600	-580399
8	3.11702	3.15834	3.13281	3.14256	-5.8039	-5.80627
9	3.13281	3.15834	3.14256	3.14859	-5.8063	-5.7982
10	3.13281	3.14859	3.1388	3.14856	-5.08076	-5.8063
11	3.13281	3.14256	3.13653	3.13883	-5.8071	-5.8076
12	3.13653	3.142557	3.13883	3.140255	-5.80764	-5.80745
13

|a-b|=7.893370498E-3< ε, x*=(a+b)/2=3.1407091

f(x*)=-5.807126299

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

2 Прямые методы безусловной оптимизации многомерной функции

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

Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. В основном все методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Будем предполагать, что точка минимума существует. Однако в реальных задачах это предположение может не выполняться.

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

F(x1,x2)=a*x*y+(b*y+c*x)/x*y → min

a=5 b=3.5 c=2.5

x1=

x2=

2.1 Метод покоординатного циклического спуска

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

базисная точка переносится в

Циклы повторяются до тех пор, пока в ε окрестности найденной базисной точки будет улучшение функции. Решением поставленной задачи является точка

в ε окрестности которой функция не принимает значение, лучшие, чем в этой точке.

Для решения поставленной задачи выбрано приближение ε=0,01 α=0,15

Таблица 3 - Метод покоординатного циклического спуска

№ шага	x1	x2	Z(x1,x2)	α
0	2.1932884	1.6094917	20.7994602	0.5
1	1.6932884	1.6094917	17.2469375	0,5
2	1.1932884	1.6094917	14.0892956	0,5
3	0.6932884	1.6094917	12.1808992	0,5
4	0.6832884	1.6094917	12.1743085	0.01
5	0.6732884	1.6094917	12.1699126	0.01
6	0.6632884	1.6094917	12.1678107	0.01
7	0.6632884	1.1094917	11.2095884	0.5
8	0.6632884	1.0094917	11.1011539	0.1
9	0.6632884	0.9094917	11.041804	0,1
10	0.6632884	0.8094917	11.0497295	0,1
11	-0,183	0,827	-0,2137796	0,15
13	-0,183	0,677	-0,4082396	0,15
14	-0,183	0,527	-0,4631996	0,15
15	-0,108	0,527	-0,5887121	0,075
16	-0,033	0,527	-0,6860996	0,075
17	0,042	0,527	-0,7553621	0,075
18	0,117	0,527	-0,7964996	0,075
19	0,192	0,527	-0,8095121	0,075
20	0,192	0,452	-0,8409296	0,075
21	0,2295	0,452	-0,842513975	0,0375
22	0,2295	0,4145	-0,8479571	0,0375

α/2< ε, x1=0,2295 x2=0,4145 Z(x1,x2)= -0,8479571

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

Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке 4.

Рисунок 4 – 1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.

При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2 . Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.

Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1,..., dn и направлений поиска по образцу.

Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.

Основной этап.