14 октября 2011 года

Тропическое линейное программирование

Сергей Николаевич Сергеев (INRIA and CMAP Ecole Polytechnique, France)

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

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

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