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

Дана некоторая функция многих переменных f(x₁,x₂,x₃,…..,x_n) или надо найти такое значение при котором функция принимает экстремальное значение (минимальное или максимальное). Процесс поиска экстремального значения иногда называют оптимизацией. называют оптимизируемой или целевой функцией называют вектором параметров оптимизации. В области определения функции может быть несколько экстремумов. Все существующие методы многомерной оптимизации позволяют определить лишь один из экстремумов. Какой именно экстремум будет определён, зависит от выбора начального приближения: Методы поиска экстремума будем рассматривать относительно случая поиска минимума, для функции двух переменных.

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

Дана целевая функция  которая графически представляет собой поверхность параболоида вращения.

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

Определим зависимости x₁ от x₂ для соответствующих линий уровней. Для заданной функции f(x₁,x₂) линии уровней будут представлять окружности с соответствующими радиусами:

R₁=√1=1; 

 

 

R₂=√2=1.41; 

 

 

R₃=√3=1.73;

 

x1 y f(x1,x2) x2

Рис. 2.10.1. Трехмерная фигура – параболоид вращения.

 

x2 x1 R3 R2 R1

Рис. 2.10.2. Сечения фигуры – параболоида вращения.

 

Функция Химмельблау

 

Рис. 2.10.3. Функция Химмельблау.

 

fxx01=inline('(x1.^2+x2-11).^2+(x1+x2.^2-7).^2')

[x1,x2]=meshgrid(-4:0.05:4);

z=fxx01(x1,x2);

contour(x1,x2,z)

 

Все методы многомерной оптимизации делятся на два класса: градиентные; безградиентные.

 

 

Градиентный метод. Градиентом называется вектор равный сумме произведений частных производных на соответствующие орты. Орта – единичный связанный вектор, направленный вдоль координатной оси.

Касательная

Рис. 2.10.4. Градиент, антиградиент и касательная.

 

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

Алгоритм

1) Дана функция n переменных точность ε, параметр шага h, задаем начальное приближение вычисляем значение функции

2) Вычисляем вектор градиента  и единичный вектор градиента

3) Вычисляем новое приближение, делая шаг в направление антиградиента  и вычисляем значение функции

4) Проверяем условие Fz < Fx

5) Если условие выполняется, то за начальное приближение принимаем  т.е. , переходим на пункт 2.

6) Иначе, проверяем условие окончания h < ε

7) Если условие выполняется, то выводим Конец алгоритма

8) Если не выполняется, то уменьшаем параметр шага h=h/3 и переходим на пункт 2