Поиск по правильному симплексу

Поиск минимума целевой функции/(Х) по данному методу основан на выборе в качестве пробных точек вершин правильно­го симплекса. Напомним, что правильным симплексом в Е" назы­вается множество из и+1 равноудаленных друг от друга точек -вершин симплекса. Так, в Е² правильным симплексом является равносторонний треугольник, в Е^ъ - тетраэдр.

Из аналитической геометрии известно, что если Х°~ одна из вершин правильного симплекса в Е", то координаты остальных вершин X¹,..., ^находятся по формулам

(2.4)

где d, = -

I + n-\); d₂ = — =(yJn + \ -l); t - длина ребра.

По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины симметрично относитель­но центра тяжести А" остальных вершин симплекса. Новая и ста­рая вершины X и Л"* связаны соотношением:

^л [

В результате получается новый правильный симплекс с тем же ребром и вершинами:

х" =2X^c-X^k,X^J, j = O,...,n,j*k.

Описанная операция отражения в пространстве Е^г представ­лена на рис. 2.1.

V⁰

„о Л

Рис. 2.1. Построение нового симплекса в Е² отражением точки X¹:

а - начальный симплекс Х°, Х\ А"²; б- новый симплекс Х°, X¹. Х'*\

центр отражения - точка X '= (Х° + Х')/2

На каждой итерации поиска сравниваются значения функ­ции f{x) в вершинах симплекса и выполняется описанная про­цедура отражения для той вершины, в которой/(л) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Иначе выполняют еще одну попытку отражения для вершины со следующим по величине значением/(а). Если и она не приводит к уменьшению функции, то сокращают длину ребра и строят но­вый симплекс с этим ребром. При этом в качестве базовой выби­рают ту вершину Х° старого симплекса, в которой функция при­нимает наименьшее значение. Поиск точки минимума X закан­чивают, когда либо ребро симплекса, либо разность между зна­чениями функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.

г

Шаг-0, Задать параметр точности е, выбрать базовую точку Х° и длину ребра t, построить по формуле (2.4) начальный симп­лекс и вычислить f(X)■

Шаг1. Вычислить значения функции/(А) в вершинах симп­лекса X',..., X".

Шаг 2. Упорядочить вершины симплекса X,..., Л"¹ так,

чтобы f(X°)<...<f{X").

ШагЗ. Проверить условие достижения точности

Если оно выполняется, то перейти к шагу 7, иначе - к шагу 4.

Шаг 4. Найти по формуле (2.4) центр тяжести Х^

вершин Х\Х\..., А""'и выполнить отражение вершины X":

X" =2Х^С -X". Если ffx"'^<f(X"-^l),TO положить X"'¹ = А'""' и перейти к шагу 2, иначе - к шагу 5.

Шаг 5. Найти центр тяжести X^е вершин Х°, X¹,..., X" ', X" и выполнить отражение вершины Х"~': X"' = 2Х^е -X"'. Если

/|А"¹~')</(А"'~^|),то положить X"'¹ = X" "' и перейти к шагу 2, иначе - к шагу 6.

Шаг 6. Построить новый правильный симплекс с вдвое мень­шим ребром, считая базовой вершину А'⁰, а остальные п вершин на­ходя по формуле X' = [X^J + X^й У2, j -1,..., п, и перейти к шагу 1.

Шаг_7. Завершить вычисления, положив Х'-Х°,/' =/(А"¹).

■/ 2.1.2. Поиск но деформируемому многограннику

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

Рассмотрим метод поиска, в котором симплекс может изме­нять свою форму и уже не остается симплексом. Более подходя­щим для него оказалось название «деформируемый многогранник».

В методе деформируемого многогранника, как и в предыду­щем методе, функция п независимых переменных минимизирует­ся с использованием п+ 1 вершин многогранника. Вершина, в ко­торой значение функции/^ максимально, проектируется через центр тяжести оставшихся вершин. Улучшенные значения функ-цииДА) находятся последовательной заменой точки с максималь­ным значением/(,¥) на более «хорошие» точки, пока не будет най­ден минимум/УО-

Итак, пустьX¹, Х^г,...,Х"*^х -вершины многогранника на не­котором этапе поиска. Определим точки X^hwX^L, в которых фун­кция имеет соответственно наибольшее и наименьшее значения:

Центр тяжести всех вершин, исключая X^h, определим по формуле

X^^-Wx'-X" \. (2.6)

Процедура отыскания вершины, в которой/(Л0 имеет луч­шее значение, состоит из четырех операций.

1. Отражение - проектирование точки X^h через центр тяже­
сти Х"^+г в соответствии с соотношением

X^nri=X^nt2+a(X~²-X^h), (2.7)

где а > 0 - коэффициент отражения: А'"'² - центр тяжести, вычис­ляемый по формуле (2.6).

2. Растяжение. Если /(*"*')</(*'), то вектор Х^-Х"*¹
растягивается в соответствии с соотношением

X"**=X-*²+y{X"*ⁱ-X'*²), (²-⁸>

где у > 1 - коэффициент растяжения. Если j(X"**)<J[X)• ^т0 вершина ^заменяется на.Г⁴ и начинается новый этап поиска

снова с операции отражения. В противном случаев* заменяется на X"" и также осуществляется переход к операции отражения нового этапа.

3. Сжатие. Если f{x"*³) >f(x^j)yj * h, то вектор X^й - X"*¹ сжимается в соответствии с формулой

X = Х +р(А -X), (2.9)

где (Зе(0;1)-коэффициент сжатия. Вершина X^h заменяется HaX"⁺ⁱ

и выполняется вновь операция отражения на новом этапе поиска.

4. Редукция. Если f(X"^1l)>f(x"), _{то все} векторы;Г -*-'■

уменьшаются, например, в 2 раза с отсчетом от X^L в соответствии

с формулой

. (2.10)

для продолже-Критерий окончания поиска может быть выбран

в виде ус-

где е > 0 - достаточно малое число.

Геометрическая иллюстрация описанных процедур для про­странства Е¹ приведена на рис. 2.2 и 2.3.

IK

Так как величина аб(0;1], то выбор точек Х"*^ъ и А'"⁺³ соот­ветствует отражению; ре(0;1), поэтому выбор точки A""^+s соот­ветствует сжатию, а у >1 и выбор точки Х"*^л приводит к растяже­нию симплекса.

,-:Y A -

{\0 и значение функции в ней:/(^⁶) = 8.

Так как /(А'⁶) < f(x^L), заменяем вершину X^й на А""⁴, пола­гая X² = X ⁶ и тем самым завершая первую итерацию поиска.

На рис. 2.4 приведена геометрическая интерпретация поис­ка по деформируемому многограннику на пяти начальных эта­пах минимизации функции: /(Х) = 4х² +х\ -40х, -12х₂ +136.

Рис

Очевидно линиями уровня функции являются эллипсы. На _тс 2 4 и обряжены линии уровня, соответствующие значениям Е™ 2 5 10 20 и 30. Пунктиром выделены многогранники с в ршинами^" U- номер вершины деформируемого многогран­ника на /-м этапе поиска). Сплошными линиями показана траек­тория поиска, соединяющая вершины многогранника, соответ­ствующие наименьшим значениям/С*) в каждом из них.

Убедитесь в соответствии графической иллюстрации опи­санному с помощью формул (2.7) - (2.10) алгоритму.

Порядок выполнения лабораторной работы

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

2. Выполнить алгоритмическую реализацию описанного ме­
тода деформируемого многоугольника.

3. Дать геометрическую иллюстрацию указанной препода­
вателем задачи и выполнить вручную две итерации по состав­
ленному алгоритму.

4. Провести с использованием компьютерного комплекса
расчеты полученной задачи при различных значениях парамет­
ров алгоритма.

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

6. Сформулировать вывод о влиянии параметров алгорит­
ма на эффективность поиска решения задачи. Содержание рабо­
ты отразить в отчете.

Задания для лабораторной работы

1. Минимизировать функцию f(x) = 2xf + r₂ -*,*,, исполь­
зуя в качестве начального многогранник с вершинами X '=(2- 2)^т
л =(3;2,5)', А"=(2;3)^т '

2. Минимизировать функцию f(x) = 5х? + 5х^г₂ + 8*, х₂ ис-

3. Минимизировать функцию/(X) = 4.x,² + х\ -40х, - 12л, +136,
используя в качестве начального многогранник с вершинами
A"=(8;9)^T,A-²=(10; 11)^Т,ЛГ³=(8; 11)^т.

4. Минимизировать функцию f[X) = 2х] + 2х\ - 2х,х, - 14х, -
- \2х_г + 29, используя в качестве начального многогранник с вер­
шинами Х^х= (6;3)^Г,Х²=(9; 3)\Х'= (7;4)^т.

5. Минимизировать функцию f(X) = x* +4xl -Wjc, -48.x, +169
используя в качестве начального многогранник с вершинами
X^х = (7; 3)^т, Х¹= (9; 1)^т, Xⁱ= (9; 3)^т.

6. Минимизировать функцию/(А^г) = х,² +9x1 -4.x, -18х₂ +13,
используя в качестве начального многогранник с вершинами
X^х = (4; Ъ)\Х^г= (6; 3)^т,^ = (6;4)^т.

7. Минимизировать функцию/(-Y) = 9x_l² +х\ -36х, -2х₂ +37,
используя в качестве начального многогранник с вершинами
Х' = (5; 3)^т,*²=(7; 5)^т,^ = (5;5)^т.

8. Минимизировать функцию f (X) =\00(х₂-х_[¹)²+ (1-х,)²,
используя в качестве начального многогранник с вершинами
А" = (-1; \)⁷,Х²=(-0,5; 1)^т,Х³=(-1; 2)^т.

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

Рассмотрим прямые методы решения задачи безусловной минимизации (2.1), использующие вместо итерационных проце­дур вида (2.3) простейшие вычислительные алгоритмы, основан­ные на рекуррентной формуле

X^k*^l=X^k+a_kS\ (2.12)

где S^k - направление поиска точки л^[ из точки Х^к, а положи­тельное число <х_к - величина шага в этом направлении.

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

Поиск по сайту: