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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Анализ метода)
(Анализ метода)
Строка 55: Строка 55:
Считаем, что один шаг - это один этап цикла (п. 2-4).
Считаем, что один шаг - это один этап цикла (п. 2-4).
-
Изначальная длина отрезка составляет <tex>\Delta_0=a-b</tex>. <br />
+
Изначальная длина отрезка составляет <tex>\Delta_0=a-b</tex>.
-
После первого шага: <tex>\Delta_1=\frac{a-b}{2}+(1-\frac{1}{2}) \delta</tex>, <br />
+
 
 +
После первого шага: <tex>\Delta_1=\frac{a-b}{2}+(1-\frac{1}{2}) \delta</tex>,
 +
 
После <tex>k</tex>-го шага: <tex>\Delta_k=\frac{a-b}{2^k}+(1-\frac{1}{2^k}) \delta</tex>.
После <tex>k</tex>-го шага: <tex>\Delta_k=\frac{a-b}{2^k}+(1-\frac{1}{2^k}) \delta</tex>.

Версия 14:00, 18 ноября 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.  \overline {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}-\overline {x^{\ast}}| \quad <  \quad \frac{1}{2}\Delta_k  \quad =  \quad \frac{a-b- \delta}{2^{k+1}}+ \frac{\delta}{2}

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


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

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

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

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


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

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

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

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

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

Заключение

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

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

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

См. также

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