New techniques for determining search directions of interior point algorithms in optimization

Abstract

This thesis deals with solving optimization problems using primal-dual interior point methods. By employing algebraic transformations of centrality equations, we conducted a theoretical and algorithmic study on four optimization problems: linear programming, convex quadratic programming, linear semidefinite programming and convex quadratic semidefinite programming. For each problem, through various algebraic transformations, we demonstrated the convergence of the proposed algorithms and provided the rates of their polynomial algorithmic complexities. The obtained results are reinforced by highly significant numerical experiments.