ИСПОЛЬЗОВАНИЕ УНИВЕРСАЛЬНОГО АЛГОРИТМА В МЕТОДЕ ПАРАБОЛ ПРИ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ - Студенческий научный форум

XII Международная студенческая научная конференция Студенческий научный форум - 2020

ИСПОЛЬЗОВАНИЕ УНИВЕРСАЛЬНОГО АЛГОРИТМА В МЕТОДЕ ПАРАБОЛ ПРИ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

Лебедев В.М. 1, Гданский Н.И. 1
1МГУТУ имени К. Г. Разумовского
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

1. Введение

В зависимости от применяемого математического аппарата методы оптимизации однопараметрических функций подразделют на: аналитические, пассивные последовательные и аппроксимационные,

В аналитических методах используется дифференциальное исчисление, а также методы математического анализа. Данные методы удобны в применении. Однако их область применения ограничена только дифференцируемыми функциями.

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

Последовательные методы используют специальные алгоритмы для выбора расчетных точек. У них значительно сокращается число необходимых вычислений значений функции по сравнению с пассивными методами. Самые лучшие результаты дают методы золотого сечения и метод Фибоначчи.

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

2. Основная идея квадратичной аппроксимации

Основной идеей метода являетсяприближенная аппроксимация, применяемая для целевой функции F(x), в которой применяется квадратическая парабола, имеющая вид P2(x)= C0+ C1x + C2x2.В силу того, что число неизвестных постоянных коэффициентов равно 3, для построения такой параболы требуется также задать три точки на плоскости. Как правило – это граничные точки исходного интервала[a,b], а также некоторая точка внутри его.

При этом набор уравнений для расчета неизвестных коэффициентов параболы принимает вид:

C0 + C1a + C2a2 = F(a);

C0 + C1c + C2c2 = F(c);

C0 + C1b + C2b2 =F(b).

Искомая xэкстрминимума на параболе (в случаеC2>0) находится для дифференцируемой функции в стационарной точке, в которой удовлетворяется условие вида:P2(xэкстр) = 2C2xэкстр + C1 = 0.

Вышеприведенные зависимости дают следующие формулы:

Такой метод достаточно точноприближает дифференцируемую функцию F(x), поскольку в окрестности точки искомого минимума функция может быть разложена в ряд Тейлора 2-го порядка:

F(x) =F(с)+ F(x)(х-с)+(1/2!)F(x)(х-с)2 + o ((х-с)2),

через o((х-с)2) обозначено остаточное значение малого порядка.

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

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

2. Для недифференцируемой функции сходимость может быть очень медленной.

3. В тех случаях, когда точки для аппроксимации(a,F(a)), (b,F(b)), (c,F(c))попадают на одну прямую, метод вообще не работает.

лежат на одной прямой (например, у функции, график которой имеет вид ломаной), то

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

3.Исправленный универсальный алгоритм метода парабол

Назовем исправленный вариант метода универсальным .

Исходные данные:

1) [a,b] – границы заданного интервала,

2) с - внутренняя точка, a<c<b,

3) F(a),F(c),F(b) - значения F(x)в точкахa,b,с,

4) - точность.

Выходные данные:

1)[a,b] – результирующие границы доверительного интервала, b-a<,

2) xmin– найденное в результате оптимальное значение параметра,

3) Fmin - оптимум целевой функции,Fmin = F(xmin).

Начало цикла по условию (b-a> ).

Шаг 1. Выяснениеблизостиимеющейся внутренней к крайним и ее коррекция.

Если (с-a)/(b-a)<0,1; то xmin:=с+ (b-с)/4, переход на Шаг 7.

Если (b-с)/(b-a)<0,1; то xmin:=с- (с-а)/4, переход на Шаг 7.

Шаг 2. Определение старшего коэффициента параболы C2. ЕслиC2 = 0, то переход на Шаг 3 либо 4 .

Шаг 3. C2=0. В этом случае парабола превращается в прямую линию, общепринятыеформулы применять нельзя.

При F(a)<F(b):xmin:=(a+с)/2, b:=c; иначе: xmin:=(b+c)/2, а:=c. Fmin = F(xmin).Переход на конец цикла .

Шаг 4 .C20. Аппроксимирующая кривая является параболой. Расчет величины xэкстр. При выполнении условий C2 < 0 ,C2>0 переход на Шаг 5 либо 6.

Шаг 5 .C2<0. В этом случае парабола направлена вниз и в точке xminбудет локальный максимум.

При xэкстр<(а+b)/2 : xmin:=(b+c)/2, а:=c; иначе: xmin:= (a+ с)/2, b:=c. Fmin =F(xmin).Переход на конец расчета.

Шаг 6 .C2>0. В этом случае парабола направлена вверх и в точке xэкстр- локальный минимум.

При xэкстр а: xmin:=(a+с)/2, b:=c, Fmin = F(xmin).Переход на конец цикла.

При xэкстрb: xmin:=(b+c)/2, a:=c, Fmin =F(xmin).Переход на конец цикла.

Оценка близости пробной точки к средней точке c и соответствующая коррекция доверительного интервала.

При xэкстр<c, xэкстрc:xmin = c – 0,1/2.

При xэкстр>c, xэкстрc:xmin = c + 0,1/2.

Данная ситуация возникает, например, уже на втором шаге, если F(x) сама является квадратичной параболой.

Если a<xэкстр<bиxэкстр с : xmin:= xэкстр.

Шаг 7 . Расчет значения функции в точке xmin: Fmin = F(xmin).

Сокращение доверительного интервала.

Если xmin<c, то при Fmin<F(c): b:=c, c:=xmin; иначе: а:=xmin .

Если xminc, то при Fmin<F(c): а:=c, c:=xmin; иначе: b:=xmin .

Конец цикла.

Завершение поиска.

В качестве искомого оптимального значения xminпринимаем ту из величин a, b, с, полученных на последнем шаге, в которой значение целевой функции минимально.

Завершение работы алгоритма.

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

Пример. Необходимо найти минимум F(х) =3- 2 на интервале [0,2;2]при помощи универсального алгоритма метода парабол с заданной внутренней точкой интервала с=0,4 при точности =0,5.

Решение. При последовательном выполнении шагов переходы к ним не оговариваются.

Шаг 0. Предварительные действия. Рассчитываем значения функции в точках a,b,c: F(a)=-0,10; F(с)=-0,35; F(b)=4.

Цикл по условию (b-a> ).

Итерация 1. Шаг 1. Условия (с-a)/(b-a)<0,1; (b-с)/(b-a)<0,1 не выполняются.

Шаг 2.РасчетC2. C2 = [(F(b)-F(a))/(b-a)-(F(c)-F(a))/(c-a)]/(b-c)= [(4)/(1,8)-(-0,25)/(0,2)]/(1,6)=2,2.Переход на Шаг 4.

Шаг 4.xэкстр = 0,58. Так как С2>0 то переход на Шаг 6.

Шаг 6. В результате проверки выхода xэкстрза пределы отрезка [a,b] и близости к средней точке c, выявлено, что ни одно из этих условий не выполняется, поэтому xmin:= xэкстр.

Шаг 7. Расчет значения функции в точке xmin: Fmin =F(xmin)=-0,62.

Сокращение доверительного интервала.

Так как xэкстрc и Fmin<F(c), то а:=c=0,4; c:=xmin=0,58.

Итерация 2. Шаг 1. Условия не выполняются.

Шаг 2.C2 =2,96>0. Переход на Шаг 4.

Шаг 4.xэкстр = 0,74. Переход на Шаг 6.

Шаг 6. Условия не выполняются, xmin:= xэкстр.

Шаг 7.Fmin =F(xmin)=-0,83.

Так как xmincи Fmin<F(c), то а:=c=0,58; c:=xmin=0,74.

Итерация 3. Шаг 1. Условия не выполняются.

Шаг 2.C2 =3,66>0. Переход на Шаг 4.

Шаг 4.xэкстр = 0,84. Переход на Шаг 6.

Шаг 6. Условия не выполняются, xmin:= xэкстр.

Шаг 7.Fmin =F(xmin)=-0,93.

Так как xmincи Fmin<F(c), то а:=c=0,74; c:=xmin=0,84.

Итерация 4. Шаг 1. Так как (с-a)/(b-a)=(0,1)/(1.16)<0,1, то:xmin:= с+ 0,25 (b-с)/2=1,13. Переход на Шаг 7.

Шаг 7.Fmin =F(xmin)=-0,94.

Так как xmincи Fmin<F(c), то а:=c=0,84; c:=xmin=1,13.

Итерация 5. Шаг 1. Условия не выполняются.

Шаг 2.C2 =4,95>0. Переход на Шаг 4.

Шаг 4.xэкстр = 0,99. Переход на Шаг 6.

Шаг 6. Условия не выполняются, xmin:= xэкстр.

Шаг 7.Fmin =F(xmin)=-0,9998.

Так как xmin<cи Fmin<F(c), то b:=c=1,13; c:=xmin=0,99.

Поскольку (b-а)=0,29<, то цикл завершается.

В качестве искомого xminпринимаем величину с, поскольку в ней значение функции минимально и равно Fmin = -0,9998.

Ответ: Выполнено 5 итераций, вычислено 8 значений функции, найден доверительный интервал [0,84;1,13].xmin=0,99;Fmin = -0,9998.

Рассмотренный вариант метода парабол при масштабах порядка 102 – 103 и выше в среднем работает быстрее метода Фибоначчи – наиболее быстрого регулярного метода.. Поскольку сам он не является регулярным, для него в общем случае нет оценок скорости сходимости.

Заключение

Лучшие регулярные последовательные методы одномерного поиска в среднем значительно уступают в скорости сходимости лучшим аппроксимационным. Однако их реализация должна учитывать существенные особенности данных методов.

Список литературы

1. Аттетков А.В. Методы оптимизации / А.В.Аттетков, В.С. Зарубин, А.Н.Канатников.- М.: ИЦ РИОР, НИЦ ИНФРА-М,2013.-270 с.

2. Корнеенко В.П. Методы оптимизации / В.П. Корнеенко.- М.: Высшая школа, ИНФРА-М,2007.-664 с.

3. Измаилов А.Ф. Численные методы оптимизации / А.Ф. Измаилов, М.В.Солодов - М.: Физматлит, 2008.-320 с.

4. Гданский Н.И., Карпов А.В., Марченко Ю.А. Оптимальное равномерное приближение произвольных непрерывных функций при помощи ломаных линий. Математические методы в технике и технологиях – ММТТ-23. Сб. трудов ХХIII МНК.: в 12 т.- Т.2. Секция 5 /под ред. В.С. Балакирева. Саратов, СГТУ, 2010, с. 32-36.

Просмотров работы: 19