Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
17
Добавлен:
13.02.2015
Размер:
704.51 Кб
Скачать

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

 

 

 

 

 

 

Дана некоторая функция многих переменных f(x1,x2,x3,…..,xn) или

f ( x )

 

 

 

 

надо найти такое значение x*,

при котором функция

f (x*)

 

принимает экстремальное значение (минимальное или максимальное).

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

 

 

f ( x )

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

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

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

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

(0)

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

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

 

минимума, для функции двух переменных

1

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

 

 

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

f ( x ) x12 x22

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

y

f(x1,x2)

x2

x1

2

Проведем сечения поверхности равно отстоящими плоскостями, которые параллельны плоскости изменения переменных x1 и x2.

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

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

y1 x12

x22

 

 

 

 

 

 

 

 

 

1

Определим зависимости x1 от x2 для

x1

1 x22

 

 

 

 

 

 

соответствующих линий уровней.

 

 

 

 

 

y

 

x2

x2

2

x1

 

2 x22

2

Для заданной функции f(x1,x2) линии уровней

 

 

1

2

 

 

будут представлять окружности с

 

 

 

 

 

y3 x12

x22

3

 

 

 

 

 

 

 

соответствующими радиусами:

x

 

3 x2

 

 

 

 

 

 

R1=√1=1; R2=√2=1.41; R3=√3=1.73;

1

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x1

 

 

 

 

 

 

 

 

 

 

 

 

 

R1

 

 

 

 

 

 

 

 

 

 

 

 

 

R2

x2

 

 

 

 

 

 

 

 

 

 

 

 

R3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

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

f (x1, x2 ) (x12 x2 11)2 (x1 x22 7)2

4

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

•Градиентные

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

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

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

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

 

1

 

0

 

 

0

 

 

 

 

 

 

 

 

 

 

e 1

0

e 2

1

 

 

e n 0

 

.

 

 

.

 

 

 

.

 

 

 

 

 

 

 

 

 

 

 

 

0

 

0

 

 

1

 

 

 

 

 

 

 

 

 

 

f

 

 

 

 

 

 

 

 

 

 

 

 

 

x1

 

 

 

 

 

 

 

 

 

 

 

 

 

f

 

 

 

 

 

 

f

 

f

 

f

 

 

 

 

 

 

 

grad(f ( x ))

e1

e 2 .........

e n

x2

 

 

 

 

x1

x2

xn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

xn

5

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

1.Норма градиента определяет скорость изменения функции в направление градиента.

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

3.Градиент перпендикулярен линии уровня.

grad(f ( x ))

Касательная

grad(f ( x ))

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

6

Алгоритм

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Дана функция n переменных

f ( x ),

точность ε, параметр шага h, задаем начальное

 

 

 

 

(0)

 

 

 

 

 

 

 

 

 

приближение x x

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

FX f ( x )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

G grad(f ( x ))

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

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

V

 

 

 

G

 

 

 

 

 

 

 

 

 

 

 

 

 

|| G ||

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

x h V

 

 

 

 

 

 

 

 

 

 

 

 

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

FZ f ( z )

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x z и FX FZ

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

 

 

 

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

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

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

7

начало

 

 

 

 

 

 

 

 

 

 

 

 

(0)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

,h, || f (x)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(0)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x x

: FX f (x)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G grad(f ( x )) : V

 

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

|| G ||

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

z

x h V :

FZ f ( z )

 

 

 

 

 

 

 

 

 

 

 

h:=h/3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

FZ<FX

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x z :

FX FZ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пример:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f ( x ) 8x12 4x1x2 5x22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x , FX

 

 

 

 

 

 

 

 

 

 

 

0.2

h 2

(0)

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

конец

 

 

 

 

 

 

 

 

 

 

 

2

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

FX

G

|| G ||

V

h

z

FZ

Примечание

2

68.00

40

48.8

0.82

2

0.36

5.918

да

2

 

28

 

0.57

 

0.85

 

 

0.36

5.918

9.2

13.6

0.68

2

-0.99

12.27

нет

0.85

 

9.98

 

0.74

 

-0.62

 

 

0.36

5.918

9.2

13.6

0.68

0.66

-0.09

0.6090

да

0.85

 

9.98

 

0.74

 

0.37

 

 

-0.09

0.6090

0.1

3.34

0.03

0.66

-0.11

0.6380

нет

0.37

 

3.33

 

1

 

-0.29

 

 

-0.09

0.6090

0.1

3.34

0.03

0.22

-0.09

0.1230

да

0.37

 

3.33

 

1

 

0.15

 

 

-0.09

0.123

-0.89

1.42

-0.62

0.22

0.04

0.0150

да

0.15

 

1.11

 

0.78

 

-0.02

 

 

0.04

0.0150

0.62

0.62

1

0.22

-0.17

0.2440

нет

-0.02

 

-0.06

 

-0.1

 

0

 

 

0.04

0.0150

0.62

0.62

1

0.07

-0.02

0.0080

да

-0.02

 

-0.06

 

-0.1

 

-0.02

 

 

-0.02

0.0080

-0.47

0.54

-0.86

0.07

0.04

0.0140

нет

-0.02

 

-0.27

 

-0.5

 

0.02

 

 

*

0.02

 

9

x

f ( x ) 0.0080

0.02

 

68

5.92

0.61

0.01 0.12

12.3

0.64

10

Соседние файлы в папке Лекции по VBA

Калькулятор

Сервис бесплатной оценки стоимости работы

  1. Заполните заявку. Специалисты рассчитают стоимость вашей работы
  2. Расчет стоимости придет на почту и по СМС

Нажимая на кнопку, вы соглашаетесь с политикой конфиденциальности и на обработку персональных данных.

Номер вашей заявки

Прямо сейчас на почту придет автоматическое письмо-подтверждение с информацией о заявке.

Оформить еще одну заявку