Sven Leyffer
Mathematics and Computer Science Division, Argonne National Laboratory, and Computation Institute, Chicago
Many design and engineering applications result in optimization problems that involve so-called black-box functions as well as integer variables, resulting in mixed-integer derivative-free optimization problems (MIDFOs). MIDFOs are characterized by the fact that a single function evaluation is often computationally expensive (requiring a simulation run for example) and that derivatives of the problem functions cannot be computed or estimated efficiently. In addition, many problems involve integer variables that are non-relaxable, meaning that we cannot evaluate the problem functions at non-integer points.

In the first part of our talk, we survey applications of MIDFO from a range of Department of Energy applications. The design of nano-photonic devices involves integer decision variables due to manufacturing limitations, and each function evaluation requires a finite-element simulation that takes several hours to run on a cluster. Similarly, automatic performance tuning of code snippets for high-performance computing involves non-relaxable integer variables such as loop-unroll-factors and compiler options and require several runs to eliminate random measurement errors. Finally, the design and operation of concentrating solar plants, requires forward simulations that take hours on a desktop and involve unrelaxable decision such as the number of panels on the receiver.

In the second part of our talk, we present a new method for non-relaxable MIDFO that enables us to prove global convergence under idealistic convexity assumptions. To the best of our knowledge this is the first globally convergent method for non-relaxable MIDFO apart from complete enumeration. Our method constructs hyperplanes that interpolate the objective function at previously evaluated points. We show that in certain portions of the domain, these hyperplanes are valid underestimators of the objective, resulting in a set of conditional cuts. The union of these conditional cuts provide a nonconvex underestimator of the objective. We show that these nonconvex cuts can be modeled as a standard mixed-integer linear program (MILP). Unfortunately, this MILP model turns out to be prohibitively expensive to solve even with state-of-the-art MILP solvers. We develop an alternative approach that is computationally tractable, and provide some early numerical experience with our new method.

Co-Authors: Prashant Palkar (IIT Bombay) and Jeffrey Larson and Stefan Wild (Argonne)