Russian
English
Теория и методы математического программирования и распознавания
образов, исследование операций, математическая экономика
Историческая справка
Математическое программирование (МП) является в настоящее время одним из активно развивающихся разделов прикладной математики. Объектом изучения в этой дисциплине служит задача оптимизации некоторого показателя качества принимаемого решения при ограничениях на это решение в виде функциональных неравенств и (или) уравнений. Подобные задачи возникают как в самой математике (аппроксимация, решение систем уравнений, регрессия, оптимальное управление системами, распознавание образов (РО), теория игр), так и в многочисленных приложениях по оптимизации технико-экономических систем, транспортных и информационных сетей, по управлению производством и другими сферами человеческой деятельности, в робототехнике и т.п.
У истоков уральской школы по МП стоял выдающийся математик С.Н.Черников (1912-1987), известный своими классическими работами по теории групп и теории линейных неравенств. В 1961 году в Свердловском отделении Математического института им. В.А.Стеклова (ныне Институт математики и механики УрО РАН им. Н.Н.Красовского) при отделе алгебры, возглавляемом профессором С.Н.Черниковым, была создана лаборатория линейного программирования. Ее возглавил ученик С.Н.Черникова молодой кандидат наук И.И.Еремин. После успешной защиты докторской диссертации в 1967 году на базе данной лаборатории И.И.Ереминым был организован отдел МП, ставший в дальнейшем ядром научной школы по оптимизации.
Уральскую школу отличают и предмет, и методология исследований. В первую очередь, это интерес к глубинным вопросам теории классического МП таким, как двойственность, устойчивость, регуляризация, нестационарность, несобственность. Далее, это проблема построения общих методов решения линейных и выпуклых задач оптимизации (фейеровского типа, штрафных функций, модифицированных функций Лагранжа), исследование дискретных оптимизационных задач, построение точных и приближенных алгоритмов анализа данных с гарантированными оценками точности и трудоемкости.
Сразу следует заметить, что ряд этих вопросов: теория двойственности для определенных классов задач МП (многокритериальных, противоречивых, дизъюнктивных), нестационарные задачи МП, несобственные (в частности, противоречивые) задачи МП, некоторые виды регуляризации задач МП, комитетные конструкции в задачах РО, были инициированы работами представителей данной школы и получили широкую известность и признание как в нашей стране, так и за рубежом.
Специфику методологии в области теории составляет прежде всего алгебраический подход к доказательству математических результатов, опирающийся преимущественно на теорию линейных неравенств. В области алгоритмического обеспечения основное внимание уделяется оценочному подходу, связанному с получением оценок скорости сходимости методов, точности приближений, вычислительной сложности.
Отметим ряд результатов, полученных в рамках данной школы. Большое значение имеют исследования по методам штрафных функций. В 1966 году И.И.Ереминпредложил метод точных штрафных функций, позволяющий в принципе свести решение исходной задачи на условный экстремум к однократной минимизации без ограничений подходящим образом выбранной вспомогательной функции. Результаты по методу, основанному на предложенной точной штрафной функции, именуемой в мировой специальной литературе “функцией Еремина-Зангвилла”, в значительной мере опередили зарубежные исследования в этой области. На самом деле был открыт конструктивный класс точных штрафных функций для задач линейного и выпуклого программирования (Еремин-Зангвилл) и дана исчерпывающая идентификация оптимальных штрафных констант (И.И.Еремин), совпадающих с объективно-обусловленными оценками Канторовича. Был развит оценочный подход в методе штрафных функций и получены соответствующие оценки уклонений (см. И.И.Еремин, Н.Н.Астафьев. “Введение в теорию линейного и выпуклого программирования”. –М.: Наука, 1976).
Был исследован широкий класс методов фейеровского типа для решения систем выпуклых неравенств и задач выпуклого программирования. Разработана методология нестационарных процессов МП как средства моделирования эволюционирующих сложных систем (экономических, биологических и др.). Первым итогом этого нового направления стала монография И.И.Еремина, Вл.Д.Мазурова “Нестационарные процессы математического программирования” (М.: Наука, 1979).
Базовой идеей теории МП является двойственность, позволяющая осуществлять конструктивный анализ моделей оптимизации. В работах И.И.Еремина и его учеников построена каноническая теория двойственности для несобственных (противоречивых, не имеющих решения в обычном смысле) задач МП, а также многокритериальных, дизъюнктивных задач, разработаны методы оптимальной коррекции несобственных задач. Решение этих вопросов можно найти в монографиях: И.И.Еремин, Вл.Д.Мазуров, Н.Н.Астафьев “Несобственные задачи линейного и выпуклого программирования” (М.: Наука, 1983), I.I.Eremin “Theory of Linear Optimization” (Inverse and Ill-Posed Problems, VSP, Utrecht, Boston, Köln, Tokyo, 2002).
Теория линейных неравенств, развитая С.Н.Черниковым, послужила фундаментом для развития исследований по оптимизационным задачам РО — дисциплины, актуальной своими богатыми приложениями (разнообразные задачи классификации, диагностика технико-экономических систем, медицинская диагностика и т.д.). В работах Вл.Д.Мазурова и его учеников системы линейных неравенств и комитеты большинства применялись для решения задач дискриминантного анализа, таксономии и выбора информативных признаков в условиях неформализованности, противоречивости и нестационарности постановок. Теория комитетов определяет оригинальную методику решения задачи обучения РО, которая тесно связана как с работами по алгебраическому подходу в РО (школа акад. Ю.И.Журавлева), так и с работами по исследованию несобственных задач оптимизации в рамках нестационарных процессов в МП и РО. Соответствующие результаты нашли отражение в монографии Вл.Д.Мазурова “Метод комитетов в задачах оптимизации и классификации” // М.: Наука, 1990.
В последние десятилетия были получены оценки числа членов минимального комитета, обоснованы соотношения двойственности для различных задач РО, предложена комбинаторная классификация минимальных комитетов несовместных систем ограничений на основе изоморфизма подходящих гиперграфов, доказана NP-полнота задачи о минимальном комитете (см., напр., Vl.D.Mazurov, M.Yu.Khachai, A.I.Rybin. “Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction” // Proceedings of Steklov Inst. of Math. Suppl. 1, 2002). Исследована вычислительная сложность задачи о минимальном комитете, возникающая при в рамках подхода Вапника и Червоненкиса к структурной минимизации риска (М.Ю.Хачай. Cм. напр., Khachay, M. “On the computational complexity of the minimum committee problem” // J. of Math Modeling and Algorithms. 2007. Vol. 6. P.547–561). Предложены подходы к повышению гарантированных оценок точности полиномиальных приближенных алгоритмов решения труднорешаемых комбинаторных задач, основанный на результатах современной теории статистического обучения (М.Ю.Хачай, М.И.Поберий. См., напр., Khachay, M., Poberiy, M. “Complexity and approximability of committee polyhedral separability of sets in general position” // Informatica. 2009. Vol. 20. P.217-234; Khachay, M. “Committee polyhedral separability: complexity and polynomial approximation” // Machine Learning. 2015. Vol. 101, issue 1. P. 231-251). Проведен алгоритмический анализ серии обобщений известной Задачи коммивояжера, имеющих практические приложения в исследовании операций и анализе данных. В частности, показано, что Задача о цикловом покрытии заданного размера для взвешенного графа (Задача о нескольких коммивояжерах) наследует основные сложностные и аппроксимативные свойства Задачи коммивояжера: задача NP-трудна в сильном смысле и неаппроксимируема в общей постановке, в метрической и евклидовых постановках задача, сохраняя труднорешаемость, обладает приближенными полиномиальными алгоритмами с фиксированной точностью и полиномиальными приближенными схемами, соответственно (М.Ю.Хачай, Е.Д.Незнахина. См. напр., Khachay, M. “Approximability of the minimum-weight k-size cycle cover problem” / M. Khachay, K. Neznakhina // J. Global Optimization. 2016. Vol.66, No.1. P.65-82.)
Для данной школы характерно устойчивое внимание к созданию программного обеспечения для задач МП и РО и к решению прикладных задач. В числе созданных пакетов прикладных программ выделяются ППП ОПТИМА, ДЕЛЬТА-ПЛАН, ЛАМБДА, реализующие методы линейного, квадратичного и нелинейного программирования для задач большой размерности, ППП КВАЗАР и КВАЗАР-плюс для решения задач РО (последний пакет имеет вариант для работы через Интернет). Полигоном проверки эффективности программных средств выступали такие задачи как объемно-календарное планирование производства Уральского завода тяжелого машиностроения, задачи из области энергетики и черной металлургии, медицинские задачи, задачи управления сложными техническими системами.
Научная школа академика И.И.Еремина совместно с Ассоциацией математического программирования с 1972 года регулярно проводит всероссийскую конференцию “Математическое программирование и приложения”, входящую в число важнейших научных мероприятий в области теории и методов оптимизации на территории РФ.
С 2012 года в Екатеринбурге проводится ежегодная международная молодежная конференция «Анализ изображений, сетей и текстов», избранные труды которой публикуются издательством Springer Verlag в рамках серии Communications in Computer and Information Sciences.
- Сектор 1
- Сектор 2
Партнёрство