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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (→Метод золотого сечения)
м («Участник:Евгения Одинокова/Метод золотого сечения. Симметричные методы.» переименована в «[[Метод золотого сечения. Симметричные метод)

Версия 19:30, 22 ноября 2008

Содержание

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

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

Пусть дана функция 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.

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

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

Параметры на входе: \delta, \quad \epsilon - достаточно малые положительные константы.

1. Повторять:

2. x_1 = \frac{a + b - \delta}{2}, \quad x_2 = \frac{a + b + \delta}{2};
3. Если f(x_1) > f(x_2), то a=x_1;
4. Если f(x_1) < f(x_2), то b=x_2;

5. пока \frac{b-a}{2} \geq \epsilon;

6. \tilde{x}^{\ast}=\frac{a+b}{2}.

Анализ метода

Считаем, что один шаг - это один этап цикла (п. 2-4).

Изначальная длина отрезка составляет \Delta_0=a-b.

После первого шага: \Delta_1=\frac{a-b}{2}+(1-\frac{1}{2}) \delta,

После k-го шага: \Delta_k=\frac{a-b}{2^k}+(1-\frac{1}{2^k}) \delta.

Если мы останавливаемся на k-м шаге, то погрешность результата составит:

|x^{\ast}-\tilde{x}^{\ast}| \quad < \quad \frac{1}{2}\Delta_k \quad = \quad \frac{a-b- \delta}{2^{k+1}}+ \frac{\delta}{2}

Таким образом, чтобы погрешность вычисления была менее \epsilon, должна выполняться оценка на число шагов:

k>\log_2 (\frac{b - a - \delta}{\epsilon - \frac{\delta}{2} }) - 1

На каждом шаге необходимо вычислить значение функции в 2х точках, соответственно, при k шагах вычисляется N=2k значений.

Недостаток:

  • Информация о значении функции в точках x_1 и x_2 используется только на одном шаге.

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

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

Определение:

Говорят, что точка x осуществляет золотое сечение отрезка [a, \quad b], если

\frac{b-a}{b-x}=\frac{b-x}{x-a}=\phi=\frac{1+\sqrt{5} }{2}


В качестве x_1 и x_2 выберем точку золотого сечения отрезка и симметричную ей. Если a<x_1<x_2<b, то при указанном выборе точек получаем, что x_1 - точка золотого сечения отрезка [a, \quad x_2], а x_2 - точка золотого сечения отрезка [x_1, \quad b]. Таким образом, на каждом шаге, кроме первого, необходимо вычислять значение только в одной точке, вторая берется из предыдущего шага.

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

Параметр на входе: \epsilon - достаточно малая положительная константа, погрешность метода.

1. x_1 = b-\frac{b-a}{\phi}, \quad x_2 = a+\frac{b-a}{\phi}

2. Повторять:

3. Если f(x_1) > f(x_2), то a=x_1, \quad x_1=x_2, \quad x_2=b-(x_1-a);
4. Если f(x_1) < f(x_2), то b=x_2, \quad x_2=x_1, \quad x_1=a+(b-x_2);

5. пока \frac{b-a}{2} \geq \epsilon;

6. \tilde{x}^{\ast}=\frac{a+b}{2}.

Анализ метода

Считаем, что один шаг - это один этап цикла (п. 3-4), \lambda=\frac{1}{\phi}=\frac{\sqrt{5}-1}{2}. Тогда, считая длину отрезка на каждом шаге \Delta_k , получаем:

\Delta_0=a-b;
\Delta_1=\lambda(b-a)=\lambda\Delta_0 ;
\Delta_{k+2}=\Delta_k-\Delta_{k+1};

Нетрудно проверить, что

(1)
\Delta_k=\Delta_k(\lambda)=(-1)^{k-1}(F_k\lambda-F_{k-1})\Delta_0, где F_k-числа Фибоначчи.

С другой стороны, выполняется равенство:

(2)
\Delta_k(\lambda)=\lambda^k\Delta_0<0,7^k\Delta_0

Чтобы погрешность вычисления была менее \epsilon, должна по крайней мере выполняться оценка на число шагов:

k>\frac{1}{\log_{0,7}\frac{2\Delta_0}{\epsilon}}

Тогда значение будет вычисляться в N=k+1точках.

Недостаток:

  • Неустойчивость относительно ошибок округления: мы получаем приблизительные значения чисел \phi и \lambda, дальнейшие вычисления только накапливают ошибки, что может привести к нарушению условия вложенности отрезков [a_k, \quad b_k] и расходимости процесса.

Пусть \lambda вычисляется с погрешностью \delta

Тогда имеем: \tilde{\lambda}=\lambda+\delta

Из (1):

\Delta_k(\tilde{\lambda})=(-1)^{k-1}(F_k(\lambda+\delta)-F_{k-1})\Delta_0= \Delta_k(\lambda)+(-1)^{k-1}\delta F_k \Delta_0.

Подставляем (2):

(3)
\Delta_k(\tilde{\lambda})=\lambda^k\Delta_0+(-1)^{k-1}\delta F_k \Delta_0.

Известно, что последовательность \{\Delta_k(\lambda)\} сходится при k \to \infty, В то же время F_k \to +\infty, поэтому |\Delta_k(\tilde{\lambda})| \to +\infty.

При этом числа Фибоначчи растут со скоростью геометрической прогрессии, знаменателем которой является число \phi. Вследствие этого при фиксированной точности "раскачка" процесса происходит довольно быстро.

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

Для сходимости процесса необходимо согласовывать точность \delta вычисления величины \lambda с заданной точностью \epsilon результата.

Из (3) получаем, что при

\big(\frac{\sqrt{5}-1}{2}\big)^k\Delta_0 \leq \frac{\epsilon}{2} и |\delta| \leq \frac{\epsilon}{2F_k\Delta_0},

будет выполняться \Delta_k(\tilde{\lambda}) \leq \epsilon


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

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

Анализ метода

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

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

Заключение

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

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

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

См. также

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F._%D0%A1%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B»
Личные инструменты