birmaga.ru
добавить свой файл

1 2 3
47. МЕТОДЫ ОДНОМЕРНОГО ПОИСКА. ПРЯМЫЕ МЕТОДЫ ПОИСКА. СИМПЛЕКСНЫЙ МЕТОД. НЕЛЬДЕРА И МИДА.


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

Методы сужения интервала неопределенности:
Пусть требуется найти минимум функции f(x) на некотором интервале [a, b]. Задача приближенного отыскания минимума в методах сужения интервала неопределенности состоит в том, чтобы найти множество абсцисс x1,x2,...,xk, в которых вычисляется функция, такое, что минимальное значение * лежит при некотором i в интервале xi-1 ≤ x≤ x. Такой интервал называется интервалом неопределенности D. Очевидно, что сначала интервал неопределенности совпадает с отрезком [a, b].

Одномерные: Метод золотого сечения, Дихотомия, Метод парабол, Метод Фибоначчи

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

Прямые методы: Метод Гаусса, Метод Нелдера-Мида, Метод Хука-Дживса, Метод конфигураций, Метод Розенброка.

Симплекс-метод

Рассмотрим следующую задачу локальной безусловной оптимизации: найти минимум критерия оптимальности http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=1/?k=10(http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=2/?k=10), определенного в http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=3/?k=10-мерном евклидовом пространстве http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=4/?k=10,



http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=5/?k=10

 (1)


Регулярный симплекс и некоторые операции над ним.

Регулярным симплексом в пространстве http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=4/?k=10 называется правильный многогранник, образованный http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=6/?k=10-ой равноотстоящими друг от друга вершинами. Для случая http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=7/?k=10 – это равносторонний треугольник, для случая http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=8/?k=10 – тетраэдр.

Если в пространстве http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=4/?k=10 необходимо построить регулярный симплекс, одна из вершин которого находится в точке http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=9/?k=10, то координаты вершин такого симплекса удобно задавать с помощью http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=10/?k=10 матрицы

http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=11/?k=10


 (2)


Здесь http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=12/?k=10-й столбец представляет собой координаты http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=12/?k=10-й вершины симплекса, http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=13/?k=10;


http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=14/?k=10

 (3)


http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=15/?k=10-длина ребра симплекса.

Например, регулярный симплекс в двумерном пространстве http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=16/?k=10 с одной из вершин в начале координат (когда http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=17/?k=10 определяется http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=18/?k=10 матрицей

http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=19/?k=10


и имеет вид, представленный на рис. 1.


http://bigor.bmstu.ru/?img/?doc=mo/ch0605.mod/?n=2http://bigor.bmstu.ru/?img/?doc=mo/ch0605.mod/?n=1


Рис. 1.  Регулярный симплекс в пространстве R2 с одной из вершин в начале координат.

В алгоритме симплекс-метода используется следующее важное свойство регулярного симплекса: если одну из вершин регулярного симплекса перенести на надлежащее расстояние вдоль прямой, соединяющей данную вершину и центр тяжести оставшихся вершин, то вновь получится регулярный симплекс (см. рис. 2).

Будем называть эту процедуру отражением вершины симплекса относительно центра тяжести остальных вершин.

Рис. 2.  Отражение вершины X 1 регулярного симплекса в пространстве R2 относительно центра тяжести Xc остальных вершин.

Пусть http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=20/?k=10 - векторы координат вершин регулярного симплекса. Тогда при выполнении операции отражения http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=21/?k=10-й вершины симплекса имеет место следующая связь координат этой вершины и новой вершины:

http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=22/?k=10


 (4)


Здесь


http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=23/?k=10

 (5)


вектор координат центра тяжести остальных вершин симплекса (за исключением отраженной вершины http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=21/?k=10)

Таким образом, после отражения http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=21/?k=10-й вершины симплекса с координатами вершин http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=20/?k=10, получаем новый симплекс с координатами вершин


http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=24/?k=10

 (6)


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

http://bigor.bmstu.ru/?img/?doc=mo/ch0605.mod/?n=3

Рис. 3.  Редукция вершин регулярного симплекса в пространстве R2 к вершине X1.


Пусть http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=20/?k=10 - векторы координат вершин регулярного симплекса. Тогда при выполнении операции редукции вершин этого симплекса к вершинеhttp://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=25/?k=10 новые координаты остальных вершин симплекса определяются по формуле

http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=26/?k=10=http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=27/?k=10+http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=28/?k=10(http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=29/?k=10-http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=30/?k=10), http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=31/?k=10[1,http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=3/?k=10+1], http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=32/?k=10,

где http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=33/?k=10 - коэффициент редукции. Рекомендуется использовать http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=34/?k=10.


Таким образом, после редукции вершин симплекса http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=20/?k=10 к вершине http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=25/?k=10 получаем новый симплекс с координатами вершин


http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=35/?k=10

 (7)


Схема простейшего варианта симплекс-метода.

Суть симплекс-метода раскрывает его простейший вариант.


  1. Задаем начальную точку http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=36/?k=10, длину ребра симплекса http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=37/?k=10 и полагаем http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=38/?k=10=0.

  2. По формулам (2), (3) находим координаты http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=39/?k=10 всех вершин симплекса.

  3. Вычисляем значения http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=40/?k=10 минимизируемой функции во всех вершинах симплекса.
  4. Находим максимальное из значений функции http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=41/?k=10 в вершинах симплекса http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=42/?k=10

    http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=43/?k=10


  5. По формулам (5), (6) отражаем вершину http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=44/?k=10 относительно центра тяжести остальных вершин симплекса – получаем новый симплекс с координатами вершин http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=45/?k=10.

  6. Вычисляем значениеhttp://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=46/?k=10 минимизируемой функции в новой вершине симплекса.
  7. Если условие окончания итераций (см. ниже) выполнено, то в качестве приближенного значения точки минимума функции http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=47/?k=10(http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=48/?k=10) принимаем ту вершину симплекса http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=49/?k=10, в которой http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=47/?k=10(http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=48/?k=10) имеет минимальное значение, и заканчиваем вычисления. Иначе полагаем http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=38/?k=10=http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=38/?k=10+1 и переходим к п. 4http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=50/?k=10


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


http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=51/?k=10

 (8)


где http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=52/?k=10 - требуемая точность решения по http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=53/?k=10http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=54/?k=10 - номер произвольной вершины симплекса. Отметим, что выражение в левой части неравенства (8) есть максимальная разность значений функции http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=1/?k=10(http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=2/?k=10) в двух вершинах симплекса http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=55/?k=10.

Простейший вариант симплекс-метода иллюстрирует рис. 4, на котором показаны линии уровня функции Химмельблау (http://bigor.bmstu.ru/?frm/?doc=mo/ch0605.mod/?n=3/?k=10=2).


http://bigor.bmstu.ru/?img/?doc=mo/ch0605.mod/?n=4


следующая страница >>