Математическая модель одномерной оптимизации. Приближенные методы решения: Метод ломаных
-
Математическая модель одномерной оптимизации:
Условие Липшица
Применение метода ломаных возможно только в случае, если
удовлетворяет на
условию Липшица.Функция удовлетворяет на отрезке условию Липшица, если существует такое число
(константа Липшица), что
для всех
и
,
принадлежащих
.Метод ломаных
Этот прямой метод рассчитан на минимизацию мультимодальных функций, удовлетворяющих условию Липшица. В нем используются кусочно-линейные аппроксимации функции , графиками которых являются ломаные. Рассмотрим построение аппроксимирующих кусочно-линейных функций
.Пусть функция удовлетворяет на отрезке условию Липшица с константой
.
Зафиксируем точку
и рассмотрим вспомогательную функцию
одной переменной:
Ее график выглядит так:
Введем аппроксимирующие кусочно-линейные функции ,
,
которые строятся следующим образом.
Рассмотрим две прямые
и
.
Они пересекаются в точке
с координатами
.Положим
График функции
показан на рисунке
,
ее точка минимума
,
а минимальное значение
.
Выберем точку глобального минимума функции , то есть
.
Используя вспомогательную функцию
,
определим следующую аппроксимирующую
функцию:
,у которой вместо точки минимума появились две новые точки локального минимума
и
(рис.
).
Точки минимума
и
,
а также сами минимумы
могут быть найдены из несложных
геометрических соображений.Далее выберем любую из точек глобального минимума функции
,
например,
,
и, обозначив
,
,
положим
.У функции
по сравнению с
вместо
появились две новые точки локального
минимума
и
(рис.
).Повторим этот процесс несколько раз. Пусть функция
построена. Выбрав произвольную точку
ее глобального минимума функции
и обозначив ее через
,
определим функцию
.Новые точки локального минимума
и
функции
,
появившиеся взамен
,
а также значения
в этих точках находятся по формулам:
Отметим некоторые свойства функций :
1. – непрерывная кусочно-линейная функция, ее графиком является ломаная, состоящая из отрезков с угловыми коэффициентами
.
У функции
существует ровно
локальных минимумов, точками которых
являются абсциссы вершин ломаной, а
сами эти минимумы равны ординатам
вершин.2. Для всех
и
справедливы неравенства
.Из этих свойств и способа построения функций следует, что с ростом
ломаные
приближаются снизу к графику функции
вблизи точек ее глобального минимума.
Идея метода ломаных состоит в том,
чтобы искать глобальный минимум не
функции
,
а ломаных
,
что значительно проще, так как точками
минимума могут быть только абсциссы
вершин этой ломаной, определяемые в
ходе построения последовательности
.Ответ на вопрос можно построить так: 1) рассказать об условиях применимости метода ломаных; 2) указать идею метода; 3) подробно показать построение кусочно-линейной аппроксимации исследуемой функции на примере с рисунком (стараясь не приводить слишком много формул); 4) указать основное достоинство метода.
Алгоритм метода не надо.