Многомерная безградиентная оптимизация

Многомерная оптимизация. Концепция методов.

Математическая постановка задачи имеет следующий вид:

Задачу условной оптимизации сформулируем в традиционном виде:

Найти минимум целевой функции

(1)

по поисковым переменным при наличии различных ограничений:

на поисковые переменные

, (2)

l=1,L; L-число поисковых переменных;.

на поисковые переменные в виде функциональных неравенств , (3)

j=1,J; J - число функциональных неравенств;

на поисковые переменные в виде функциональных равенств , (4)

i=1,I. I - число функциональных равенств.

В данном разделе рассматриваются численные методы опти­мизации, у которых величина и направление шага к оптимуму формируются однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Все алгоритмы имеют итерационный характер и для переменной i на j +1 итерации вы­ражаются формулой:

. (5)

Для рассматриваемой группы методов . Среди этих методов выделим: метод Гаусса - Зайделя, метод Хука-Дживса, методы деформируемого многогранника ( симплексный метод). Основная особенность рассматриваемой группы методов — отсутствие вычисления градиента критерия оптимальности. Ряд методов прямого поиска ба­зируется на последователь­ном применении одномер­ного поиска по переменным или по другим задаваемым направлениям, что облегча­ет их алгоритмизацию и применение.

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

Одними из методов нахождения минимума функции n-переменных являются методы прямого поиска. Методы прямого поиска являются методами, в которых используются только значения функции. Суть метода состоит в поочередной одномерной оптимизации целевой функции с помощью методов одномерной оптимизации, например, с помощью метода золотого сечения поочередно по каждой переменной Х1,…,Хn.

Рис.1. - Метод прямого поиска

Рассмотрим функцию двух переменных. Ее линии уровня представлены на рис.1, а минимум лежит в точке (x₁^*,x₂^*). Простейшим методом поиска является метод покоординатного спуска. Из точки А произведем поиск минимума вдоль направления оси х₁ и, таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси х₁. Затем, производя поиск из точки В в направлении оси х₂, получаем точку С, производя поиск параллельно оси х₂, получаем точку D, и т.д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идею можно применить для функции n переменных. Теоретически данный метод эффективен в случае единственного минимума функции. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.

3.6. Симплексный метод оптимизации.

Симплексом называется правильный многогранник, имею­щий п+1 вершину, где п—число факторов, влияющих на про­цесс. Так, например, если факторов два, то симплексом явля­ется правильный треугольник.

Рис.2. Оптимизация по симплексному методу

Сущность симплексного метода оптимизации иллюстрирует рис. 2. Начальная серия опытов соответствует вершинам исход­ного симплекса (точки 1, 2 и 3). Условия этих первых опытов берутся из области значений факторов, соответствующих наи­более благоприятным из известных режимов оптимизируемого процесса. Сравнивая между собой результаты опытов в точках 1, 2 и 3, находят среди них самый «плохой», с точки зрения выбран­ного критерия оптимальности. Пусть, например, самым «не­удачным» оказался опыт в точке 1. Этот опыт исключают из рассмотрения, а вместо него в состав симплекса вводят опыт в точке 4, которая симметрична точке 1 относительно проти­воположной стороны треугольника, соединяющей точки 2 и 3. Далее сравнивают между собой результаты опытов в вер­шинах нового симплекса, отбрасывают самый «неудачный» из них и переносят соответствующую вершину симплекса в точ­ку 5. Затем рассмотренная процедура повторяется в течение всего процесса оптимизации. Если экстремум критерия оптимальности достигнут, то дальнейшее движение симплекса прекращается. Это значит, что новый шаг возвращает исследователя в предыдущую точ­ку факторного пространства. Следует иметь в виду, что симплексный

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

3.7.ПОИСК ПО ДЕФОРМИРУЕМОМУ МНОГОГРАННИКУ

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

симплексного метода (не путать с симплексным методом в линейном программировании). Он более простой, однако находит широкое применение в решении задач планирования экстремальных экспериментов.

Рис. 3. Иллюстрация идеи симплексного метода

Симплексами называют регулярные многогранники. Например, для случая двух переменных это будет равносторонний треугольник, для трех переменных - тетраэдр и т. д. Точки испытаний (рис. 3) совпадают с вершинами симплекса (точки 1, 2,3). Из вершины, в которой целевая функция максимальна (точка 1), проводится проектирующая прямая через цент тяжести симплекса. Затем строится новый симплекс, называемый отраженным, из точек 2, 3 и новой точки 4, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести. Такая процедура, в которой каждый раз вычеркивается вершина с максимально целевой функцией, повторяется. Треугольник (в случае двух переменных) как бы переворачивается через сторону с наименьшим значениями целевой функции. Существуют правила постепенного уменьшения размера симплекса и предотвращения циклического движения в окрестности минимума. Использование именно регулярных многогранников обусловливает ряд недостатков метода: неэффективный поиск в искривленных оврагах, замедление поиска в некоторых ситуациях. В метод деформируемого многогранника симплекс может изменять свою форму, поэтому лучше приспособиться к особенностям многомерно поверхности. Обозначим координаты вершин многогранника на с-м шаг через

Х_i,k i = 1, . . ., п + 1; k = 0, 1, ... Выделим вершины, в которых целевая функция максимальная и минимальная, и обозначим их соответственно через Хплохое (Xмакс)и Xхорошее(X min). (для упрощения формул индекс шага к в дальнейшем будем опускать) Через X центр обозначим центр тяжести всех вершин, исключая Хплохое:

X_n+2,j=

Работа метода состоит из сле­дующих операций: отражения, растяжения, сжатия и редукции (рис. 4).

Рис. 4. Операции метода деформируе­мого многогранника

Рис. 5. Траектория метода деформиру­емого многогранника.