Читайте также:
|
|
ПРЯМЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ
Рассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х) ® min, xÎ E n, которые опираются только на вычисление значений функции f (х), т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишь иметь возможность вычислять или измерять значения f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.
Остановимся сначала на вычислительных процедурах вида (3.25), в которых выбор нового приближения к точке минимума определяется сравнением значений функции в нескольких точках пространства E n.
МИНИМИЗАЦИЯ ПО ПРАВИЛЬНОМУ СИМПЛЕКСУ
Определение 3.7. Правильным симплексом в пространстве E n называется множество из п + 1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.
В пространстве E 2 правильным симплексом является совокупность вершин равностороннего треугольника, в E 3 – правильного тетраэдра.
Если х0 – одна из вершин правильного симплекса в E n то координаты остальных п вершин х1,..,х n можно найти, например, по формулам:
(3.37)
где d 1 , d 2 , a– длина ребра. Вершину х0 симплекса, построенного по формулам (3.37), будем называть бaзовой.
В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой–либо вершины, например, х k симметрично относительно центра тяжести х c остальных вершин симплекса. Новая и старая вершины и х k связаны соотношением: , где x c . В результате получается новый правильный симплекс с тем же ребром и вершинами = 2x c – х k, х i, i = 0,.., n, i¹ k. Таким образом, происходит перемещение симплекса в пространстве Е n. На рис. 3.3 представлена иллюстрация этого свойства симплекса в пространстве Е 2.
Поиск точки минимума функции f (x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f (х) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для той вершины, в которой f (х) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.
Шаг 0. Выбрать параметр точности e, базовую точку х0, ребро a и построить начальный симплекс по формулам (3.37). Вычислить f (х0).
Шаг 1. Вычислить значения f (х) в вершинах симплекса х1,.., x n.
Шаг 2. Упорядочить вершины симплекса х0,.., х n так, что бы f (х0) £ …£ £ f (х1) £ f (х n –1) £ f (х n).
Шаг 3. Проверить условие
(3.38)
Если оно выполнено, то вычисления прекратить, полагая х*» х0, f *» f (x0).
В противном случае перейти к шагу 4.
Шаг 4. Найти и выполнить отражение вершины х n:
= 2x c – х n. Если f () <f ( x n), то положить х n = и перейти к шагу 2. Иначе – перейти к шагу 5.
Шаг 5. Найти и выполнить отражение вершины х n– 1: = 2x c – х n– 1. Если f () < f (х n– 1), то положить х n– 1 = и перейти к шагу 2. Иначе – перейти к шагу 6.
Шаг 6. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершиной х0. Остальные п вершин симплекса найти по формуле х i = (х i + х0)/2, i= 1, .., п. Перейти к шагу 1.
Геометрическая иллюстрация работы алгоритма в пространстве показана на рис. 3.4, где точки х 0, х 1, х 2 – вершины начального симплекса, а пунктиром указаны процедуры отражения.
Замечания:
1. Следует иметь в виду, что если функция f (х) многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума f (х).
2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.
Дата добавления: 2015-05-05; просмотров: 18 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
Выбор экспертов | | | ПОИСК ТОЧКИ МИНИМУМА ПО ДЕФОРМИРУЕМОМУ СИМПЛЕКСУ |