Numerical experiments with an interior-exterior point method for Semidefinite Programming

Session : PM / Programmation Mathématique
Vendredi 12 février 10:30 - 11:30 Salle : RP10
Derkaoui Orkia et Lehireche Ahmed

The SemiDefinite Programming (SDP) is not only an extension of Linear Programming (LP) but also includes convex quadratic optimization problems and some other convex optimization problems. It has a lot of applications in various fields such as combinatorial optimization, control theory, robust optimization, and quantum chemistry. In our work we present the implantation of a new algorithm for solving semidefinite programming problems. The algorithm is based on a new class of interior–exterior method. The latter is also known as the primal-dual method of type path-following where only one Newton iteration is sufficient to approximate the solution of penalized problem which satisfies a criterion of proximity. The result is demonstrated by solving problems from SDPLIB problem sets using semidefinite solver SDPA that is modified to include the interior-exterior point method subroutine. We specifically solved instances of quadratic problems. The preliminaries numerical results show the performance of this procedure and why its integration is a reasonable approach for solving semidefinite programming problems. Our future work is to implement a new variant of this method with another way to determine the step-size along the direction which is more efficient than classical line searches.

Mots clés : Interior point method, Exterior point method, Primal-dual method, Semidefinite programming, Interior–exterior approach