Show simple item record

dc.contributor.advisorPokutta, Sebastian
dc.contributor.authorZink, Daniel
dc.date.accessioned2017-06-07T17:42:22Z
dc.date.available2017-06-07T17:42:22Z
dc.date.created2017-05
dc.date.issued2017-04-06
dc.date.submittedMay 2017
dc.identifier.urihttp://hdl.handle.net/1853/58274
dc.description.abstractLinear programming (LP) and semidefinite programming (SDP) are among the most important tools in Operations Research and Computer Science. In this work we study the limitations of LPs and SDPs by providing lower bounds on the size of (approximate) linear and semidefinite programming formulations of combinatorial optimization problems. The hardness of (approximate) linear optimization implied by these lower bounds motivates the lazification technique for conditional gradient type algorithms. This technique allows us to replace (approximate) linear optimization in favor of a much weaker subroutine, achieving significant performance improvement in practice. We can summarize the main contributions as follows: (i) Reduction framework for LPs and SDPs: We present a new view on extended formulations that does not require an initial encoding of a combinatorial problem as a linear or semidefinite program. This new view allows us to define a purely combinatorial reduction framework transferring lower bounds on the size of exact and approximate LP and SDP formulations between different problems. Using our framework we show new LP and SDP lower bounds for a large variety of problems including Vertex Cover, various (binary and non-binary) constraint satisfaction problems as well as multiple optimization versions of Graph-Isomorphism. (ii) Lazification technique for Conditional Gradient algorithms: In Convex Programming conditional gradient type algorithms (also known as Frank-Wolfe type methods) are very important in theory as well as in practice due to their simplicity and fast convergence. We show how we can eliminate the linear optimization step performed in every iteration of Frank-Wolfe type methods and instead use a weak separation oracle. This oracle is significantly faster in practice and enables caching for additional improvements in speed and the sparsity of the obtained solutions.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectExtended formulations
dc.subjectLinear programming
dc.subjectSemidefinite programming
dc.subjectApproximations
dc.subjectConvex optimization
dc.subjectFrank-Wolfe method
dc.subjectConditional gradients
dc.titleA reduction framework for approximate extended formulations and a faster algorithm for convex optimization
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentIndustrial and Systems Engineering
thesis.degree.levelDoctoral
dc.contributor.committeeMemberBlekherman, Grigoriy
dc.contributor.committeeMemberDey, Santanu S.
dc.contributor.committeeMemberLan, Guanghui
dc.contributor.committeeMemberVempala, Santosh
dc.date.updated2017-06-07T17:42:22Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record