Short-Term Scientific Mission

Empirical Drift Analysis for Mixed-Integer Optimization

Main theme: Mixed Continuous and Discrete Optimisation
Grantee: Stephan Frank, Ruhr-Universität Bochum, Bochum, Germany
Host: Youhei Akimoto, University of Tsukuba, Tsukuba, Japan

Start date: 2025-05-01
End date: 2025-05-30
Awarded: 2025-04-04
Report approved: 2025-06-30

Description

While drift analysis is a well-established tool in the discrete domain and in its early stages for continuous optimization, its application to mixed-integer algorithms remains unexplored. Existing potential function candidates have been proposed for the continuous case, but their adaptation and analytical provability for mixed-integer settings require further study. This STSM focuses on extending empirical drift analysis to mixed-integer optimization by refining existing potential functions, introducing new candidates, and improving their theoretical foundations. The project aims to bridge the gap between empirical observations and analytical convergence guarantees, fostering collaboration and advancing theoretical insights for subsequent research efforts.

Achievements

This STSM advanced the empirical understanding of potential-based drift analysis for evolution strategies, focusing on the (μ,λ)-CMA-ES. Key achievements included the evaluation and refinement of candidate potential function terms to capture convergence behavior related to step-size adaptation and covariance matrix updates. The simulation framework was extended for greater flexibility and clarity in visualizing drift dynamics. These contributions support the development of theoretical tools for runtime analysis and lay the groundwork for analytical convergence proofs. The STSM also initiated a productive research collaboration, with a follow-up visit and joint publication already planned to continue this line of work.