Участник:Slimper/Песочница

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

Версия от 17:02, 17 ноября 2008; Slimper (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Постановка задачи оптимизации
2 Метод сопряжённых направлений
3 Минимизация квадратичного функционала
- 3.1 Общий случай
4 Литература

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

Пусть задано множество $X \subset R^n$ и на этом множестве определена целевая функция (objective function) $f : R^n \mapsto R$ . Задача оптимизации состоит в нахождении на множестве $X$ точной верхней или точной нижней грани целевой функции. Множество точек, на которых достигается нижняя грань целевой функции обозначается $X_*$ .
$X_* = \{x \in X| f(x) = inf \limits_{x \in X} f(x) \}$
Если $X = R^n$ , то задача оптимизации называется безусловной (unconstrained). Если $X \neq R^n$ , то задача оптимизации называется условной (constrained).

Метод сопряжённых направлений

Метод сопряжённых направлений (conjugate direction method) первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения безусловных задач оптимизации в $R^n$

Минимизация квадратичного функционала

Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации: $f(x) = \frac{1}{2}<Ax, x> - <b, x> \to inf, \quad x \in R^n$
$A$ - симметричная положительно определённая матрица размера $n \times n$ . Такая задача оптимизации называется квадратичной. Функция $f$ достигает своей нижней грани в единственной точке $x_*$ , определяемой уравнением $Ax_* = b$ . Таким образом, данная задача оптимизации сводится к решению линейной системы $Ax = b$