VIII. Методы многомерной оптимизации

1. Основные определения. Задачей многомерной оптимизации является минимизация функции U=f(x₁,x₂,...,x_m) от m переменных (параметров) x₁,x₂,...,x_m. Если нет ограничений на параметры x₁,...,x_m, то говорят о глобальной безусловной минимизации, если есть ограничения на параметры x₁,...,x_m, то говорят об условной минимизации.

Для сокращенного обозначения функции многих переменных удобно использовать векторное обозначение , при этом подразумевается, что каждой величине сопоставлен свой единственный набор значений величин x₁,...,x_m. В соответствии с этим величину можно рассматривать как точку (элемент) m-мерного линейного пространства независимых переменных x₁,...,x_m. Если в этом пространстве ввести единичные векторы , поставленные в соответствие переменным x₁,...,x_m, то величину можно рассматривать как вектор: , а операции сложения и вычитания производить по правилу векторов.

а) поверхность уровня. Множество точек , для которых называется поверхностью уровня, для двух переменных это множество называется линей уровня

б) градиент. Вектор называется градиентом функции и обозначается:

(8.1)

Вектор указывает направление наискорейшего возрастания функции, а вектор называется антиградиентом и указывает направление наискорейшего убывания функции. Градиент всегда перпендикулярен поверхности (линии) уровня.

2. Необходимое и достаточное условия минимума функции многих переменных:

а) необходимое условие. Необходимым условием минимума функции многих переменных является условие равенства нулю ее градиента:

(8.2)

или

б) достаточное условие. Достаточным условием является условие положительной определенности матриц Гессе:

(8.3)

Для положительной определенности матрица Гесса необходимо, чтобы ее собственные числа l₁,...,l_m были положительны. Собственные числа l₁,...,l_m являются корнями характеристического уравнения:

(8.4)

где det -определитель квадратной матрицы ранга m, Е - единичная матрица.

Матрица C=G-lE называется характеристической матрицей для матрицы G.

3. Основные методы безусловной многомерной минимизации:

а) покоординатный спуск. В методе покоординатного спуска

выбирается начальная точка x₀ с координатами

. Фиксируются все координаты кроме первой, и решается одномерная задача минимизации относительно переменной x₁(Рис.5). Затем фиксируются все координаты кроме второй, и опять решается задача одномерной минимизации относительно переменной x₂ и т.д., т.е. поочередно производится спускание по всем координатам x_i, до тех пор, пока не выполнятся все условия:

, (8.5)

Если линия уровня имеет изломы, что соответствует “оврагам” на поверхности , то данный метод становится непригодным;

б) простой градиентный метод. В методе простого градиентного спуска выбирается начальная точка и начальное значение шага h. В точке вычисляется градиент и делается шаг в направлении антиградиента (Рис.6):

. (8.6)

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

Недостатком метода является необходимость на каждом шаге вычислять значение градиента, что требует достаточно много времени;

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

, (8.7)

где a выступает в качестве параметра.

В результате находится значение , соответствующее минимальному значению функции на выбранной прямой (Рис.7). Затем вычислительный процесс повторяется для точки и т.д. Критерием окончания является третье условие (8.5);

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

Обычно это делается следующим образом. Задаются координаты точки , а координаты остальных точек определяются с помощью соотношения:

(8.8)

где h-параметр, который определяет стороны многогранника.

Точки являются сторонами равнобедренного многогранника (на плоскости это треугольник).

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

(8.9)

Далее вычисляется пробная точка:

(8.10)

которая является симметричным отражением исключенной точки относительно точки (Рис.8).

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

а) значение в пробной точке лежит между значениями исходных точек . Тогда исключенная точка сразу заменяется на пробную точку , и рассматривается новый многогранник с точками , где , а .

б) значение в пробной точке

меньше чем в исключенной точке

. Это значение также меньше, чем значение функции во всех остальных исходных точках

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

(8.11)

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

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

в) значение в пробной точке больше, чем в исключенной точке . Тогда выбирается новая пробная точка внутри многогранника:

(8.12)

и тоже рассматривается новый многогранник с точками , где , а . Многогранник при этом также деформируется.

Периодически, после нескольких деформаций многогранника (обычно после 4-5 деформаций) многогранник восстанавливают. За новую базовую точку принимается точка, в которой функция минимальна, а величина шага h выбирается равной половине средней длине всех граней, исходящих из точки .

Процесс заканчивается, когда длины всех сторон многогранника, выходящих из точки с минимальным значением, станут меньше некоторого выбранного e или после очередного восстановления параметр h/2 станет меньше e.

Варианты задания №11

Найти точку минимума функции U(x,y) с точностью 0,1 указанным методом: а-покоординатный спуск, б-простой градиентный метод, в-метод наискорейшего спуска, г-метод деформированного многогранника.

1. 2.