Author(s)

Orkia Derkaoui¹, Ahmed Lehireche²

¹Computer Science Department, University Dr Moulay Tahar of Saida, Saida, Algeria.
²Computer Science Department, University Djillali Liabes of SidiBel Abbes, SidiBel Abbes, Algeria.

Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.

Semidefinite Programming, Interval Arithmetic, Rigorous Error, Bounds, SDPA Solver, Branch and Bound Algorithm

Derkaoui, O. and Lehireche, A. (2014) Safe Bounds in Semidefinite Programming by Using Interval Arithmetic. American Journal of Operations Research, 4, 293-300. doi: 10.4236/ajor.2014.45028.