Group for Research in Decision Analysis

New cutting plane approaches for non-convex optimization problems

Gonzalo Munoz Polytechnique Montréal, Canada

Modern problems arising in many domains are driving a need for more capable, state-of-the-art optimization tools. In particular, science and engineering applications are constantly pushing the development of new efficient methods for challenging problems, namely, non-convex optimization problems. In this talk, we will show novel approaches for generating approximations to these problems via cutting planes: a classical technique proven to be key in effective methods for mixed-integer programming. First, we show how a reformulation of generic polynomial optimization problems and the long-studied theory of "intersection cuts" can be used to obtain cutting planes with minimal structural assumptions about the problems. Second, and motivated by the close relationship between numerical stability of algorithms and sparsity of optimization formulations, we discuss ongoing work aimed at searching for sparse cutting planes in non-convex quadratic problems. In both cases, we will show numerical experiments indicating the potential these approaches have.

Coffee and biscuits will be offered at the beginning of the seminar.
Welcome to everyone!