Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
== Постановка задачи одномерной оптимизации ==
== Постановка задачи одномерной оптимизации ==
Задача одномерной оптимизации определяется следующим образом:
Задача одномерной оптимизации определяется следующим образом:
-
# ''Допустимое множество'' — множество <teh>\mathbb{X}=\{\vec{x}:\;g_i(\vec{x})\leq 0,\;i=1,\ldots,n_1;\;g_j(\vec{x})=0,\;j=1,\ldots,n_2;\;g_k(\vec{x})\geq 0,\;k=1,\dots,n_3;\;m=n_1+n_2+n_3 \} \subset \mathbb{R}^n(\mathbb{C}^n)</teh>;
+
# ''Допустимое множество'' — множество <tex>\mathbb{X}=\{\vec{x}:\;g_i(\vec{x})\leq 0,\;i=1,\ldots,n_1;\;g_j(\vec{x})=0,\;j=1,\ldots,n_2;\;g_k(\vec{x})\geq 0,\;k=1,\dots,n_3;\;m=n_1+n_2+n_3 \} \subset \mathbb{R}^n(\mathbb{C}^n)</tex>;
-
# ''Целевую функцию'' — отображение <teh>f:\;\mathbb{X}\to\mathbb{R}</teh>;
+
# ''Целевую функцию'' — отображение <tex>f:\;\mathbb{X}\to\mathbb{R}</tex>;
# ''Критерий поиска'' (max или min).
# ''Критерий поиска'' (max или min).
-
Тогда решить задачу <teh>f(x)\to \min_{\vec{x}\in\mathrm{X}}</teh> означает одно из:
+
Тогда решить задачу <tex>f(x)\to \min_{\vec{x}\in\mathrm{X}}</tex> означает одно из:
-
# Показать, что <teh>\mathbb{X}=\varnothing</teh>.
+
# Показать, что <tex>\mathbb{X}=\varnothing</tex>.
-
# Показать, что целевая функция <teh>f(\vec{x})</teh> не ограничена.
+
# Показать, что целевая функция <tex>f(\vec{x})</tex> не ограничена.
-
# Найти <teh>\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})</teh>.
+
# Найти <tex>\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})</tex>.
-
# Если <teh>\nexists \vec{x}^* </teh>, то найти <teh>\inf_{\vec{x}\in\mathbb{X}}f(\vec{x})</teh>.
+
# Если <tex>\nexists \vec{x}^* </tex>, то найти <tex>\inf_{\vec{x}\in\mathbb{X}}f(\vec{x})</tex>.
-
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <teh>x_0</teh> таких, что всюду в некоторой их окрестности <teh>f(x)\ge f(x_0)</teh> для минимума и <teh>f(x)\le f(x_0)</teh> для максимума.
+
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <tex>x_0</tex> таких, что всюду в некоторой их окрестности <tex>f(x)\ge f(x_0)</tex> для минимума и <tex>f(x)\le f(x_0)</tex> для максимума.
-
Если допустимое множество <teh>\mathbb{X}=\mathbb{R}</teh>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''.
+
Если допустимое множество <tex>\mathbb{X}=\mathbb{R}</tex>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''.
== Метод Ньютона ==
== Метод Ньютона ==
== Метод Парабол ==
== Метод Парабол ==

Версия 20:41, 16 ноября 2008

Содержание

Постановка задачи одномерной оптимизации

Задача одномерной оптимизации определяется следующим образом:

  1. Допустимое множество — множество \mathbb{X}=\{\vec{x}:\;g_i(\vec{x})\leq 0,\;i=1,\ldots,n_1;\;g_j(\vec{x})=0,\;j=1,\ldots,n_2;\;g_k(\vec{x})\geq 0,\;k=1,\dots,n_3;\;m=n_1+n_2+n_3 \} \subset \mathbb{R}^n(\mathbb{C}^n);
  2. Целевую функцию — отображение f:\;\mathbb{X}\to\mathbb{R};
  3. Критерий поиска (max или min).

Тогда решить задачу f(x)\to \min_{\vec{x}\in\mathrm{X}} означает одно из:

  1. Показать, что \mathbb{X}=\varnothing.
  2. Показать, что целевая функция f(\vec{x}) не ограничена.
  3. Найти \vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x}).
  4. Если \nexists \vec{x}^* , то найти \inf_{\vec{x}\in\mathbb{X}}f(\vec{x}).

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x_0 таких, что всюду в некоторой их окрестности f(x)\ge f(x_0) для минимума и f(x)\le f(x_0) для максимума.

Если допустимое множество \mathbb{X}=\mathbb{R}, то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Метод Ньютона

Метод Парабол

Совмещение метода Ньютона и Парабол

Численный пример

Литература

Смотри также

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