Laboratory of Mathematical Logic at PDMI

Пятница, 21 июня, комната 106. Начало в 18:00.

Докладчик: А. Кожевников.

Доклад по статье P.Parrilo
ИСПОЛЬЗОВАНИЕ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ ДЛЯ ПОИСКА ПОЛУАЛГЕБРАИЧЕСКИХ ДОКАЗАТЕЛЬСТВ
Полуалгебраические системы доказательств -- один из новых интересных и активно изучаемых классов систем пропозициональных доказательств. В статье описывается новый подход для определения разрешимости системы полиномиальных неравенств с использованием полуопределенного программирования.
Основная идея метода заключается в переформулировке задачи разложения полинома от многих переменных в сумму квадратов в полуопределенную программу. Также используются некоторые результаты из вещественной алгебраической геометрии.
Автором статьи предложен эффективный алгоритм нахождения доказательства ограниченной степени в Positivstellensatz. Методы, использованные в этом алгоритме, имеют приложение и к другим задачам.
Источник: P.Parrilo, "Semidefinite programming relaxations for semialgebraic problems", Preprint, 2001, 15.