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

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

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

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

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

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

1. Показать, что $\mathbb {X} =\varnothing$.
2. Показать, что целевая функция $f({\vec {x}})$ не ограничена.
3. Найти ${\vec {x}}^{*}\in \mathbb {X} :\;f({\vec {x}}^{*})=\min _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})$.
4. Если $\nexists {\vec {x}}^{*}$, то найти $\inf _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})$.

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек $x_{0}$ таких, что всюду в некоторой их окрестности $f(x)\geq f(x_{0})$ для минимума и $f(x)\leq f(x_{0})$ для максимума.

Если допустимое множество $\mathbb {X} =\mathbb {R} ^{n}$, то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

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

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

• Локальные методы (задача оптимизации унимодальной целевой функции).
• Глобальные методы (имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.).

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1) детерминированные,

2) случайные,

3) комбинированные.

Некоторые детерминированные методы:

• Задачи оптимизации, в которых целевая функция $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}$, то имеют дело с задачей целочисленного (дискретного) программирования.

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

• аналитические методы;
• численные методы;
• графические методы.

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

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высш. шк., 1986.

1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.

1. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.

1. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

1. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.

1. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

1. Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991.

1. Растригин Л.А. Статистические методы поиска. — М.: 1968.

1. Абакаров А.Ш., Сушков Ю.А. Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004.

Ссылки

Глобальная оптимизация, принятие решений — Программные системы поддержки принятия оптимальных решений. Глобальные алгоримы.

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Оптимизация (математика). Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---