Back to search

Georgia Institute of Technology

A reduction framework for approximate extended formulations and a faster algorithm for convex optimization

Abstract

dc:description.abstract

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

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zink, Daniel
Advisor dc:contributor.advisor
  • Pokutta, Sebastian
Committee members dc:contributor.committeemember
  • Blekherman, Grigoriy
  • Dey, Santanu S.
  • Lan, Guanghui
  • Vempala, Santosh

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/58274

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zink, Daniel. A reduction framework for approximate extended formulations and a faster algorithm for convex optimization. Doctoral thesis, Georgia Institute of Technology, 2017. http://hdl.handle.net/1853/58274