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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: ==Введение== ==Постановка задачи== ==Метод решения==)
Строка 1: Строка 1:
-
==Введение==
+
==Постановка задачи оптимизации==
-
==Постановка задачи==
+
Пусть задано множество <tex> X \subset R^n </tex> и на этом множестве определена ''целевая функция'' (''objective function'') <tex>f : R^n \mapsto R</tex>. Задача оптимизации состоит в нахождении на множестве <tex>X</tex> точной верхней или точной нижней грани ''целевой функции''.
-
==Метод решения==
+
Множество точек, на которых достигается нижняя грань целевой функции обозначается <tex>X_* </tex>. <br/>
 +
<tex>X_* = \{x \in X| f(x) = inf \limits_{x \in X} f(x) \} </tex>
 +
<br/>
 +
Если <tex> X = R^n </tex>, то задача оптимизации называется ''безусловной'' (''unconstrained'').
 +
Если <tex> X \neq R^n </tex>, то задача оптимизации называется ''условной'' (''constrained'').
 +
 
 +
==Метод сопряжённых направлений==
 +
''Метод сопряжённых направлений'' (''conjugate direction method'') первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения безусловных задач оптимизации в <tex>R^n</tex>
 +
==Минимизация квадратичного функционала==
 +
Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации:
 +
<tex>f(x) = \frac{1}{2}<Ax, x> - <b, x> \to inf, \quad x \in R^n</tex> <br/>
 +
<tex>A</tex> - симметричная положительно определённая матрица размера <tex>n \times n</tex>.
 +
Такая задача оптимизации называется квадратичной. Функция <tex>f</tex> достигает своей нижней грани в единственной точке <tex>x_*</tex>, определяемой уравнением <tex> Ax_* = b</tex> . Таким образом, данная задача оптимизации сводится к решению линейной системы
 +
<tex> Ax = b</tex>
 +
=== Общий случай ===
 +
== Литература ==
 +
Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002
 +
Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999

Версия 17:02, 17 ноября 2008

Содержание

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

Пусть задано множество 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

Общий случай

Литература

Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002 Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Slimper/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты