Back to search

Cornell University

A Quadratic Cone Relaxation-Based Algorithm For Linear Programming

Abstract

dc:description.abstract

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).

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 × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8793417

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sondjaja, Mutiara. A Quadratic Cone Relaxation-Based Algorithm For Linear Programming. Doctor of Philosophy thesis, Cornell University, 2014. https://hdl.handle.net/1813/39004