IMPLEMENTATION OF AN INTERIOR POINT CUTTING PLANE ALGORITHM

Abstract

In this thesis, first we propose a new approach to solve Semi Infinite Linear Optimization Problems (SILP). The new algorithm uses the idea of adding violated cut or cuts at each iteration. Our proposed algorithm distinguishes itself from Luo, Roos, and Terlaky's logarithmic barrier decomposition method, in three aspects: First, the violated cuts are added at their original locations. Second, we extend the analysis to the case where multiple violated cuts are added simultaneously, instead of adding only one constraint at a time. Finally, at each iteration we update the barrier parameter and the feasible set in the same step. In terms of complexity, we also show that a good approximation of an optimal solution will be guaranteed after finite number of iterations. Our focus in this thesis is mainly on the implementation of our algorithm to approximate an optimal solution of the SILP. Our numerical experiences show that unlike other SILP solvers which are suffering from the lack of accuracy, our algorithm can reach high accuracy in a competitive time. We discuss the linear algebra involved in efficient implementation and describe the software that was developed. Our test problem set includes large scale second order conic optimization problems.