Read the full paper at: http://www.scirp.org/journal/PaperInformation.aspx?PaperID=49675 DOI: 10.4236/ajor.2014.45028 Author(s) Orkia Derkaoui, Ahmed Lehireche Affiliation(s) Computer Science Department, University Dr Moulay Tahar of Saida, Saida, Algeria. Computer Science Department, University Djillali Liabes of SidiBel Abbes, SidiBel Abbes, Algeria. ABSTRACT 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.gjreww140917 KEYWORDS Semidefinite Programming, Interval Arithmetic, Rigorous Error, Bounds, SDPA Solver, Branch and Bound Algorithm
