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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Метод деления отрезка пополам)
 
(6 промежуточных версий не показаны.)
Строка 1: Строка 1:
== Постановка задачи ==
== Постановка задачи ==
-
В данной статье рассмотрены некоторые методы поиска экстремума функции одного переменного.
+
В данной статье рассмотрены [[#Симметричные методы| симметричные методы]] поиска экстремума функции одного переменного.
Пусть дана функция <tex>y=f(x)</tex>, необходимо найти минимум этой функции на заданном отрезке <tex>[a, \quad b]</tex> (задача максимума решается аналогично).
Пусть дана функция <tex>y=f(x)</tex>, необходимо найти минимум этой функции на заданном отрезке <tex>[a, \quad b]</tex> (задача максимума решается аналогично).
Строка 22: Строка 22:
'''''Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.'''''
'''''Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.'''''
-
== Симетричные методы ==
+
== Симметричные методы ==
В классе '''симметричных методов''' на каждом шаге выбирается две точки отрезка <tex>x_1</tex> и <tex>x_2</tex>, симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции: <br />
В классе '''симметричных методов''' на каждом шаге выбирается две точки отрезка <tex>x_1</tex> и <tex>x_2</tex>, симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции: <br />
Пусть функция <tex>f(x)</tex> унимодальна на отрезке <tex>[a, \quad b]</tex>, а ее минимум достигается в точке <tex>x^{\ast}</tex>. Для любых точек <tex>x_1</tex> и <tex>x_2</tex> этого отрезка и таких, что <tex>a < x_1 < x_2 < b</tex> верно следующее:
Пусть функция <tex>f(x)</tex> унимодальна на отрезке <tex>[a, \quad b]</tex>, а ее минимум достигается в точке <tex>x^{\ast}</tex>. Для любых точек <tex>x_1</tex> и <tex>x_2</tex> этого отрезка и таких, что <tex>a < x_1 < x_2 < b</tex> верно следующее:
Строка 74: Строка 74:
*Информация о значении функции в точках <tex>x_1</tex> и <tex>x_2</tex> используется только на одном шаге.
*Информация о значении функции в точках <tex>x_1</tex> и <tex>x_2</tex> используется только на одном шаге.
-
====Рекомендации в выборе параметров====
+
----
 +
===Метод золотого сечения===
 +
'''Определение: '''
-
----
+
Говорят, что точка <tex>x</tex> осуществляет золотое сечение отрезка <tex>[a, \quad b]</tex>, если
-
===Метод золотого сечения===
+
<center><tex>\frac{b-a}{b-x}=\frac{b-x}{x-a}=\phi=\frac{1+\sqrt{5} }{2}</tex></center>
-
====Описание метода====
+
-
====Анализ метода====
+
-
====Рекомендации в выборе параметров====
+
 +
В качестве <tex>x_1</tex> и <tex>x_2</tex> выберем точку золотого сечения отрезка и симметричную ей. Если <tex>a<x_1<x_2<b</tex>, то при указанном выборе точек получаем, что <tex>x_1</tex> - точка золотого сечения отрезка <tex>[a, \quad x_2]</tex>, а <tex>x_2</tex> - точка золотого сечения отрезка <tex>[x_1, \quad b]</tex>. Таким образом, на каждом шаге, кроме первого, необходимо вычислять значение только в одной точке, вторая берется из предыдущего шага.
-
----
 
-
===Улучшение метода Золотого сечения===
 
====Описание метода====
====Описание метода====
 +
 +
Параметр на входе: <tex> \epsilon</tex> - достаточно малая положительная константа, погрешность метода.
 +
 +
1. <tex>x_1 = b-\frac{b-a}{\phi}, \quad x_2 = a+\frac{b-a}{\phi}</tex>
 +
 +
2. Повторять:
 +
 +
:3. Если <tex>f(x_1) > f(x_2)</tex>, то <tex>a=x_1, \quad x_1=x_2, \quad x_2=b-(x_1-a)</tex>;
 +
 +
:4. Если <tex>f(x_1) < f(x_2)</tex>, то <tex>b=x_2, \quad x_2=x_1, \quad x_1=a+(b-x_2)</tex>;
 +
 +
5. пока <tex>\frac{b-a}{2} \geq \epsilon</tex>;
 +
 +
6. <tex> \tilde{x}^{\ast}=\frac{a+b}{2}</tex>.
====Анализ метода====
====Анализ метода====
 +
Считаем, что один шаг - это один этап цикла (п. 3-4), <tex>\lambda=\frac{1}{\phi}=\frac{\sqrt{5}-1}{2}</tex>. Тогда, считая длину отрезка на каждом шаге <tex>\Delta_k </tex>, получаем:
 +
 +
:<tex>\Delta_0=a-b</tex>;
 +
 +
:<tex>\Delta_1=\lambda(b-a)=\lambda\Delta_0 </tex>;
 +
 +
:<tex>\Delta_{k+2}=\Delta_k-\Delta_{k+1}</tex>;
 +
 +
Нетрудно проверить, что
 +
 +
{{eqno|1}}
 +
:<tex>\Delta_k=\Delta_k(\lambda)=(-1)^{k-1}(F_k\lambda-F_{k-1})\Delta_0</tex>, где <tex>F_k</tex>-[http://ru.wikipedia.org/wiki/Числа_Фибоначчи числа Фибоначчи].
 +
 +
С другой стороны, выполняется равенство:
 +
 +
{{eqno|2}}
 +
:<tex>\Delta_k(\lambda)=\lambda^k\Delta_0<0,7^k\Delta_0</tex>
 +
 +
Чтобы погрешность вычисления была менее <tex>\epsilon</tex>, должна по крайней мере выполняться оценка на число шагов:
 +
 +
:<tex>k>\frac{1}{\log_{0,7}\frac{2\Delta_0}{\epsilon}}</tex>
 +
 +
Тогда значение будет вычисляться в <tex>N=k+1</tex>точках.
 +
 +
'''Недостаток''':
 +
 +
*Неустойчивость относительно ошибок округления: мы получаем приблизительные значения чисел <tex>\phi</tex> и <tex>\lambda</tex>, дальнейшие вычисления только накапливают ошибки, что может привести к нарушению условия вложенности отрезков <tex>[a_k, \quad b_k]</tex> и расходимости процесса.
 +
 +
Пусть <tex>\lambda</tex> вычисляется с погрешностью <tex>\delta</tex>
 +
 +
Тогда имеем: <tex>\tilde{\lambda}=\lambda+\delta</tex>
 +
 +
Из {{eqref|1}}:
 +
 +
:<tex>\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</tex>.
 +
 +
Подставляем {{eqref|2}}:
 +
 +
{{eqno|3}}
 +
:<tex>\Delta_k(\tilde{\lambda})=\lambda^k\Delta_0+(-1)^{k-1}\delta F_k \Delta_0</tex>.
 +
 +
Известно, что последовательность <tex>\{\Delta_k(\lambda)\}</tex> сходится при <tex>k \to \infty</tex>, В то же время <tex>F_k \to +\infty</tex>, поэтому <tex>|\Delta_k(\tilde{\lambda})| \to +\infty</tex>.
 +
 +
При этом числа Фибоначчи растут со скоростью геометрической прогрессии, знаменателем которой является число <tex>\phi</tex>. Вследствие этого при фиксированной точности "раскачка" процесса происходит довольно быстро.
 +
====Рекомендации в выборе параметров====
====Рекомендации в выборе параметров====
 +
 +
Для сходимости процесса необходимо согласовывать точность <tex>\delta</tex> вычисления величины <tex>\lambda</tex> с заданной точностью <tex>\epsilon</tex> результата.
 +
 +
Из {{eqref|3}} получаем, что при
 +
:<tex>\big(\frac{\sqrt{5}-1}{2}\big)^k\Delta_0 \leq \frac{\epsilon}{2}</tex> и <tex>|\delta| \leq \frac{\epsilon}{2F_k\Delta_0}</tex>,
 +
будет выполняться <tex>\Delta_k(\tilde{\lambda}) \leq \epsilon</tex>
== Числовой пример ==
== Числовой пример ==

Текущая версия

Содержание

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

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

Пусть дана функция 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»
Личные инструменты