McCormick Envelopes for Mixed-integer PDE-constrained Optimization

• Applicant: Professor Dr. Paul Manns
• Subject Area: Mathematics
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 540198933

The proposed project is concerned with optimization problems that feature discrete-valued decision variables and are constrained by partial differential equations (PDEs). Such problems are notoriously hard to solve because they combine the curse of dimensionality that may arise in discrete and combinatorial optimization with the large number of variables that arises from discretizing the computational domain of the underlying PDE. A particular challenge that has not been dedicated much research to is to derive lower bounds for such problems if the underlying PDE is nonlinear and thus the continuous relaxation of the optimization problem is nonconvex. In this project, we consider structured nonlinearities in the PDE, specifically a bilinear coupling of state and control variables. An optimization problem that is based on a Helmholtz equation serves as a model problem for our project. We derive convex relaxations by transferring so-called McCormick envelopes from finite-dimensional discrete optimization to our infinite-dimensional setting. Subsequently, we perform a discretization and an accompanying numerical analysis in order to be able to solve the McCormick envelopes approximately and in turn compute lower bounds for our problem class of interest. We also develop a means to tighten them. Finally, we integrate the lower bounds and their computations into an algorithmic framework for global optimization of the problem class of interest.

• DFG Programme: Research Grants
• International Connection: USA
• Cooperation Partner: Sven Leyffer, Ph.D.