Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол
Материал из MachineLearning.
Содержание |
Постановка задачи одномерной оптимизации
Задача одномерной оптимизации определяется следующим образом:
- Допустимое множество — множество <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>, то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.