Лекция1_Классификация_многомерных и_ одномерные.ppt

функции
Классификация методов многомерной оптимизации
Методы нахождения минимума функции одной

переменной

в конкретной ситуации решения или, что тоже самое, сделать наилучший

выбор из множества допустимых вариантов:

сколько и куда вложить денег, чтобы получить наибольшую прибыль

по какой дороге поехать, чтобы сэкономить бензин, время и при этом обеспечить безопасность

как выбрать параметры прибора, что бы при его минимальной стоимости изготовления достигался максимум КПД.

требуется построить математическую модель, описывающую конкретную ситуацию

Формулировка модели содержит

некоторое количество параметров

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

Ценность каждого варианта определяется числом, которое называется критерием.
Если удается сопоставить каждому варианту определенное значение критерия то получаем целевую функцию

- величина прибыли при вложениях x1..xn

- длина дороги через пункты x1..xk

- величина КПД при значениях x1..xn

В результате, задача принятия оптимального решения приводит к нахождению оптимального (максимального или минимального) значения
Следует отметить, что нахождение максимума

эквивалентно нахождению минимума
поэтому стандартные программы разрабатываются, как правило, для нахождения

что имеет локальный минимум в

точке
если существует некоторая ε-окрестность точки , в которой выполняется


Будем полагать, что непрерывная дважды дифференцируемая функция.

переменных основаны на многократном повторении следующих двух действий:
выбор в области

параметров некоторого направления спуска;
спуск к минимуму вдоль выбранного направления.

единичный вектор выбранного направления в точке ,

то уравнение прямой, проходящей через эту точку в направлении , записывается в виде



где параметр z , соответствующий точкам на прямой (модуль z есть расстояние от текущей точки до ).
Значения функции вдоль этой прямой можно описать функцией одной переменной


Изменяя z двигаемся вдоль этой прямой, находим точку , в которой функция имеет меньшее значение, чем в точке
Обычно находим минимум функции одной переменной

более проста и ее решение находится одним из методов

нахождения минимума функции одной переменной
Часто лучшие результаты дает стратегия небольшого спуска в сторону уменьшения.
После нахождения zm следует перейти в новую точку и, выбрав в этой точке новое направление, опять выполнить спуск по направлению и т.д., пока не будет достигнут минимум.

x1

x2

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

выбора направлений и методов спуска в выбранном направлении.

спуска требуют вычисления только значений функции (методы: Гаусса-Зейделя, Пауэлла, ДСК,

Розенброка, Хука-Дживса, Нелдера-Мида).

МЕТОДЫ ПЕРВОГО ПОРЯДКА - требуют вычисления (точного или приближенного) градиента функции (методы: градиентный, сопряженных градиентов, Давидона-Флетчера-Пауэлла (ДФП), Флетчера-Ривса и др.).

МЕТОДЫ ВТОРОГО ПОРЯДКА - требуют вычисления как градиента, так и матрицы вторых производных (методы: Ньютона, Ньютона-Рафсона).

МЕТОДЫ С ПЕРЕМЕННОЙ МЕТРИКОЙ – занимают промежуточное место между методами 1-го и 2-го порядка.

разбить на два класса:
1) методы уточнения минимума на заданном интервале

[a, b] (метод деления пополам, метод золотого сечения);
2) методы спуска к минимуму из некоторой начальной точки x0 (метод последовательного перебора, метод квадратичной параболы, метод кубической параболы).

Ниже рассмотрим только методы спуска

что, спускаясь из точки x0 с заданным шагом h в

направлении уменьшения функции, устанавливают интервал длиной h, на котором находится минимум, и затем его уточняют.
Уточнение можно осуществить либо методом золотого сечения, либо повторяя спуск с последней точки, уменьшив шаг и изменив его знак.
Алгоритм последнего варианта приведен ниже

.
1. В точке x0 вычисляется x1=x0 и y1=f(x1).
2. x0=x1,

y0=y1 - запоминается удачная точка.
3. x1=x0+h, y1=f(x1) - делаем следующий шаг в удачном направлении.
4. Если функция убывает, y1 иначе п.5.
5. h=-h/4. В точке x1 функция оказалась большей, чем в x0, следовательно, мы перешагнули точку минимума и организуем спуск в обратном направлении.
6. Если , тогда повторить с п.2, иначе перейти к п.7.
7. конец.

некоторой точки x0 используют локальные свойства функции вблизи этой точки.

Так, скорость и направление убывания можно определить по величине и знаку первой производной.
Вторая производная характеризует направление выпуклости: если f''>0, то функция имеет выпуклость вниз, иначе - вверх.
Вблизи локального безусловного минимума дважды дифференцируемая функция всегда выпукла вниз.
Поэтому, если вблизи точки минимума функцию аппроксимировать квадратичной параболой, то она будет иметь минимум. Это свойство и используется в методе квадратичной параболы

значения y1, y2, y3.
Через эти точки проводится квадратичная парабола
Находится

ее минимум xm1

x1 x2 x3

h

x

Y

ϕ(x)

xm1

P1(x)

P2(x)

xm2