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

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

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

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

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

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

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

Задача, требующая нахождения оптимального значения функции 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) это множество называется линией уровня.

Рис. 6.8.1-1

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

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

или .

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

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

Равенство нулю градиента в точке Х является необходимым условием того, чтобы внутренняя для множества Х_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*) – единственное решение и в этой точке выполняются достаточные условия, то это точка минимума. Если хотя бы в одном из неравенств получается знак “<”, то минимума не существует. В случае появления знака “ = ” необходимо исследовать производные высших порядков.

Дата добавления: 2014-12-27