Метод дихотомии для оптимизации

Метод дихотомии для оптимизации — это численный метод нахождения экстремума x (с заданной точностью ε), минимизирующего (максимизирующего) вогнутую (выпуклую) функцию f(x) на отрезке.

Описание метода

Суть метода дихотомии состоит в разбиении отрезка [a,b] на три отрезка с помощью точек x₁ и x₂ для определения отрезка содержащего минимальное значение функции f(x).

Деление отрезка продолжается до достижения необходимой точности решения ε.

Сначала находим отрезок [a,b] такой, что функция f(x) непрерывна и вогнута на отрезке, то есть f"(x)>0.

Далее применяем алгоритм.

Алгоритм

Входные данные: f(x), a, b, ε, δ.

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

Значение x является минимизирующим решением для функции f(x) с заданной точностью ε.

• Заметим, что для нахождения решения x, максимизирующего выпуклую функцию f(x) на отрезке, алгоритм решения модифицируется в части строки 2, она меняется на строку вида:

• Задачу оптимизации f(x) можно заменить на задачу решения уравнения f'(x)=0, решаемую методом дихотомии.

Другие методы:

• метод золотого сечения;
• метод дихотомии для оптимизации;
• градиентный метод;
• метод множителей Лагранжа.