USING SEMIDEFINITE SIMPLEX METHOD FOR SOLVING SEMIDEFINITE PROBLEMS

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.