Метод золотого сечения. Симметричные методы

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Постановка задачи

В данной статье рассмотрены некоторые методы поиска экстремума функции одного переменного.

Пусть дана функция y=f(x), необходимо найти минимум этой функции на заданном отрезке [a, \quad b] (задача максимума решается аналогично). Предполагается, что производная функции либо не существует, либо сложно вычислима, что не позволяет свести задачу к поиску корней производной f'(x)=0.

Методы заключаются в построении последовательности отрезков [a_n, \quad b_n], стаягивающихся к точке x^{\ast} = argmin \{ f(x):\: \quad x \quad \in \quad [a,\quad b] \}.

Проанализируем симметричные методы поиска и оценим их эффективность и точность.

Требования к функции

Рассматривая все функции, пусть даже непрерывные, можно построить такой пример, что x^{\ast} \quad \notin \quad [a_n, \quad b_n], хотя x^{\ast} \quad \in \quad [a_0, \quad b_0].

Гарантировать применимость рассматриваемых методов можно только для унимодальных функций.

Определение : Функция f(x) называется унимодальной на отрезке [a, \quad b], если ∃! точка минимума x^{\ast} на этом отрезке такая, что для любых точек x_1, \quad x_2 этого отрезка

x^{\ast} \leq x_1 \leq x_2 \quad \Rightarrow \quad f(x^{\ast}) \leq f(x_1) \leq f(x_2),
x^{\ast} \geq x1 \geq x_2 \quad \Rightarrow \quad f(x^{\ast}) \leq f(x1) \leq f(x2)
.

Другими словами унимодальная функция монотонна на обе стороны от точки минимума x^{\ast}. Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными...

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

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

В классе симметричных методов на каждом шаге выбирается две точки отрезка x_1 и x_2, симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции:
Пусть функция f(x) унимодальна на отрезке [a, \quad b], а ее минимум достигается в точке x^{\ast}. Для любых точек x_1 и x_2 этого отрезка и таких, что a < x_1 < x_2 < b верно следующее:

  1. если f(x_1) > f(x_2), то точка минимума x^{\ast} \quad \in \quad [x_1, \quad b),
  2. если f(x_1) < f(x_2), то точка минимума x^{\ast} \quad \in \quad (a, \quad x2].


Исходя из определения методов, видно, что всякий симметричный метод полностью определяется заданием отрезка [a, \quad b] и правилом выбора первой точки. Тогда другая точка x_2 находится по правилу общему для всех симметричных методов: x_2=a+b-x_{1}.

Соответственно, методы различаются способом выбора симметричных точек x_1 и x_2.

Метод деления отрезка пополам

Метод золотого сечения

Анализ методов и оценка ошибок

Улучшение метода Золотого сечения

Числовой пример

Рекомендации в выборе параметров

Заключение

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

  • Карманов В.Г. Математическое программирование: Учебное пособие. - М.:ФИЗМАТЛИТ, 2004
  • Горячев Л.В. Одномерная минимизация. Методические указания к самостоятельной работе студентов по курсу “Методы оптимизации” - кафедра процессов управления ДВГУ, 2003

Внешние ссылки

См. также

Личные инструменты