{"588915":{"#nid":"588915","#data":{"type":"event","title":"PhD Defense by Daniel Zink","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E A Reduction Framework for Approximate Extended Formulations\u003Cbr \/\u003E\r\n\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; and a Faster Algorithm for Convex Optimization\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003ETime\u003C\/strong\u003E: Wednesday, March 29, 10:00am\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003ELocation:\u003C\/strong\u003E ISyE Groseclose 402\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003EAdvisor\u003C\/strong\u003E: Prof. Sebastian Pokutta\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003ECommittee:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nProf. Sebastian Pokutta, School of Industrial and Systems Engineering\u003Cbr \/\u003E\r\nProf. Greg Blekherman, School of Mathematics\u003Cbr \/\u003E\r\nProf. Santanu Dey, School of Industrial and Systems Engineering\u003Cbr \/\u003E\r\nProf. George Lan, School of Industrial and Systems Engineering\u003Cbr \/\u003E\r\nProf. Santosh Vempala, School of Computer Science\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003EReader:\u003C\/strong\u003E Prof. George Lan, School of Industrial and Systems Engineering\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe thesis is available for public inspection in the School of\u003Cbr \/\u003E\r\nMathematics lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE\u003Cbr \/\u003E\r\nPhD student lounge and at the URL\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Ca href=\u0022http:\/\/aco.gatech.edu\/events\/final-doctoral-examination-and-defense-dissertation-daniel-zink\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/aco.gatech.edu\/events\/final-doctoral-examination-and-defense-dissertation-daniel-zink\u003C\/a\u003E\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003ESUMMARY:\u003C\/strong\u003E Linear programming (LP) and semidefinite programming (SDP) are\u003Cbr \/\u003E\r\namong the most important tools in Operations Research and Computer\u003Cbr \/\u003E\r\nScience. In this work we study the limitations of LPs and SDPs by\u003Cbr \/\u003E\r\nproviding lower bounds on the size of (approximate) linear and\u003Cbr \/\u003E\r\nsemidefinite programming formulations of combinatorial optimization\u003Cbr \/\u003E\r\nproblems. The hardness of (approximate) linear optimization implied by\u003Cbr \/\u003E\r\nthese lower bounds motivates the lazification technique for conditional\u003Cbr \/\u003E\r\ngradient type algorithms. This technique allows us to replace\u003Cbr \/\u003E\r\n(approximate) linear optimization in favor of a much weaker subroutine,\u003Cbr \/\u003E\r\nachieving significant performance improvement in practice. We can\u003Cbr \/\u003E\r\nsummarize the main contributions as follows:\u003Cbr \/\u003E\r\n(i) Reduction framework for LPs and SDPs: We present a new view on\u003Cbr \/\u003E\r\nextended formulations that does not require an initial encoding of a\u003Cbr \/\u003E\r\ncombinatorial problem as a linear or semidefinite program. This new view\u003Cbr \/\u003E\r\nallows us to define a purely combinatorial reduction framework\u003Cbr \/\u003E\r\ntransferring lower bounds on the size of exact and approximate LP and\u003Cbr \/\u003E\r\nSDP formulations between different problems. Using our framework we show\u003Cbr \/\u003E\r\nnew LP and SDP lower bounds for a large variety of problems including\u003Cbr \/\u003E\r\nVertex Cover, various (binary and non-binary) constraint satisfaction\u003Cbr \/\u003E\r\nproblems as well as multiple optimization versions of Graph-Isomorphism.\u003Cbr \/\u003E\r\n(ii) Lazification technique for Conditional Gradient algorithms: In\u003Cbr \/\u003E\r\nConvex Programming conditional gradient type algorithms (also known as\u003Cbr \/\u003E\r\nFrank-Wolfe type methods) are very important in theory as well as in\u003Cbr \/\u003E\r\npractice due to their simplicity and fast convergence. We show how we\u003Cbr \/\u003E\r\ncan eliminate the linear optimization step performed in every iteration\u003Cbr \/\u003E\r\nof Frank-Wolfe type methods and instead use a weak separation oracle.\u003Cbr \/\u003E\r\nThis oracle is significantly faster in practice and enables caching for\u003Cbr \/\u003E\r\nadditional improvements in speed and the sparsity of the obtained solutions.\u003Cbr \/\u003E\r\n\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Reduction Framework for Approximate Extended Formulations and a Faster Algorithm for Convex Optimization"}],"uid":"27707","created_gmt":"2017-03-16 20:18:54","changed_gmt":"2017-03-16 20:18:54","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-03-29T11:00:00-04:00","event_time_end":"2017-03-29T13:00:00-04:00","event_time_end_last":"2017-03-29T13:00:00-04:00","gmt_time_start":"2017-03-29 15:00:00","gmt_time_end":"2017-03-29 17:00:00","gmt_time_end_last":"2017-03-29 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}