Immanuel M. Bomze was born in Vienna, Austria, in 1958. He received the degree Magister rerum naturalium in Mathematics at the University of Vienna in 1981. After a postgraduate scholarship at the Institute for Advanced Studies, Vienna from 1981 to 1982, he received the degree Doctor rerum naturalium (Ph.D.) in Mathematics at the University of Vienna. After his Habilitation 1987, he held several visiting research positions at various research institutions across Europe, the Americas, Asia and Australia. He also gained some practical Operations Research experience during his work as a research mathematician in the Business & Marketing Research/Operations Research group of the national incumbent telecommunication operator Telekom Austria 2002-2004. Since 2004, he holds a chair (full professor) of Applied Mathematics and Statistics at the University of Vienna and since 2009, Bomze serves as the Study Director of the Abraham-Wald-PhD program in Statistics and Operations Research, located at the Faculty of Business, Economics, and Statistics at this university. Bomze's research interests are in the areas of nonlinear optimization, qualitative theory of dynamical systems, game theory, mathematical modelling and statistics, where he has edited one and published four books, as well as over 100 peer-reviewed articles in scienti fic journals and monographs. The list of his co-authors comprises over seventy scientists from more than a dozen countries in four continents. In 2014 he was elected Fellow of EurOpt, the Continuous Optimization Working Group of EURO, the Association of European Operational Research Societies. As a member of program and/or organizing committees, he co-organized various scientific events and he is an Associate Editor for five international journals. For several science foundations and councils (based in Canada, the Czech Republic, Germany, Great Britain, Hong Kong, Israel, Italy, the Netherlands, Norway, Portugal, Singapore, Spain, USA), and for almost 50 scientific journals he acted as a reporting referee. Until the end of 2017 he serves as an Editor of the European Journal of Operational Research, one of the worldwide leading journals in the field. Bomze co-founded the Vienna Center of Operations Research (VCOR) and serves as its co-director. Recently he was nominated as a candidate for the president-elect of EURO, who will commence office in 2018.
Abstract
On gaps and dots - duality and attainability in conic optimization
based upon joint work with:
Jianqiang Cheng, Univ. Arizona; Peter J.C. Dickinson, Univ. Twente; Abdel Lisser, Univ. Paris Sud; Werner Schachinger and Gabriele Uchida, Univ. Vienna.
One of the most powerful methods for obtaining efficient bounds for hard optimization problems is based upon (Lagrangian) duality, i.e. linearly combining the original objective and (some of) the constraints. In general there will be a gap between the best such bound, i.e., the optimal dual value, and the originally sought optimal primal value. Most frequently, a positive duality gap is blamed upon failure of convexity; however, even in a linear context (over convex cones), positive or even infinite duality gaps can also occur (in sharp contrast to the familiar linear optimization over polyhedra), and this is due to a failure of closedness of related sets, rather than a convexity problem. Likewise, attainability can fail in this context as witnessed by the celebrated Frank-Wolfe theorem and related all-quadratic counterexamples over convex feasible sets.
Moreover, the dual problem significantly depends on the choice how to model the primal problem: one and the same primal problem can have several dual formulations with different gaps and attainability properties; the talk will address a recently investigated hierarchy of these dual models: we consider a primal-dual pair of conic optimization which deals with optimizing a linear function over an affine subset of a closed, convex cone. Well investigated and widely used examples include the positive orthant (LP), the semidefinite cone (SDP), the copositive cone (COP) or the completely positive cone (CPP).
The latter two occur in reformulations or tight relaxations of hard optimization problems, among them indefinite quadratic (fractional or binary) programs, and several combinatorial optimization problems.
This talk presents a construction which transforms any such primal-dual pair with an arbitrary (zero, positive or infinite) duality gap into another pair with the same optimal objective values, where either the primal or the dual optimal value is not attained. The construction basically doubles the size of the problems and establishes all possible combinations of gaps and attainability.
Further, a quite recent fresh look at mixed-binary quadratic problems will be offered, establishing a hierarchy of dual problems with different tightness of dual bounds and time permitting, we will shortly address the Semi-Lagrangian tightening of all-quadratic problems with a copositive reformulation. As is well-known, (COP) or (CPP) cannot be solved directly since the involved cones are intractable, but they can be approximated to arbitrary accuracy, e.g. the copositive cone from inside by polyhedral cones yielding a sequence of LPs which all tighten classical Lagrangian bounds considerably in case of a positive classical duality gap.
based upon joint work with:
Jianqiang Cheng, Univ. Arizona; Peter J.C. Dickinson, Univ. Twente; Abdel Lisser, Univ. Paris Sud; Werner Schachinger and Gabriele Uchida, Univ. Vienna.
One of the most powerful methods for obtaining efficient bounds for hard optimization problems is based upon (Lagrangian) duality, i.e. linearly combining the original objective and (some of) the constraints. In general there will be a gap between the best such bound, i.e., the optimal dual value, and the originally sought optimal primal value. Most frequently, a positive duality gap is blamed upon failure of convexity; however, even in a linear context (over convex cones), positive or even infinite duality gaps can also occur (in sharp contrast to the familiar linear optimization over polyhedra), and this is due to a failure of closedness of related sets, rather than a convexity problem. Likewise, attainability can fail in this context as witnessed by the celebrated Frank-Wolfe theorem and related all-quadratic counterexamples over convex feasible sets.
Moreover, the dual problem significantly depends on the choice how to model the primal problem: one and the same primal problem can have several dual formulations with different gaps and attainability properties; the talk will address a recently investigated hierarchy of these dual models: we consider a primal-dual pair of conic optimization which deals with optimizing a linear function over an affine subset of a closed, convex cone. Well investigated and widely used examples include the positive orthant (LP), the semidefinite cone (SDP), the copositive cone (COP) or the completely positive cone (CPP).
The latter two occur in reformulations or tight relaxations of hard optimization problems, among them indefinite quadratic (fractional or binary) programs, and several combinatorial optimization problems.
This talk presents a construction which transforms any such primal-dual pair with an arbitrary (zero, positive or infinite) duality gap into another pair with the same optimal objective values, where either the primal or the dual optimal value is not attained. The construction basically doubles the size of the problems and establishes all possible combinations of gaps and attainability.
Further, a quite recent fresh look at mixed-binary quadratic problems will be offered, establishing a hierarchy of dual problems with different tightness of dual bounds and time permitting, we will shortly address the Semi-Lagrangian tightening of all-quadratic problems with a copositive reformulation. As is well-known, (COP) or (CPP) cannot be solved directly since the involved cones are intractable, but they can be approximated to arbitrary accuracy, e.g. the copositive cone from inside by polyhedral cones yielding a sequence of LPs which all tighten classical Lagrangian bounds considerably in case of a positive classical duality gap.
