Лекция 2
Методы многомерной безусловной оптимизации. Прямые методы

Пусть дана функция , где и задана начальная точка . Требуется найти min с точностью εf по функции, εi по переменным. На k-м шаге определяем вектор в направлении которого функция уменьшается. В этом направлении делаем шаг величиной λk и получаем новую точку , в которой . Поиск прекращаем как только или , .

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

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

Алгоритм Гаусса

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

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

В результате получаем новую точку . Далее из точки ищем минимум функции, изменяя вторую координату и считая фиксированными все остальные координаты. В результате получаем значение

и новую точку .

Продолжая процесс, после n шагов получаем точку , начиная с которой процесс возобновляется.

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

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

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

Алгоритм Хука и Дживса

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

Задается начальная точка поиска и начальное приращение (шаг) , после чего начинается исследующий поиск.

Исследующий поиск:

Делаем пробный шаг по переменной x1, т.е. определяем точку и вычисляем значение функции для точки .

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

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

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

Поиск по образцу:

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

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

Из точки начинаем новый исследующий поиск и т.д.

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

Алгоритм Розенброка

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

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

, ,

….

, .

Следующая итерация начнется с точки . Если не изменить систему направлений, то будем иметь алгоритм Гаусса. Поэтому после завершения k-го этапа вычисляем новые направления поиска. Ортогональные направления поиска поворачиваются так, чтобы они оказались вытянутыми вдоль "оврага" ("хребта") и, таким образом, исключается взаимодействие переменных (xi xj). Направления поиска вытягиваются вдоль главных осей квадратичной аппроксимации целевой функции. Рассмотрим некоторую k-ю итерацию алгоритма Розенброка. В результате минимизации по каждому из ортогональных направлений на данной итерации мы имеем систему параметров , с помощью которых определим систему векторов , вычисляемых по формулам следующего вида:

;

;

… ;

.

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

;

;

;

;

; l = 2, ..., n

Для работы алгоритма необходимо, чтобы ни один из векторов системы не стал нулевым вектором. Для этого в алгоритме следует располагать параметры в порядке убывания по абсолютному значению, т.е. . Тогда если любые m из обращаются в нуль, то отыскиваются новые направления по процедуре Грама-Шмидта только для тех (n - m) направлений, для которых , оставшиеся же m направлений остаются неизменными: , i = (n - m + 1), ..., n. Так как первые (n - m) векторов взаимно ортогональны, , i = (n - m + 1), ..., n, первые (n - m) векторов не будут иметь составляющих в направлениях , i = (n - m + 1), ..., n. А поскольку эти последние направления взаимно ортогональны, то из этого следует, что все направления являются взаимно ортогональными.

Палмером было показано, что и пропорциональны (при условии, что , величина сокращается, и, таким образом, остается определенным, если даже . Имея это в виду Палмер предложил для вычисления следующие соотношения:

, i = 1, ..., n,

, i = 2, ..., n,

.

Критерии останова алгоритма могут быть стандартными (т.е. описанными в предыдущих алгоритмах прямых методов).

Симплексный метод Нелдера-Мида или поиск по деформируемому многограннику

В процессе поиска осуществляется работа с регулярными симплексами. Регулярные многогранники в пространстве En называются симплексами. Для n=2 регулярный симплекс представляет собой равносторонний треугольник; при n=3 - тетраэдр и т.д.

Координаты вершин регулярного симплекса в n-мерном пространстве могут быть определены следующей матрицей D, в которой столбцы представляют собой вершины симплекса, пронумерованные от 1 до (n + 1), а строки – координаты вершин, i = 1, ..., n. Матрица имеет размерность :

,

где: ; ; t – расстояние между вершинами.

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

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

В симплексном алгоритме Нелдера и Мида минимизация функций n переменных осуществляется с использованием деформируемого многогранника.

Будем рассматривать k-ю итерацию алгоритма. Путь , i = 1, ..., (n + 1), является i-й вершиной в En на k-м этапе поиска, k = 0, 1, 2, ... , и пусть значения целевой функции в вершине . Отметим вершины с минимальным и максимальным значениями. И обозначим их следующим образом:

и .

Многогранник в En состоит из n + 1 вершин . Обозначим через - центр тяжести вершин без точки с максимальным значением функции. Координаты этого центра вычисляются по формуле:

, j = 1, ..., n

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

  1. Отражение. Это проектирование точки через центр тяжести в соответствии со следующим соотношением:

    ,

    где α > 0 - коэффициент отражения.

    Вычисляем значение функции в найденной точке . Если значение функции в данной точке , то переходим к четвертому пункту алгоритма – операции редукции.

    Если , то выполняем операцию растяжения.

  2. Растяжение. Эта операция заключается в следующем. Если (меньше минимального значения на k-м этапе), то вектор растягивается в соответствии с соотношением

    ,

    где γ > 0 - коэффициент растяжения.

    В противном случае, если , то выполняется операция сжатия.

    Если , то заменяется на и процедура продолжается с операции отражения при k = k + 1. В противном случае заменяется на и переходим к операции отражения.

  3. Сжатие. Если для , то вектор сжимается в соответствии с формулой

    ,

    где 0 < β < 1 - коэффициент сжатия. После этого, точка заменяется на , и переходим к операции отражения с k = k + 1. Заново ищется .

  4. Редукция. Если , то все векторы , где i = 1, ..., (n + 1) уменьшаются в два раза с отсчетом от точки по формуле

    , i = 1, ..., (n + 1)
    и переходим к операции отражения (на начало алгоритма с k = k + 1).

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

    .

Выбор коэффициентов α, β, γ обычно осуществляется эмпирически. После того как многогранник подходящим образом промасштабирован, его размеры должны поддерживаться неизменными пока изменения в топологии задачи не потребуют многогранника другой формы. Чаще всего выбирают α = 1, 0.4 ≤ β ≤ 0.6, 2 ≤ γ ≤ 3.