Интервью с директором ВЦ РАН академиком Ю.Г. Евтушенко "Оптимизация – выбор наилучшего"

Представляем Вашему вниманию интервью с академиком РАН , известным специалистом в области вычислительной математики и оптимизации, российским ученым-математиком, доктором физико-математических наук, профессором, иностранным членом Национальной академии наук Украины, директором Вычислительного Центра имени А.А. Дородницына Российской Академии Наук, лауреатом премии Совета Министров СССР, почетным редактором-учредителем журнала «Optimization Methods and Software», Юрием Гавриловичем Евтушенко.

Мы обратились к известному эксперту в области оптимизации, Юрию Гавриловичу Евтушенко, и попросили его ответить на наши вопросы.

В беседе принимают участие научный директор StatSoft Владимир Павлович Боровиков, специалист StatSoft Светлана Валерьевна Соловьева.

В.П.: Юрий Гаврилович, добрый день!

Спасибо, что нашли время для встречи и беседы с нами.

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

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

Тема очень обширная и многогранная, сфер применения очень много...

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

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

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

Ю.Г.: Да, это действительно так… Вопросы оптимизации возникали на протяжении всей истории человечества, вначале человек учился что-то делать, потом спрашивал себя, как это сделать наилучшим образом. Слово «optimum» от латинского означает «наилучшее»…

Российский академик Леонард Эйлер писал: «В мире не происходит ничего, в чем не был бы виден смысл какого-нибудь максимума или минимума».

Великие греки, открывшие нам математический взгляд на мир, впервые сформулировали оптимизационные задачи (задачи Евклида, Архимеда, Аполлония, Дидоны и многие другие).

Древнейшей из известных экстремальных задач является, пожалуй, классическая изопериметрическая задача. Трудно сказать, когда впервые была высказана мысль о наибольшей «вместимости» окружности и сферы среди замкнутых кривых одной и той же длины, или поверхностей одной и той же площади. Один из последних учеников афинской школы платоников Симплиций (VI в. н. э.), составивший незадолго до окончательного краха античной цивилизации обширный комментарий к трудам Аристотеля (IV в. до н. э.), пишет: «Доказано до Аристотеля, ибо он пользуется этим, как известным, а затем более полно – Архимедом и Зенодором, что среди изопериметрических фигур наиболее вместимым является круг, а среди изопифанных – шар».

В этих словах обозначена постановка следующих экстремальных задач: среди плоских замкнутых кривых, имеющих заданную длину, найти кривую, охватывающую наибольшую площадь, и среди пространственных замкнутых поверхностей, имеющих заданную площадь, найти поверхность, охватывающую наибольший объем. Для философа-платоника такая постановка задачи естественна и связана с поисками идеальных форм. Недаром круг и шар были в древности символами геометрического совершенства.

Более прозаическую мотивировку той же изопериметрической и ряда близких к ней задач мы находим, пусть даже в несколько наивной, но достаточно отчетливой форме в легенде о Дидоне. Напомним ее, следуя «Энеиде» римского поэта Вергилия.

Финикийская царевна Дидона и с ней небольшой отряд жителей города Тира, спасаясь от преследований тирана – брата Дидоны, покинули родной город и в поисках счастья отправились на кораблях на запад вдоль берегов Средиземного моря. Выбрав на африканском побережье удобное место (нынешний Тунисский залив), Дидона и ее спутники решили основать здесь поселение. По-видимому, эта идея не вызвала энтузиазма у местных жителей, но все же Дидоне удалось уговорить их предводителя Ярба, и он неосторожно согласился уступить Дидоне клочок земли, «который можно окружить бычьей шкурой». Не сразу понял простодушный Ярб хитрость и коварство финикиянки. Разрезав шкуру на тонкие полоски, Дидона связала их в один длинный ремень и, окружив им значительную территорию, заложила на ней город Карфаген. В память об этой истории карфагенская цитадель получила название Бирса (на языке жителей Карфагена это слово означает «шкура»). Все эти события легенда относит к 825 (или 814) г. до н. э.

Как может звучать здесь задача оптимизации?

Требуется указать оптимальную форму участка земли, который при заданной длине периметра L имеет наибольшую площадь S. Ясно, что это та же самая классическая изопериметрическая задача. Ее решением является круг.

Решение изопериметрической задачи заключено в следующем утверждении:

Если спрямляемая кривая длины L ограничивает плоскую фигуру площади S, то

Причем неравенство имеет место тогда и только тогда, когда кривая – окружность.

С.В.: Еще одной типичной задачей оптимизации является задача коммивояжера. Расскажите, пожалуйста, о ней поподробнее...

Ю.Г.: Да, эта задача является одной из самых знаменитых в теории комбинаторики и пользуется популярностью благодаря тому, что к ней сводится большое количество практических задач. В своей области задача коммивояжера служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка задачи следующая. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? На этот вопрос можно ответить, используя алгоритмы оптимизации.

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

На самом деле все, что мы делаем – это и есть либо максимизация, либо минимизация. В каждом деле. Вот, например, человек поставил перед собой задачу жить лучше. Как можно этого достичь? Необходимо стараться максимизировать свое счастье, успех, карьеру – то есть решить задачу максимизации, а также минимизации всяких неприятностей, учитывая все ограничения, накладываемые моралью, религией, законами и т.д. В целом это и есть оптимизация.

Сейчас иногда можно видеть, как слово «оптимизация» приобретает негативный оттенок. Например, часто пишут, что в компании нужно провести оптимизацию. Что это означает? Зачастую имеется в виду, что необходимо провести сокращение. Но на деле совсем необязательно оптимизация приведет к сокращению. Возможно, даже наоборот, после решения задачи оптимизации может потребоваться привлечение большего количества сотрудников для блага компании.

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

Вот еще один хороший пример из области конструирования. Образуются молекулы из аминокислот. Посмотрите, на рисунке их 90 штук.

Полученная конфигурация особая, здесь есть порядок, гармония, это оптимально с точки зрения минимизации потенциала.

Конструкторы-биологи могут по этому рисунку создать молекулу, то есть они могут каждую аминокислоту поместить в нужное место и таким образом будет создана молекула. Это важно для разработки новых лекарств.

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

Итак, задача сводится к тому, чтобы минимизировать некоторый потенциал по координатам всех 90 точек.

Как решается такая задача? В пространстве нужно задать по три координаты каждой точки. Из условия следует, что неизвестно 90 точек. Умножим на 3, получим 270 неизвестных переменных, по которым надо искать минимум. Надо найти такие координаты, в которых потенциальная функция достигает своего минимального значения.

Это хороший пример нетривиальной задачи на поиск глобального экстремума.

В.П.: Юрий Гаврилович, давайте поясним читателю: что такое глобальный экстремум?

Ю.Г.: Экстремум бывает глобальный и локальный. Приведем пример. Допустим, человек хочет купить компьютер. Найти глобальное (наилучшее) решение за минимальную стоимость при определенных ограничениях на производительность, качество и т.д. Можно искать по всей Москве – это будет задача на поиск глобального экстремума. А можно ограничиться своим районом, это будет локальный экстремум, тогда цель будет в том, чтобы произвести оптимизацию по одному району. Очевидно, чем больше область поиска, тем больше вариантов, тем лучше компьютер будет найден.

Если человек занимается поиском компьютера по информации в интернете, то можно просмотреть весь интернет, что нереально, а можно ограничиться фиксированным временем поиска.

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

Функции, у которых необходимо найти глобальный экстремум, могут быть очень сложными, например, такими, как на рисунке…

Кстати, по глобальной оптимизации существует прекрасный учебник наших нижегородских ученых – Романа Стронгина и Ярослава Сергеева «Global Optimization with Non-Convex Constraints, Sequential and Parallel Algorithms. Книга описывает различные численные методы с наглядными примерами и подробным изложением.

Оптимизация есть всюду. Вы идете на рынок за продуктами. Конечно, с одной стороны вы хотите минимально потратить деньги, с другой стороны, купить наилучшие продукты по качеству. Для этого необходимо решить задачу оптимизации, причем здесь будет многокритериальная оптимизация. Один критерий – необходимо потратить меньше денег, второй – получить товар наивысшего качества. По качеству максимизация, по деньгам минимизация. Задача многокритериальная – сложная, т.к. есть два критерия и они противоречивы.

С.В.: Итак, как я понимаю, ключевой момент - многокритериальная оптимизация?

Ю.Г.: Именно…

Вот еще один пример многокритериальной задачи. В 30-е годы прошлого века И.В. Сталин дал указание генеральным авиаконструкторам, что надо делать такие самолеты, чтобы они летали дальше всех, выше всех и быстрее всех.

Вы видите, что здесь целых три критерия, и все они противоречивые.

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

Так как критерии противоречивые, тут надо пойти на компромисс между критериями или построить паретовское множество (множество Парето, по имени итальянского ученого Парето).

Паретовское множество – это целое семейство решений, удовлетворяющее критериям. Однако, необходимо помнить, что если мы улучшаем какой-то один критерий, то неизбежно ухудшается какой-нибудь другой, так как критерии взаимосвязаны. Задача состоит в том, чтобы построить паретовское множество и дать возможность лицу, принимающему решения, выбрать из этого множества одно решение.

С.В.: Юрий Гаврилович, хотелось бы рассмотреть задачу, чрезвычайно актуальную в наше время для провайдеров сотовой связи: задачу развития сети и улучшения качества связи. Задача зависит от множества факторов, все их необходимо учесть и прийти к наиболее оптимальному решению.

Ю.Г.: Да, это задача действительно актуальная в наше время и это хороший пример типичной оптимизационной задачи.

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

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

Даже в простейшем одномерном случае сделать это не так просто. Говоря формальным языком, от нас требуется найти глобальный экстремум функции многих переменных. Решить такую задачу без применения оптимизационных современных методов и высокопроизводительной вычислительной техники было бы крайне трудно.

С.В.: Приведите, пожалуйста, пример применения оптимизации в области освоения новых территорий нашей страны.

Ю.Г.: Обустройство нефте- и газодобычи, нефтеносные поля. В то время, когда осваивалась западная Сибирь, естественно, возникал вопрос, где ставить скважины и как сделать транспортную сеть?

Из Москвы во Владивосток можно добраться множеством путей, но необходимо найти оптимальный кратчайший. Это транспортная задача, как добраться из одного пункта в другой. Для наглядности, можно взять глобус и нитку, и протянуть нитку от одного пункта до другого. Когда длина нитки будет минимальной? Это и есть самый короткий путь. Но при этом мы не учли много реальных ограничений: рельеф местности, наличие на пути рек, гор и озер. Кроме этого, не учтено то, что часть Сибири постоянно находится в вечной мерзлоте. А ведь путь необходимо прокладывать с учетом всех факторов. И в науке, и в технике, и в жизни – всюду нужна оптимизация!

В ВЦ РАН, в отделе, руководимым В.Р. Хачатуровым, была создана система такого типа, предназначенная для проектирования и освоения нефтяных и газовых месторождений Западной Сибири.

Одним из важнейших результатов, полученных в ВЦ РАН, явилось то, что был обнаружен феномен «ядерной зимы». В 70-х годах прошлого века академиком Моисеевым Н.Н. и его учеником В.В. Александровым было показано, что в результате возможной в то время ядерной войны между США и СССР могла возникнуть «ядерная зима», в результате которой температура на Земле резко упала бы и это привело бы к гибели всего живого на нашей планете. Правительствам многих стран стало ясно, что решать конфликты военным путем невозможно. В результате этих исследований произошли большие сокращения ядерного оружия, снизилась опасность ядерного конфликта.

С.В.: Какие крупные проекты были реализованы в вашем институте?

Ю.Г.: Расскажем об одной из простейших задач. Для Конструкторского Бюро Сухого П.О. (КБ Сухого) мы решали такую задачу: летит самолет на определенной высоте, ему надо развернуться на 180 градусов, подняться на заданную высоту за кратчайшее время. Получается так называемый боевой разворот. Что надо сделать? Надо увеличивать тягу двигателя с максимальной скоростью. Тягу нельзя мгновенно изменить. Есть ограничения на скорость изменения тяги и перегрузку на крен.

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

С.В.: Практические задачи оптимизации – достаточно сложные и их расчет требует высокопроизводительных компьютерных систем и эффективного программного обеспечения. Какие программные методы применялись для решения подобных задач?

Ю.Г.: В конце 70-х годов у нас в ВЦ имени А. А. Дородницына РАН была разработана Диалоговая Система Оптимизации (ДИСО). Эта была первая человеко-машинная диалоговая система для решения задач оптимизации на ЭВМ. Она была реализована на лучшей отечественной машине того времени БЭСМ-6 и затем перешла на машины серии ЕС. В ДИСО впервые была реализована техника быстрого автоматического дифференцирования. Система также позволяет по программе заданных функций, определяющей постановку оптимизационной задачи, вычислять точное значение градиентов всех этих функций.

Этот подход успешно развивается в ВЦ РАН и в настоящее время. С его помощью решается ряд задач оптимального управления процессом плавления и кристаллизации изделий сложной геометрической формы для задач авиационного и космического машиностроения.

Впоследствии система была внедрена в многочисленные организации, в том числе в КБ Сухого

ДИСО – это человеко-машинная система. Человек сидит и управляет расчетами, задает алгоритмы, параметры этих алгоритмов. И смотрит, как идет вычислительный процесс.

Например, замечает, что метод стал плохо работать. Какими должны быть его действия? Поменять параметры метода. Если это не поможет, то дать команду перейти на другой метод оптимизации. Оптимизационных методов очень много. Работа происходит в режиме диалога с машиной.

Вот еще интересный пример…

Мы сотрудничаем со многими университетами, в том числе и с МГТУ им. Н.Э. Баумана. Там есть инженеры, которые занимаются робототехникой и перед ними стояла следующая задача.

В рабочем цеху установлен робот-манипулятор. Предполагается, что он производит некоторые работы. Причем, условия действия его рук, которыми он перемещает детали, заданы. Требуется опередить ту зону, в которой робот будет находиться в процессе выполнения работ, с тем, чтобы в этой зоне не было посторонних предметов и туда не заходили люди. Это типичная задача на поиск глобального экстремума, она решалась оригинальным методом неравномерных покрытий, разработанным в ВЦ РАН.

В.П.: Юрий Гаврилович, StatSoft сейчас активно занимается статистическими и аналитическими исследованиями данных в таких областях, как медицина, фармакология, промышленность, экономика, геологоразведка, страхование и множество других. Было бы очень интересным, и думаем, плодотворным, организовать сотрудничество с учеными ВЦ РАН и со специалистами базовой кафедры МФТИ. Что вы об этом думаете?

Ю.Г.: Да, действительно, было бы очень интересно и полезно обменяться опытом. Похожие задачи - бесценный кладезь знаний, накопившийся за столько лет практики в самых различных областях. StatSoft смог бы привнести в свою работу дух научно-исследовательской деятельности, а наши специалисты имели бы возможность применить свои знания на практике в востребованной среде.

В.П.: Спасибо Вам огромное за беседу!

Ю.Г.: Спасибо и Вам!

Краткая биография Юрия Гавриловича:

Евтушенко Юрий Гаврилович родился 28 декабря 1938 г. в г. Краснодаре. Окончил Московский физико-технический институт (1962).

С 1965 г. по 1967 г. работал в Центральном аэрогидродинамическом институте (ЦАГИ).

В 1974-1975 гг. – научный сотрудник Международного института системного анализа (Вена, Австрия). С 1967 г. по настоящее время работает в Вычислительном Центре АН СССР сначала в должностях младшего, затем старшего научного сотрудника, зав. отделом, заместителем директора (1981-1989), а с 1989 г. по настоящее время – директором ВЦ РАН. По совместительству работает в МФТИ и МГУ.

Кандидат физико-математических наук (1976), доктор физико-математических наук (1981). Профессор (1983). Член-корреспондент РАН (1990). Член Бюро Отделения математики РАН. Лауреат премии Совета Министров СССР (1981). Награжден орденом “Знак Почета”.

В 2006 избран действительным членом (академиком) Российской академии наук. С 1992 по 2004 год – главный редактор созданного им международного журнала “Optimization Methods & Software”, издаваемого в Великобритании. В настоящее время – почетный редактор-учредитель этого журнала, член редколлегий “Журнала вычислительной математики и математической физики”, международных журналов “Computers & Mathematics with Applications”, “Journal of Global Optimization”, “Informatica”.

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

Ю.Г.Евтушенко создал научную школу, известную своими результатами не только у нас в стране, но и за рубежом. Подготовил 5 докторов, 16 кандидатов наук.

Читает лекционные курсы: "Численные методы оптимизации", "Методы глобальной оптимизации нелинейного программирования". Автор более 200 научных трудов.