- Задача оптимизации
-
Задачей оптимизации в математике называется задача о нахождении экстремума (минимума или максимума) вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие и заданные набором равенств и неравенств.
Содержание
Постановка задачи оптимизации
Для того, чтобы корректно поставить задачу оптимизации необходимо задать:
- Допустимое множество — множество ;
- Целевую функцию — отображение ;
- Критерий поиска (max или min).
Тогда решить задачу означает одно из:
- Показать, что .
- Показать, что целевая функция не ограничена.
- Найти .
- Если , то найти .
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x0 таких, что всюду в некоторой их окрестности для минимума и для максимума.
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.
Классификация методов оптимизации
Методы, по средством которых решают задачи оптимизации, подразделяются на виды, соответствующие задачам, к которым они применяются:
- Локальные методы (задача оптимизации унимодальной целевой функции).
- Глобальные методы (имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.).
Существующие в настоящее время методы поиска можно разбить на три большие группы:
- детерминированные;
- случайные;
- комбинированные.
Некоторые детерминированные методы:
- Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования.
- В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
- если и — выпуклые функции, то такую задачу называют задачей выпуклого программирования;
- если , то имеют дело с задачей целочисленного (дискретного) программирования.
Помимо того, оптимизационные методы делятся на следующие группы:
- аналитические методы;
- численные методы;
- графические методы.
Также они разделяются по критерию размерности допустимого множества на методы одномерной оптимизации и методы многомерной оптимизации.
Литература
- Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высшая школа, 1986.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
- Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991.
- Растригин Л.А. Статистические методы поиска. — М.: 1968.
- Абакаров А.Ш., Сушков Ю.А. Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004.
Ссылки
- MDOP — Поиск глобального оптимума для задач оптимального проектирования систем или определения оптимальных законов управления.
- Глобальная оптимизация, принятие решений — Программные системы поддержки принятия оптимальных решений. Глобальные алгоримы.
Общие методы (методы нелинейного программирования): Методы одномерной оптимизации: Метод золотого сечения (Метод чисел Фибоначчи) • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод троичного поиска Методы многомерной оптимизации: Прямые методы:
(требуют только значения функции в точках приближений)
Метод Гаусса • Метод деформируемого многогранника (метод Нелдера — Мида, симплексный метод) • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса
Методы первого порядка:
(помимо значений функции требуют значения частных производных)
Метод наискорейшего спуска • Метод покоординатного спуска • Метод сопряжённых градиентов
Методы второго порядка:
(требуют значения первой и второй частных производных):
Метод Ньютона • Метод Ньютона-РафсонаМетоды линейного программирования:
Метод эллипсоидов • Симплекс-метод • Метод потенциалов
Wikimedia Foundation. 2010.