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

Оптимизация (в математике, информатике и исследовании операций) — это задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

Граф параболоида описанного функцией z = f(x, y) = −(x² + y²) + 4. Глобальный максимум от (x, y, z) = (0, 0, 4) обозначен синей точкой

Поиск минимума Нелдера-Мида Функции оптимизации. Симплексные вершины упорядочиваются по их значению, при этом 1 имеет наименьшее (лучшее) значение.

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

Математическое программирование — это область математики, разрабатывающая теорию, численные методы решения многомерных задач с ограничениями.

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

В процессе проектирования ставится обычно задача определения наилучших, в некотором смысле, структуры или значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчётом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией. Задача выбора оптимальной структуры является структурной оптимизацией.

Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов χ, образующих множества Χ, найти такой элемент χ^*, который доставляет минимальное значение f(χ^*) заданной функции f(χ). Для того, чтобы корректно поставить задачу оптимизации, необходимо задать:

1. Допустимое множество — множество [math]\displaystyle{ \mathbb{X}=\{\vec{x}|\;g_i(\vec{x})\leq 0,\;i=1,\ldots,m\} \subset \mathbb{R}^n }[/math];
2. Целевую функцию — отображение [math]\displaystyle{ f:\;\mathbb{X}\to\mathbb{R} }[/math];
3. Критерий поиска (max или min).

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

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

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек [math]\displaystyle{ x_0 }[/math] таких, что всюду в некоторой их окрестности [math]\displaystyle{ f(x)\ge f(x_0) }[/math] для минимума и [math]\displaystyle{ f(x)\le f(x_0) }[/math] для максимума.

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

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

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

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

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

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

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

По виду целевой функции и допустимого множества, задачи оптимизации и методы их решения можно разделить на следующие классы:

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

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

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

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

• аналитические методы (например, метод множителей Лагранжа и условия Каруша — Куна — Таккера);
• численные методы;
• графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

• задачи дискретного программирования (или комбинаторной оптимизации) — если X конечно или счётно;
• задачи целочисленного программирования — если X является подмножеством множества целых чисел;
• задачи нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.
• Если же все ограничения и целевая функция содержат лишь линейные функции, то это — задача линейного программирования.

Кроме того, разделами математического программирования являются параметрическое программирование, динамическое программирование и стохастическое программирование.

Математическое программирование используется при решении оптимизационных задач исследования операций.

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

• Определение границ системы оптимизации
  • Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
• Выбор управляемых переменных
  • «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
• Определение ограничений на управляемые переменные
  • … (равенства и/или неравенства)
• Выбор числового критерия оптимизации (например, показателя эффективности)
  • Создаём целевую функцию

История

Задачи линейного программирования были первыми подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Джордж Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

Присутствие в названии дисциплины термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин «линейное программирование» был предложен Дж. Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях.

Поэтому наименование «математическое программирование» связано с тем, что целью решения задач является выбор оптимальной программы действий.

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 1930-м годам. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман — математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Л. В. Канторович — советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 году венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

Л. В. Канторович и М. К. Гавурин в 1949 году разработали метод потенциалов, который применяется при решении транспортных задач. В последующих работах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем.

Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 году Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Куна, А. Таккера, Гасса (Saul I. Gass), Чарнеса (A. Charnes), Била (E. M. Beale) и др.

Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 году была опубликована работа Г. Куна и А. Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области.

Начиная с 1955 года опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина и Р. Дорфмана, Франка (M. Frank) и Ф. Вулфа, Г. Марковица и др.). В работах Денниса (J. B. Dennis), Розена (J. B. Rosen) и Зонтендейка (G. Zontendijk) разработаны градиентные методы решения задач нелинейного программирования.

В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.

См. также

• Многокритериальная оптимизация
• Математический анализ
• Скалярное ранжирование

Литература

• Абакаров А. Ш., Сушков Ю. А. Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004.
• Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высшая школа, 1986.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Гирсанов И. В. Лекции по математической теории экстремальных задач. — М.; Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003. — 118 с. — ISBN 5-93972-272-5.
• Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991.
• Карманов В. Г. Математическое программирование. — Изд-во физ.-мат. литературы, 2004.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
• Лотов А. В., Поспелова И. И. Конспект лекций по теории и методам многокритериальной оптимизации. Архивная копия от 21 января 2022 на Wayback Machine Учеб. пос. М., 2005. 127 с.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
• Плотников А. Д. Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4.
• Растригин Л. А. Статистические методы поиска. — М., 1968.
• Сергеев Я. Д., Квасов Д. Е. Диагональные методы глобальной оптимизации Архивная копия от 26 октября 2017 на Wayback Machine. — М.: ФИЗМАТЛИТ, 2008. 341с.
• Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. — 8 изд. — М.: Вильямс, 2007. — С. 912. — ISBN 0-13-032374-8.
• Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981. — 560 с.
• Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. — 2-е изд., перераб. и доп.. — М.: Издательство «Наука», 1967.
• Минаев Ю. Н. Стабильность экономико-математических моделей оптимизации. — М.: Статистика, 1980.
• Моисеев Н. Н. Численные методы в теории оптимальных систем. — М.: Наука, 1971. — 424 с.
• Моисеев Н. Н. Элементы теории оптимальных систем. — М.: Наука, 1975. — 528 с.
• Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. — М.: Наука, 1978. — 352 с.

• Дегтярёв Ю. И. Методы оптимизации. — М.: Советское радио, 1980. — 272 с.
• Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. — М.: Мир, 1986. — 400 с.
• Романовский И. В. Алгоритмы решения экстремальных задач. — М.: Наука, 1977. — 352 с. — 16 000 экз.
• Умнов А.Е., Умнов Е.А. Параметрические задачи в математическом программировании Архивная копия от 9 июля 2021 на Wayback Machine (pdf)
• Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации. Архивная копия от 18 января 2021 на Wayback Machine Курс лекций. Новосибирск, 2007.
• Хохлюк В. И. Методы дискретной оптимизации. Архивная копия от 18 января 2021 на Wayback Machine Учебное пособие. НГУ, 2013. 154 с.

Ссылки

• Поляк Б. П. История математического программирования в СССР: анализ феномена // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения». — 2008. — Т. 1. — С. 2—20.