A Quadratic Cone Relaxation-Based Algorithm For Linear Programming
We present and analyze a linear programming (LP) algorithm based on replacing the non-negative orthant with larger quadratic cones. For each quadratic relaxation that has an optimal solution, there naturally arises a parameterized family of quadratic cones for which the optimal solutions create a path leading to the LP optimal solution. We show that this path can be followed efficiently, thereby resulting in an algorithm whose complexity matches the best bounds proven for interior-point methods. We then extend the algorithm to semidefinite programming (SDP).
Linear programming; Semidefinite programming; Interior-point methods
Williamson, David P; Todd, Michael Jeremy
Ph.D. of Operations Research
Doctor of Philosophy
dissertation or thesis