Ученый ИПМаш РАН создал новый алгоритм решения задач оптимизации
Ведущий научный сотрудник ИПМаш РАН Максим Долгополик создал алгоритм решения сложных задач невыпуклой оптимизации. Алгоритм может быть использован для управления сетевыми, распределнными и колебательными системами. Результаты исследования опубликован в Computational Optimization and Applications.
Задачи оптимизации являются актуальными при решении многих практических задач. В оптимизации изучаются методы выбора оптимальных параметров в различных задачах, возникающих в приложениях. Например, задача построения оптимального маршрута, с целью добраться из одной точки города в другую за наименьшее время, которая решается навигатором в смартфоне. Задачи ученых в сфере оптимизации заключаются в разработке программного обеспечения и самих методов, которые позднее применяются на практике, например, на производстве.
Задачи в оптимизации делятся на различные классы, отражающие их особенности. Для каждого класса разрабатываются свои специальные методы решения. Наиболее изученными являются задачи выпуклой оптимизации. Для задач выпуклой оптимизации разработано множество очень эффективных методов и пакетов программ, реализующих эти методы на компьютере. Задачи невыпуклой оптимизации сложнее.
Одним из эффективных подходов к задачам невыпуклой оптимизации является DC оптимизация (от англ. Difference of Convex functions) - оптимизация разности выпуклых функций. Основная идея этого подхода заключается в том, что поскольку имеется возможность эффективно и быстро решать выпуклые задачи, то стоит попытаться каким-нибудь образом применить методы выпуклой оптимизации к невыпуклым задачам. Это можно сделать разными способами. В рамках DC оптимизации это делается с помощью сведения невыпуклой задачи к некоторому специально построенному набору выпуклых задач. Ранее ведущий научный сотрудник ИПМаш РАН Максим Долгополик доказал возможность применения методов DC оптимизации к решению некоторых классов таких задач.
«В новой работе речь идёт о распространении классического метода DCA (от англ. Difference of Convex functions Algorithm) на случай задач с матричными ограничениями (в частности, задач негладкой оптимизации на матричных многообразиях). Статья посвящена подробному анализу этого метода для таких задач. Также в ней приведены примеры применения этого метода к решению нескольких прикладных задач, продемонстрировавшие высокую эффективность предложенного метода. В новой статье показано, как с помощью разработанного в первой части исследования теоретического аппарата можно построить прикладной численный метод (алгоритм) и с его помощью решать прикладные задачи на компьютере», - рассказал Максим Долгополик.
В научной работе предложен новый численный метод (алгоритм) решения некоторых классов сложных невыпуклых задач оптимизации, а именно, негладких задач полуопределённого программирования и задач негладкой оптимизации на матричных многообразиях. В ходе работы была осуществлена программная реализация разработанного алгоритма и были проведены численные эксперименты на компьютере, показавшие высокую эффективность разработанного метода.