Методы оптимизации. Рейзлин В.И. - 6 стр.

UptoLike

Составители: 

Рубрика: 

Е заданная точность.
Как видно из формулы (1.1), для того чтобы получить начальную точку необходимо
заранее знать число вычислений функции, за которое будет в результате поиска получен
оптимум с заданной точностью. Ниже приводится алгоритм поиска для данного метода.
Шаг 1. Положить x0=a, x3=b. Вычислить значение x1 по формуле (1.1).
Вычислить значение f(x1).
Шаг 2. Положить x2=x0-x1+x3. Вычислить значение f(x2).
Шаг 3. Сравнить f(x2) и f(x1).
Если f(x2)>f(x1), сравнить x1 и x2.Если x2>x1, исключить интервал (x2, x3),
положив x3=x2. Перейти к шагу 4. Если x2<x1, исключить интервал (x0, x2),
положив x0=x2. Перейти к шагу 4. Если f(x2)<f(x1), сравнить x1 и x2. Если
x1>x2, исключить интервал (x1, x3), положив x3=x1, x1=x2, f(x1)=f(x2). Перейти к
шагу 4. Если x1<x2, исключить интервал (x0, x1), положив x0=x1, x1=x2,
f(x1)=f(x2). Перейти к шагу 4.
Шаг 4. Определить количество вычислений функции - k. Если k<N перейти
к шагу 2. В противном случае закончить поиск.
1.2. Полиномиальная аппроксимация и методы
точечного оценивания
Основная идея рассматриваемых методов связана с возможностью
аппроксимации гладкой функции полиномом и последующего использования
аппроксимирующего полинома для оценивания координаты точки оптимума /1,2/.
Необходимыми условиями эффективной реализации такого подхода являются
унимодальность и непрерывность исследуемой функции. Согласно теореме
Вейерштрасса об аппроксимации, если функция непрерывна в некотором
интервале, то ее с любой степенью точности можно аппроксимировать
полиномом достаточно высокого порядка. Следовательно, если функция
унимодальна и найден полином, который достаточно точно ее аппроксимирует,
то координату точки оптимума функции можно оценить путем вычисления
координаты точки оптимума полинома. Согласно теореме Вейерштрасса,
качество оценок координаты точки оптимума, получаемых с помощью
аппроксимирующего полинома, можно повысить двумя способами:
использованием полинома более высокого порядка и уменьшением интервала
аппроксимации. Второй способ, вообще говоря, является более
предпочтительным, поскольку построение аппроксимирующего полинома
порядка выше третьего становиться весьма сложной процедурой, тогда как
уменьшение интервала в условиях, когда выполняется предположение об
унимодальности функции, особой сложности не представляет.