Введение в математическое программирование

Многомерная (многометрическая) оптимизация

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

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

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

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

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj,

j = 1, 2, ..., n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f(x) в базисной точке b1 с целью получения сведений о локальном поведении функции f(x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b1 находится следующим образом:

1.Вычисляется значение функции f(b1) в базисной точке b1.

2.Каждая переменная по очереди изменяется прибавлением длины шага.

Таким образом, мы вычисляем значение функции f(b1 + h1e1), где e1 - единичный вектор в направлении оси х1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1 + h1e1. В противном случае вычисляется значение функции f(b1 – h1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т.е. находится значение функции f(b1 + h2e2) и т.д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

3.Если b2 = b1, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4.Если b2 ≠ b1, то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b2 в направлении b2 - b1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

(1.1)

В общем случае

(1.2)

2.Затем исследование следует продолжать вокруг точки P1 ( Pj ).

3.Если наименьшее значение на шаге В,2 меньше значения в базисной точке b2 (в общем случае bj+1 ), то получают новую базисную точку b3 (bj+2), после чего следует повторить шаг В,1.

10

Введение в математическое программирование

В противном случае не производить поиск по образцу из точки b2 (bj+1) а продолжить исследования в точке b2 (bj+1).

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

Ниже приведена блок-схема данного метода.

2. Метод Нелдера – Мида.

Метод Нелдера — Мида (называется также поиском по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта. Множество (n + 1) -й равноудаленной точки в n -мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве — правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n + 1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился

очень надежный метод прямого поиска, являющийся одним из самых эффективных, если . В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных

операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.

A. Найдем значения функции f1=f(x1),f2=f(x2) ... fn+1=f(хn+1) в вершинах симплекса.

Б. Найдем наибольшее значение функции fh, следующее за наибольшим значением функции fg наименьшее значение функции fl и соответствующие им точки xh, xg, xl.

B. Найдем центр тяжести всех точек, за исключением точки хh. Пусть центром тяжести

будет

11

Введение в математическое программирование

(2.1)

и вычислим f(x0)=f0.

Г. Удобнее всего начать перемещение от точки xh. Отразив точку xh относительно точки х0, получим точку хr и найдем f(xr) = fr. Операция отражения иллюстрируется рис.3. Если а > 0 - коэффициент отражения, то положение точки хr определяется следующим образом:

т.е.

(2.2)

Замечание:

Д. Сравним значения функций fr и fl.

1. Если fr < fl, то мы получили наименьшее значение функции. Направление из точки x0 в точку xr наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку xe и значение функции fe = f(xe). Рисунок 4 иллюстрирует операцию растяжения симплекса.

т.е.

(2.3)

Замечание:

а) Если fe < fl, то заменяем точку xh на точку xe и проверяем (n + 1) -ую точку симплекса на сходимость к минимуму (см. шаг И). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг Б.

б) Если fe > fl, то отбрасываем точку xe. Очевидно, мы переместились слишком далеко от точки x0 к точке xr. Поэтому следует заменить точку xh на точку xr, в которой было получено улучшение (шаг Д, 1), проверить сходимость и, если она не достигнута, вернуться на шаг Б.

2.Если fr > fl, но fr < fg, то xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xh на точку xr и, если сходимость не достигнута, возвращаемся на шаг Б, т.е. выполняем пункт 1,6, описанный выше.

3.Если fr > fl и fr > fg, перейдем на шаг Е.

Е. Сравним значения функций fr и fh.

1. Если fr > fh, то переходим непосредственно к шагу сжатия Е,2.

Если fr < fh, то заменяем точку xh на точку xr и значение функции fh на значение функции fr. Запоминаем значение fr > fg из шага Д,2, приведенного выше. Затем переходим на шаг Е,2.

2. В этом случае fr > fh, поэтому ясно, что мы переместились слишком далеко от точки xh к точке x0. Попытаемся исправить это, найдя точку xc (а затем fc ) с помощью шага сжатия, показанного на рис.5. Если fr > fh, то сразу переходим к шагу сжатия и находим точку xc из

Если fr < fh, то сначала заменим точку xh на точку xr, а затем произведем сжатие. Тогда точку xc найдем из соотношения

т.е.

(2.5)

12

Введение в математическое программирование

закончились неудачей, поэтому мы переходим на шаг 3.

3. На этом шаге мы уменьшаем размерность симплекса делением пополам расстояния от каждой точки симплекса до x1 - точки, определяющей наименьшее значение функции.

Таким образом, точка xj заменяется на точку , т.е. заменяем точку xi

точкой

(2.6)

Затем вычисляем fi для i = 1, 2, ...,(n+1), проверяем сходимость и, если она не достигнута, возвращаемся на шаг В.

И. Проверка сходимости основана на том, чтобы стандартное отклонение (n + 1) -го значения функции было меньше некоторого заданного малого значения е. В этом случае вычисляется

(2.7)

где .

Если , то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума функции xl. Исходя из этого, такой критерий сходимости является разумным, хотя Бокс, Дэвис и Свенн предлагают то, что они считают более "безопасной" проверкой.

Шаги этой процедуры представлены в виде блок-схемы на рис.7.

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

Начальный симплекс выбирается на наше усмотрение. В данном случае точка x1 является начальной точкой, затем формируются точки

(2.8)

где k - произвольная длина шага, a ej - единичный вектор.

13