Системы принятия решений

Оценки экстремума

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

Оценки экстремума для унимодальных функций
Пример. Унимодальная функция на отрезке [0,8].

Оценки экстремума для унимодальных функций
Пусть теперь в общем случае проведено k испытаний в точках и получены значения . Перенумеруем точки испытаний нижним индексом в порядке возрастания координаты, добавив к ним также концы отрезка поиска a и b, т.е.
Тогда интервалом неопределенности будет интервал , где номер i определяется из условия , где из (1.16) (в случаях i=1 и i=k интервалами неопределенности будут полуинтервалы и соответственно). Иными словами, для строго унимодальной функции можно построить оценку координаты глобального минимума в виде интервала неопределенности и тем самым оценить погрешность решения задачи (по координате) величиной , ибо
Что касается величины глобального минимума, то строгой унимодальности для получения оценки (1.18) недостаточно и требуются более жесткие условия для ее реализуемости.

Оценки экстремума для липшицевых функций
Другим важным классом функций, допускающим построение оценок экстремума по конечному числу испытаний, является класс функций, удовлетворяющих условию Липшица
(1.20)
Что означает неравенство (1.20)? Перепишем его в одномерном случае в виде
Является ли липшицева функция непрерывной?
Ответ положительный, поскольку согласно (1.20) малому приращению аргумента соответствует малое приращение функции.

Рассмотрим одномерную задачу
Является ли непрерывная функция липшицевой?
Является ли липшицева функция дифференцируемой?
Является ли дифференцируемая функция липшицевой?
Оценки экстремума для липшицевых функций

Возьмем некоторую точку из множества (1.19). Тогда для липшицевой функции, удовлетворяющей (1.20), для любого справедливо неравенство
или
где в правой части стоит возрастающая линейная функция
(1.22)
Оценки экстремума для липшицевых функций
(1.23)
(1.24)
значение которой в точке совпадает со значением .

Если мы обозначим как
правую часть неравенства (1.22), то в общем случае
значением миноранты. Это значит, что мы можем оценить погрешность решения (1.18) – погрешность по значению – величиной
а погрешность по координатам оценивается величиной области, в которой
Оценки экстремума для липшицевых функций

Оценки экстремума для липшицевых функций
Рассмотрим пример построения миноранты для конкретной функции
Это квадратичная функция с минимумом в точке и значениями на концах отрезка – в точках 1 и 7 , равными 9.5.

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

Оценки экстремума для липшицевых функций

Оценки экстремума для липшицевых функций
Берем точку . Для нее функция (1.23) имеет вид
а функция (1.24) -

Оценки экстремума для липшицевых функций
а функция (1.24)
Конструируем миноранту

Estimates of extremum for Lipschitzian functions

Оценки экстремума для липшицевых функций

Оценки экстремума для липшицевых функций
и функцию (1.23)

Оценки экстремума для липшицевых функций
где
Ее легко найти из равенства
откуда