Лаборатория 6.1. Невыпуклой оптимизации
Основные направления исследований лаборатории:
- разработка теории и методов решения невыпуклых задач оптимизации и оптимального управления с непрерывными данными;
- исследование математических моделей и разработка алгоритмов решения задач дискретной оптимизации большой размерности.
Важнейшие научные результаты:
Для невыпуклых задач оптимизации общего вида (с ограничениями типа равенства и неравенства и целевой функцией, заданными разностями выпуклых функций: DC функциями) разработана новая теория глобального поиска (ТГП), ядром которой являются оригинальные условия глобальной оптимальности (УГО). Известно, что любая задача оптимизации с непрерывными данными на компакте может быть с любой точностью аппроксимирована задачей с DC функциями. При этом классические условия оптимальности (УО), например, правило Лагранжа (теорема Каруша – Куна – Таккера) являются очень частным случаем УГО (тем более, приближенных УГО), позволяющих не только «выйти» из локального решения и/или стационара, но и достичь глобального решения в общей и канонических задачах DC оптимизации (выпуклая максимизация, обратно-выпуклые задачи, DC-минимизация и т.п.).
Для общей задачи DC оптимизации разработана и обоснована генеральная схема (стратегия) глобального поиска (ГСГП), состоящая из двух частей:
а) семейства специальных методов локального поиска (СМЛП); б) процедур выхода из критических точек (полученных СМЛП), основанных на УГО. При этом доказана сходимость новой ГСГП, использующей Теорию точного штрафа (ТТШ), когда рассматривается последовательность оштрафованных задач с ограниченной последовательностью штрафных параметров, а не с бесконечным пределом. Обязательно доказывается также сходимость методов локального поиска к некоторому критическому вектору. Кроме того, «внутри» методов локального поиска применяются классические методы выпуклой оптимизации и современные пакеты прикладных программ (CPLEX, GUROBI, X-PRESS и др.), что значительно увеличивает эффективность СМЛП и ГСГП.
В последние десятилетия начато построение новой теории глобального поиска для задач оптимального управления (ОУ) с невыпуклыми данными (структурами).
Разработка Теории глобального поиска позволила решить следующие актуальные задачи, некоторые из которых, по мнению ведущих специалистов, представляют вызовы XXI века:
— численный поиск равновесий (скажем, по Нэшу), например, в полиматричных играх и конфликтных ситуациях в экономике, экологии и военных приложениях;
— численный поиск оптимистических и гарантированных решений в иерархических задачах управления;
— численное решение систем нелинейных алгебраических уравнений (СНАУ) и неравенств повышенной размерности (n=10^3 – 10^4);
— численное решение прикладных задач оптимального управления, невыпуклых по состоянию;
— прикладные целочисленные и комбинаторные задачи оптимизации (например, с булевыми переменными);
— задачи фракционной (дробной) оптимизации, возникающие в молекулярной биологии и медицине и других областях цивилизации.