Тема 6.8. Многомерная оптимизация

Пример 6.8.1-1. Найти точку локального минимума функции.

f(x, y) = x² + y² – 4x + 100 – 8y.

Следовательно, в точке x* = 2 и y* = 4 функция имеет локальный минимум.

Пример 6.8.1-2. Найти точку локального минимума функции
f(x, y)= x²+y²–4x+10xy–8y.

Следовательно, функция не имеет точки локального минимума.

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

Методы спуска

Большинство итерационных методов, применяемых для решения задач безусловной минимизации функции нескольких переменных, относятся к классу методов спуска. Это такие методы, для которых каждая итерация (шаг) приводит к уменьшению значения целевой функции: f(x_k₊₁)< f(x_k), для всех k³ 0.

Структура типичного алгоритма метода спуска для функции двух переменных Q(x, y) состоит в следующем:

1. Задается начальная точка (x₀, y₀), принадлежащая области допустимых значений функции.

2. На текущей k-й итерации (k=0, 1, …n) определяется вектор задающий направление спуска, причем такой, чтобы для всех достаточно малых значений l> 0 (где l- коэффициент, являющийся шагом поиска) выполнялось неравенство:

f(x_k+ lp_k, y_k+ ls_k) < f(x_k, y_k).

3. Вычисляется шаг поиска - l_k, для которого выполняется условие п.2, и за очередное приближение к точке минимума принимается точка:

(x_k + lp_k, y_k+ ls_k), где x_k + lp_k = x_k₊₁, а y_k+ ls_k = y_k₊₁.

4. Проверяется выполнение критерия окончания итераций. Если критерий метода выполняется, то полагают (x*, y*)»(x_k₊₁, y_k₊₁). В противном случае осуществляется переход к п.2 и выполняется следующая итерация.

Последовательность точек х₁, х₂, …, х_k_, получаемую методом спуска, называют траекторий спуска.

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

Для использования градиентного метода оптимизации необходимо определить правило выбора шага ( l_k ) на каждой итерации и правило прекращения итерационного процесса.

При решении вопроса о выборе шага l_k следует учитывать, что выбор малого шага на каждой итерации приведет к малым изменениям аргумента и функции, и, следовательно, к увеличению числа итераций, необходимых для решения задачи. Выбор слишком большого шага l_k может привести не к убыванию целевой функции Q(x, y), а к ее увеличению, и, следовательно, процесс не будет сходиться к точке минимума.

Алгоритм метода градиентного спуска приведен на рис. 6.8.2-1.

По способу выбора шага спуска среди градиентных методов наиболее известными являются метод градиентного спуска с дроблением шага ( ГДШ ) и метод наискорейшего спуска ( НС ).

Рис. 6.8.2-1. Алгоритм метода градиентного спуска

Пример 6.8.3-1. Найти минимум функции Q(x, y) методом ГДШ.

Пусть Q(x, y) = x² +2y²; x₀ = 2; y₀ = 1.

Проверим достаточные условия существования минимума:

Проделаем одну итерацию согласно алгоритму.

1. Q(x₀, y₀) = 6.

2. При х = x₀ и y = y₀,

3. Шаг l_k = l₀ = 0, 5

Таким образом, 4 < 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

Метод наискорейшего спуска

Суть метода состоит в следующем. Из выбранной точки (x₀, y₀) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча (рис. 6.8.4-1). В найденной точке луч касается линии уровня. Затем из этой точки спуск проводится в направлении антиградиента (перпендикулярном линии уровня) до тех пор, пока соответствующий луч не коснется в новой точке проходящей через нее линии уровня, и т.д.

Рис. 6.8.4-1

Выразим целевую функцию Q(x, y) через шаг l. При этом представим целевую функцию на определенном шаге как функцию одной переменной, т.е. величины шага

Величина шага на каждой итерации определяется из условия минимума функции :

= min( (l)) l_k = l*(x _k, y _k), l > 0.

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

- аналитический метод (НСА);

- численный метод (НСЧ).

В методе НСА значение шага получают из условия , а в методе НСЧ величину l_k находят на отрезке [0; 1] c заданной точностью, используя один из методов одномерной оптимизации.

Алгоритм выбора шага в методе наискорейшего спуска с использованием метода золотого сечения приведен на рис. 6.8.4-2.

Рис. 6.8.4-2. Алгоритм выбора шага в численном методе наискорейшего спуска НСЧ

с использованием метода золотого сечения

Пример 6.8.4-1. Найти минимум функции Q(x, y)=x² + 2y²с точностью e=0.1, при начальных условиях: x₀=2; y₀=1.

Проделаем одну итерацию методом НСА.

Выразим целевую функцию через величину l:

=(x-2lx)²+2(y-4ly)² = x²-4lx²+4l²x²+2y²-16ly²+32l²y².

Из условия ¢ (l)=0 найдем значение l*:

Полученная функция l=l(x, y) позволяет найти значение l. При x=2 и y=1 имеем l=0.3333.

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

Проверим выполнение критерия окончания итераций при k=1:

Поскольку |2*0.6666|> 0.1 и |-0.3333*4|> 0.1, то условия окончания процесса итераций не выполнены, т.е. минимум не найден. Поэтому следует вычислить новое значение l при x=x₁ и y=y₁ и получить координаты следующей точки спуска. Вычисления продолжаются до тех пор, пока не выполнятся условия окончания спуска.

Отличие численного метода НС от аналитического состоит в том, что поиск значения l на каждой итерации происходит одним из численных методов одномерной оптимизации (например, методом дихотомии или методом золотого сечения). При этом в качестве интервала неопределенности служит диапазон допустимых значений l - [0; 1].

Пример 6.8.6-2. Решить задачу оптимизации для функции двух переменных градиентным методом.

Начальные значения переменных для поиска минимума

Решение: xmin=0 ymin=0 f(xmin, ymin)=0

Пример 6.8.6-3. Решить задачу оптимизации с помощью встроенных функций miner( ).

Построим трехмерный график функции f(x, y)

Построим график линий уровня функции f(x, y)

Пример 6.8.6-4. Решить задачу оптимизации с помощью встроенных функций

Maximize (Minimize).

Пример 6.8.6-5. Определить минимум функции .

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

Градиент – это

1) вектор, состоящий из вторых частных производных целевой функции

2) вектор, позволяющий определить направление убывания функции

3) вектор, состоящий из первых частных производных целевой функции

4) в списке нет правильного ответа

Антиградиент направлен

1) в сторону наискорейшего возрастания целевой функции

2) в сторону наискорейшего изменения целевой функции

3) в сторону наискорейшего убывания целевой функции

4) в списке нет правильного ответа

Модуль градиента показывает

1) направление возрастания функции

2) скорость возрастания функции

3) направление убывания функции

4) скорость убывания функции

Тема 6.8. Многомерная оптимизация

6.8.1. Постановка задачи и основные определения

6.8.2. Методы спуска

6.8.3. Метод градиентного спуска с дроблением шага

6.8.4. Метод наискорейшего спуска

6.8.5. Технология решения задач многомерной оптимизации средствами математических пакетов

6.8.5.1. Технология решения задач многомерной оптимизации средствами

MathCad

6.8.5.2. Технология решения задач многомерной оптимизации средствами

MatLab

6.8.7. Тестовые задания по теме «Многомерная оптимизация»

6.8.1. Постановка задачи и основные определения

Задача, требующая нахождения оптимального значения функции m переменных f(Х)=f(x₁, x₂, …, x_m), называется задачей многомерной оптимизации. Так же, как и для случая одномерной оптимизации, задача нахождения максимума функции сводится к задаче нахождения минимума путем замены целевой функции f на -f.

Пусть функция f(Х) = f(x₁, x₂, …, x_m) определена на некотором множестве ХÎ R^m. Если Х=R^m (т.е. ограничения на переменные x₁, x₂, …, x_m отсутствуют), принято говорить о задаче безусловной минимизации. В противном случае, когда Х ¹ R^m, говорят о задаче условной минимизации.

Методы решения задачи безусловной минимизации являются основой для перехода к изучению более сложных методов решения задач условной минимизации.

В постановке задачи безусловной оптимизации для f(Х)=f(x₁, x₂, …, x_m) требуется найти хотя бы одну точку минимума Х* и вычислить f*=f(Х*). Точка Х*Î R^m называется точкой глобального минимума функции f на множестве Х, если для всех ХÎ R^m выполняется неравенство f(Х*)£ f(Х). В этом случае значение f(Х*) называется минимальным значением функции f на R^m.

Точка Х*Î R^m называется точкой локального минимума функции f, если существует такая d - окрестность U_d этой точки (d> 0), что для всех ХÎ Х_d=Х U_d выполняется неравенство f(X*)£ f(X).

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

Рассмотрим функцию нескольких переменных и введем для нее основные определения.

Множество точек, для которых целевая функция принимает постоянное значение f(x₁, x₂, …, x_m) = c, называется поверхностью уровня. Для функции двух переменных (m = 2) это множество называется линией уровня.

Функция f(x₁, x₂) задает в трехмерном пространстве некоторую поверхность U=f(x₁, x₂) (рис. 6.8.1-1), низшая точка которой и дает решение задачи минимизации. Для того чтобы изобразить рельеф этой поверхности, проведем несколько плоскостей
(U = const): U=c₁, U=c₂, U=c₃. Проекции на плоскость Ох₁х₂ линий пересечений этих плоскостей с поверхностью и дают линии уровня.

Рис. 6.8.1-1

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

или .

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

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

Равенство нулю градиента в точке Х является необходимым условием того, чтобы внутренняя для множества Х_i (i = 1, 2, …m) точка Х была точкой локального минимума дифференцируемой функции f. Точка Х, для которой выполняется равенство f’(X) = 0, называется стационарной точкой функции.

Это равенство представляет собой систему из m нелинейных уравнений относительно компонент х₁, х₂, …, х_m, вектора X, где m – количество переменных.

Для функции двух переменных Q(x, y)это условие имеет вид:

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

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

Для функции двух переменных Q(x, y) матрица Гессе имеет вид:

а достаточное условие существования минимума:

Алгоритм решения задачи оптимизации функции двух переменных Q(x, y) аналитическим (классическим) методом следующий:

1. Составляется и решается система уравнений

из которой находятся (x*, y*).

2. Проверяются достаточные условия существования минимума

Если (x*, y*) – единственное решение и в этой точке выполняются достаточные условия, то это точка минимума. Если хотя бы в одном из неравенств получается знак “< ”, то минимума не существует. В случае появления знака “ = ” необходимо исследовать производные высших порядков.