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

уровня

Дана целевая функция

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

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

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

Градиентные

Безградиентные

Орта – единичный связанный вектор, направленный вдоль координатной оси.

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

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

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

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

Касательная

задаем начальное

приближение

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

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

И единичный вектор градиента

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

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

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

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

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

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

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

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

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

треугольник

n=3 тетраэдр

приближение

2. Вычисляем координаты вершин симплекса

4. Определяем худшую вершину

она будет лежать на прямой исходящей из худшей вершины и проходящей через середину противоположной грани

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

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

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

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

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

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

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

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

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

kl:=1

Fi

i:=1 шаг 1 до 3

Fl:=Fi: kl:=i

начало

h=1, eps=0.2

Пример: