USING SEMIDEFINITE SIMPLEX METHOD FOR SOLVING SEMIDEFINITE PROBLEMS

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

Semidefinite optimization is relatively a new field of researches. It finds a lot of applications in combinatorial optimization, computational geometry and network theory. Over the last years applications of semidefinite optimization are continuously expanded. We can find exact or approximate solution of many NP-hard problems by using semidefinite relaxation. In this paper we use a generalization of simplex-method for solving semidefinite problems. The main idea of this method is to use the approximation of the cone of semidefinite matrices by the sum of one-rank matrices. In this way we replace the original objective function by a linear combination of one-rank matrices. A lot of numerical experiments were performed and the findings are very encouraging.