{"179101":{"#nid":"179101","#data":{"type":"event","title":"Daniel Bienstock, Columbia University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ESpeaker\u003C\/strong\u003E\u003Cbr \/\u003EDaniel Bienstock\u003Cbr \/\u003EIndustrial Engineering and Operations Research\u003Cbr \/\u003EColumbia University\u003Cbr \/\u003E\u003Cbr \/\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003Cbr \/\u003EConsider the problem of optimizing a convex function subject to nonconvex constraints; in particular, minimizing a positive-definite quadratic subject to nonconvex constraints. The approach favored by discrete optimizers would rely on solving some (hopefully strong) convex relaxation of the problem, and then resorting to branching and\/or cutting. However, when the objective is convex, this approach will fail, because even if the relaxation consists of the convex hull of the feasible region, the optimum over the relaxation will typically be infeasible, and (typically) \u0022far away\u0022 from the feasible region, yielding a very poor estimate (lower bound) on the value of the problem.\u003Cbr \/\u003E\u003Cbr \/\u003EWe describe a simple technique that relies on the so-called S-Lemma and on combinatorial estimates of the distance from a point to the feasible region, to obtain fast, strong bounds on the value of interesting cases of the situation described in the above paragraph.\u003Cbr \/\u003E\u003Cbr \/\u003E\u003Cstrong\u003EBio\u003C\/strong\u003E\u003Cbr \/\u003EProfessor Daniel Bienstock first joined Columbia University\u0027s Industrial Engineering and Operations Research Department in 1989. Professor Bienstock teaches courses on integer programming and optimization.\u003Cbr \/\u003E\u003Cbr \/\u003EBefore joining Columbia University, Professor Bienstock was involved in combinatorics and optimization research at Bellcore. He has also participated in collaborative research with Bell Laboratories (Lucent), AT\u0026amp;T Laboratories, Tellium, and Lincoln Laboratory on various network design problems.\u003Cbr \/\u003E\u003Cbr \/\u003EProfessor Bienstock\u0027s teaching and research interests include combinatorial optimization and integer programming, parallel computing and applications to networking. Professor Bienstock has published in journals such as Math Programming, SIAM, and Math of OR.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EConsider the problem of optimizing a convex function subject to nonconvex constraints; in particular, minimizing a positive-definite quadratic subject to nonconvex constraints. The approach favored by discrete optimizers would rely on solving some (hopefully strong) convex relaxation of the problem, and then resorting to branching and\/or cutting. However, when the objective is convex, this approach will fail, because even if the relaxation consists of the convex hull of the feasible region, the optimum over the relaxation will typically be infeasible, and (typically) \u0022far away\u0022 from the feasible region, yielding a very poor estimate (lower bound) on the value of the problem.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Joint ACO\/OR colloquium \u2014 Using eigenvalue techniques to obtain better bounds for convex objective, non-convex optimization problems"}],"uid":"27215","created_gmt":"2012-12-20 16:20:47","changed_gmt":"2016-10-08 02:01:40","author":"Mike Alberghini","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2009-11-03T10:00:00-05:00","event_time_end":"2009-11-03T11:00:00-05:00","event_time_end_last":"2009-11-03T11:00:00-05:00","gmt_time_start":"2009-11-03 15:00:00","gmt_time_end":"2009-11-03 16:00:00","gmt_time_end_last":"2009-11-03 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Cspan\u003ERenato Monteiro, ISyE\u003C\/span\u003E\u003Cbr \/\u003E\u003Ca href=\u0022http:\/\/www.gatech.edu\/contact\/?id=e4929\u0022\u003EContact Renato Monteiro\u003C\/a\u003E\u003Cbr \/\u003E\u003Cspan\u003E404-894-2300\u003C\/span\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}