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

Материал из Википедии — свободной энциклопедии

Задачей оптимизации в математике называется задача о нахождении экстремума (минимума или максимума) вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.

Содержание 1 Постановка задачи оптимизации 2 Классификация методов оптимизации 3 Литература 4 Ссылки

[править] Постановка задачи оптимизации

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

1. Допустимое множество — множество ;
2. Целевую функцию — отображение ;
3. Критерий поиска (max или min).

Тогда решить задачу означает одно из:

1. Показать, что .
2. Показать, что целевая функция не ограничена.
3. Найти .
4. Если , то найти .

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x₀ таких, что всюду в некоторой их окрестности для минимума и для максимума.

Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

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

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

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

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

1. детерминированные;
2. случайные;
3. комбинированные.

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

• Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования.
• В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
  • если и  — выпуклые функции, то такую задачу называют задачей выпуклого программирования;
  • если , то имеют дело с задачей целочисленного (дискретного) программирования.

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

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

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

[править] Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высшая школа, 1986.
2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
7. Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991.
8. Растригин Л.А. Статистические методы поиска. — М.: 1968.
9. Абакаров А.Ш., Сушков Ю.А. Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004.

[править] Ссылки

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

Общие методы (методы нелинейного программирования):
Методы одномерной оптимизации:	Метод золотого сечения (Метод чисел Фибоначчи) • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод троичного поиска
Методы многомерной оптимизации:	Прямые методы: (требуют только значения функции в точках приближений) Метод Гаусса • Метод деформируемого многогранника (метод Нелдера — Мида, симплексный метод) • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса Методы первого порядка: (помимо значений функции требуют значения частных производных) Метод наискорейшего спуска • Метод покоординатного спуска • Метод сопряжённых градиентов Методы второго порядка: (требуют значения первой и второй частных производных): Метод Ньютона • Метод Ньютона-Рафсона Методы линейного программирования: Метод эллипсоидов • Симплекс-метод • Метод потенциалов