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

найти такое значение
при котором функция
принимает экстремальное значение (минимальное

Процесс поиска экстремального значения иногда называют оптимизацией.

называют оптимизируемой или целевой функцией

называют вектором параметров оптимизации

В области определения функции может быть несколько экстремумов.

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

начального приближения:

Методы поиска экстремума будем рассматривать относительно случая поиска минимума, для функции двух переменных

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

f(x1,x2)

x1

x2

y

переменных x1 и x2.
Линии этих сечений проецируем на плоскость изменения

Определим зависимости x1 от x2 для соответствующих линий уровней.
Для заданной функции f(x1,x2) линии уровней будут представлять окружности с соответствующими радиусами:
R1=√1=1; R2=√2=1.41; R3=√3=1.73;

x2

x1

R3

R2

R1

вектор равный сумме произведений частных производных на соответствующие орты.
Градиентные
Безградиентные
Орта

Градиентный метод.

Градиент всегда направлен в сторону наиболее быстрого возрастания функции, т.е.

Основные свойства градиента:

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

Касательная

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

3. Вычисляем новое приближение, делая шаг в направление антиградиента

и вычисляем значение функции

4. Проверяем условие FZ < FX

переходим на пункт 2

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

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

7. Если условие выполняется, то выводим

Конец алгоритма

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

вершиной.

n=2 треугольник
n=3 тетраэдр

начальное приближение
2. Вычисляем координаты вершин симплекса
4. Определяем худшую вершину
она

и координаты отраженной вершины,

3. Вычисляем значения функции

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

9. Условие не выполняется. За

принимаем лучшую вершину последнего

5. Сравниваем значения функции

6. Условие выполняется. За новый симплекс принимаем симплекс с вершиной

и повторяем с пункта 3

h ||

Пример: