Cornell University
A Quadratic Cone Relaxation-Based Algorithm For Linear Programming
Abstract
dc:description.abstractWe 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).
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Operations Research
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Operations Research
- Grantor
- Cornell University
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sondjaja, Mutiara
- Chair dc:contributor.chair
-
- Renegar, James
- Committee members dc:contributor.committeemember
-
- Williamson, David P
- Todd, Michael Jeremy
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 8793417