Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол
Материал из 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>; |
- | ==Совмещение метода Ньютона и Парабол== | + | # ''Целевую функцию'' — отображение <teh>f:\;\mathbb{X}\to\mathbb{R}</teh>; |
- | ==Численный пример== | + | # ''Критерий поиска'' (max или min). |
- | ==Литература== | + | |
- | ==Смотри также== | + | Тогда решить задачу <teh>f(x)\to \min_{\vec{x}\in\mathrm{X}}</teh> означает одно из: |
+ | # Показать, что <teh>\mathbb{X}=\varnothing</teh>. | ||
+ | # Показать, что целевая функция <teh>f(\vec{x})</teh> не ограничена. | ||
+ | # Найти <teh>\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})</teh>. | ||
+ | # Если <teh>\nexists \vec{x}^* </teh>, то найти <teh>\inf_{\vec{x}\in\mathbb{X}}f(\vec{x})</teh>. | ||
+ | |||
+ | Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <teh>x_0</teh> таких, что всюду в некоторой их окрестности <teh>f(x)\ge f(x_0)</teh> для минимума и <teh>f(x)\le f(x_0)</teh> для максимума. | ||
+ | |||
+ | Если допустимое множество <teh>\mathbb{X}=\mathbb{R}</teh>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''. | ||
+ | == Метод Ньютона == | ||
+ | == Метод Парабол == | ||
+ | == Совмещение метода Ньютона и Парабол == | ||
+ | == Численный пример == | ||
+ | == Литература == | ||
+ | == Смотри также == | ||
* [[Практикум ММП ВМК, 4й курс, осень 2008]] | * [[Практикум ММП ВМК, 4й курс, осень 2008]] | ||
[[Категория:Учебные задачи]] | [[Категория:Учебные задачи]] |
Версия 20:39, 16 ноября 2008
Содержание |
Постановка задачи одномерной оптимизации
Задача одномерной оптимизации определяется следующим образом:
- Допустимое множество — множество <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>;
- Целевую функцию — отображение <teh>f:\;\mathbb{X}\to\mathbb{R}</teh>;
- Критерий поиска (max или min).
Тогда решить задачу <teh>f(x)\to \min_{\vec{x}\in\mathrm{X}}</teh> означает одно из:
- Показать, что <teh>\mathbb{X}=\varnothing</teh>.
- Показать, что целевая функция <teh>f(\vec{x})</teh> не ограничена.
- Найти <teh>\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})</teh>.
- Если <teh>\nexists \vec{x}^* </teh>, то найти <teh>\inf_{\vec{x}\in\mathbb{X}}f(\vec{x})</teh>.
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <teh>x_0</teh> таких, что всюду в некоторой их окрестности <teh>f(x)\ge f(x_0)</teh> для минимума и <teh>f(x)\le f(x_0)</teh> для максимума.
Если допустимое множество <teh>\mathbb{X}=\mathbb{R}</teh>, то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.