Оптимизация (математика)

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

У этого термина существуют и другие значения, см. Оптимизация.

Задачей оптимизации в математике является нахождение экстремума (минимума или максимума) действительной функции в некоторой области. Как правило, рассматриваются области принадлежащие $\mathbb{R}^n$ заданные набором равенств и неравенств.

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

Для того, чтобы корректно поставить задачу оптимизации необходимо задать:

Допустимое множество — множество $\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)$ ;
Целевую функцию — отображение $f:\;\mathbb{X}\to\mathbb{R}$ ;
Критерий поиска (max или min).

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

Показать, что $\mathbb{X}=\varnothing$ .
Показать, что целевая функция $f(\vec{x})$ не ограничена.
Найти $\vec{x}^*\in\mathbb{X}:\;f(\vec{x}^*)=\min_{\vec{x}\in\mathbb{X}}f(\vec{x})$ .
Если $\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}^n$ , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Классификация методов оптимизации

Методы, по средством которых решают задачи оптимизации, подразделяются на виды, соответствующие задачам, к которым они применяются:

Задачи оптимизации, в которых целевая функция $f(\vec{x})$ и ограничения $g_i(\vec{x}),\; i=1,\ldots,m$ являются линейными функциями, разрешаются так называемыми методами линейного программирования.
В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
- если $f(\vec{x})$ и $g_i(\vec{x}),\;i=1,\ldots,m$ — выпуклые функции, то такую задачу называют задачей выпуклого программирования;
- если $\mathbb{X}\subset \mathbb{Z}$ , то имеют дело с задачей целочисленного (дискретного) программирования.

Помимо того, оптимизационные методы делятся на следующие группы:

Либо являются комбинированными и включают в себя элементы из нескольких подгрупп.

Также они разделяются по критерию размерности допустимого множества на методы одномерной оптимизации и методы многомерной оптимизации.

Литература

Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высш. шк., 1986.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.