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

1. Введение

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

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

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

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

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

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

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

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

C₀ + C₁a + C₂a² = F(a);

C₀ + C₁c + C₂c² = F(c);

C₀ + C₁b + C₂b² =F(b).

Искомая x_экстрминимума на параболе (в случаеC₂>0) находится для дифференцируемой функции в стационарной точке, в которой удовлетворяется условие вида:P₂(x_экстр) = 2C₂x_экстр + C₁ = 0.

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

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

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

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

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

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) x_min– найденное в результате оптимальное значение параметра,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если a<x_экстр<bиx_экстр≠ с : x_min:= x_экстр.

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

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

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

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

Конец цикла.

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

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

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

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

Пример. Необходимо найти минимум F(х) = 2х³- 3х² на интервале [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.РасчетC₂. C₂ = [(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. Так как С₂>0 то переход на Шаг 6.

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

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

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

Так как x_экстрc и F_min<F(c), то а:=c=0,4; c:=x_min=0,58.

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

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

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

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

Шаг 7.F_min =F(x_min)=-0,83.

Так как x_mincи F_min<F(c), то а:=c=0,58; c:=x_min=0,74.

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

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

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

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

Шаг 7.F_min =F(x_min)=-0,93.

Так как x_mincи F_min<F(c), то а:=c=0,74; c:=x_min=0,84.

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

Шаг 7.F_min =F(x_min)=-0,94.

Так как x_mincи F_min<F(c), то а:=c=0,84; c:=x_min=1,13.

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

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

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

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

Шаг 7.F_min =F(x_min)=-0,9998.

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

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

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

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

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

Заключение

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

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

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

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

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

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

Код для цитирования: Скопировать