Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Методы исключения интервалов
|
|
Численные методы. Оптимизация функции одного аргумента
Оптимизация – нахождение наибольшего или наименьшего значения какой-либо функции, или выбор наилучшего варианта из множества возможных.
x* – точка минимума, если в ее окружности выполняется условие f(x)> f(x*). Необходимое условие минимума: значение первой производной в данной точке должно быть равным нулю. Достаточное условие минимума: вторая производная функции в этой точке больше нуля. Функция называется унимодальной, если на отрезке [a, b] имеется единственная точка, удовлетворяющая условию минимума.
Метод Свенна
В соответствии с этим методом (k+1)-я пробная точка определяется по рекуррентной формуле:
xk+1=xk+2kD, k=0, 1, 2, …,
где x0 – произвольно выбранная начальная точка
D - подбираемая некоторым способом величина шага.
Знак D определяется путем сравнения значений f(x0), f(x-0+|D|) и f(x0-|D|).
Если f(x0-|D|)³ f(x0)³ f(x0+|D|), то согласно предположению об унимодальности, точка минимума должна располагаться правее точки x0 и величина D выбирается положительной.
Если f(x0-|D|)< f(x0)< f(x0+|D|), то D следует выбирать отрицательной.
Если f(x0-|D|)³ f(x0)£ f(x0+|D|), то точка минимума лежит между x0-|D| и x0+|D| и поиск граничных точек завершен.
Случай, когда
f(x0-|D|)£ f(x0)³ f(x0+|D|), противоречит предположению об унимодальности.
Выполнение этого условия говорит о том, что функция не является унимодальной.
Пример.
Рассмотрим задачу минимизации функции f(x)=(100-x)2 при заданной начальной точке x0=30 и величине шага |D|=5.
Знак D определяется на основе сравнения следующих значений:
f(x0)=f(30)=4900,
f(x0+|D|)=f(35)=4225,
f(x0-|D|)=f(25)=5625.
Так как f(x0-|D|)³ f(x0)³ f(x0+|D|),
5626 ³ 4900³ 4225
то величена D должна быть положительной, а координата точки миимума должна быть больше 30.
Имеем x1=x0+D=35. f(35)=4225.
Далее x2=x1+2D=45,
f(45)=3025< f(x1)=4225, откуда x*> 35.
x3=x2+22D=65, f(65)=1225< f(x2)=3025, откуда x*> 45.
x4=x3+23D=105, f(105)=25< f(x3)=1225, откуда x*> 65.
x5=x4+24D=185, f(185)=7225> f(x4)=25, следовательно, x*< 185.
Таким образом, мы выявили интервал 65£ x*£ 185, в котором расположена точка x*.
Можно определить, что эффективность поиска граничных точек непосредственно зависит от величины шага D.
Если D велико, то получаем грубые оценки координат граничных точек, и построенный интервал оказывается весьма широким.
С другой стороны, если D мало, для определения граничных точек может потребоваться достаточно большой объем вычислений.
Методы исключения интервалов
Оптимизационные задачи решаются определением двух ситуаций:
1. Определяется, является ли данная точка точкой минимума.
2. Если данная точка не является точкой минимума, то каким образом можно достигнуть минимума.
Задача оптимизации функции одной переменной может быть решена методом исключения интервалов.
Дана функция f(x) унимодальная на [a, b]. Определить, является ли рассматриваемая точка точкой минимума, если нет, то каким образом ее достичь. Для функции одной переменной могут быть использованы методы, ориентированные на поиск минимума внутри интервала унимодальности путем последовательного исключения подинтервала и уменьшения интервала поиска, основанного на предположении о унимодальности, которое позволяет использовать значение функции в двух точках для определения подинтервала, содержащего точку оптимума. Пусть даны x1 и x2, такие, что a< x1< x2< b, тогда могут иметь место 3 варианта:
1.
f(x1)> f(x2) x*Î [x1, b];
2.
f(x1)< f(x2) x*Î [a, x2];
3.
f(x1)=f(x2) x*Î [x1, x2].
Данное правило положено в основу группы методов исключения интервалов.
Поиск оптимума завершается, когда интервал уменьшается до достаточно малых размеров. Все методы данной группы выполняются в два этапа: первый – установление границ поиска; второй – уменьшение интервала.
На первом этапе выбирается начальная точка x0, затем подбирается относительно широкий интервал, содержащий точку оптимума. В качестве алгоритма определения границ можно использовать эвристический метод Свена. В соответствии с этим методом, границы интервала определяются по рекуррентной формуле
xk+1=xk+2kD, где k=0, 1, 2…
x0 – предварительно выбранная точка, D – предварительно выбранная величина шага. Знак D зависит от результата сравнения трех величин: f(x0-|D|), f(x0), f(x0+|D|). Возможны 4 варианта:
1. f(x0-|D|) £ f(x0) £ f(x0+|D|). Точка оптимума лежит левее x0.
2. f(x0-|D|) ³ f(x0) ³ f(x0+|D|). Точка оптимума лежит правее x0.
3. f(x0-|D|) ³ f(x0) £ f(x0+|D|). Точка оптимума лежит внутри интервала, поиск завершен.
4. f(x0-|D|) £ f(x0) ³ f(x0+|D|). Поиск минимума невозможен, т.к. функция не удовлетворяет условию унимодальности.
Определив D, увеличиваем на каждом шаге его значение в два раза до тех пор, пока не будет истинным третье неравенство.
В зависимости от абсолютного значения D варьируется эффективность поиска границ интервала. Большое значение дает более быстрый положительный результат, меньшее – дает меньшее значение интервала.