web stats
 
   
 
Selected Development Project
 
Project Title

Black-box Optimization via Statistical Physics
以統計物理優化黑箱系統
 
Principal Investigator Dr Bill Yeung Chi-ho
 
Area of Research Project
Science and Environmental Studies
 
Project Period
From 1/1/2018 To 31/12/2020
Objectives
  1. To establish a theoretical framework to analyze black-box optimization problems with statistical physics
  2. To develop an understanding of the effectiveness of different sampling strategies, and to identify the optimal sampling method subject to different black-box functions
  3. To reveal the relationship between the fitting stage and the optimization stage in conventional modeling-fitting-optimizing approaches of black-box optimization
  4. To map black-box optimization problems to spin glass and disordered systems, in order to understand their nature and describe their behavior under the framework of statistical physics
  5. To reveal the validity of coarse-grained (dimensionality reduced) black-box systems as representatives of the original systems
  6. To derive new physics-inspired and understanding-driven black-box optimization algorithms using all the above physical insights
Methods Used

In this project, we study black-box optimization problems, i.e. optimization problems with an unknown objective function, with mathematical models, computer simulations and theoretical analytic tools in statistical physics. We will apply tools from statistical physics to understand the effectiveness of various strategies in optimizing a black-box function, map black-box problems to spin glasses and disordered systems which are compatible with statistical physical tools, and use all the generated theoretical insights to improve and inform existing black-box optimization methods, and to devise new physics-inspired and understanding-driven algorithms for black-box optimization problems.
Summary of Findings
  • We have established a theoretical framework using the generating functional approach to analyse prototype problems with an unknown objective function
  • We studied a combinatorial optimization problem called the Strong Defensive Alliance problem; the optimal states of the problem are inaccessible by conventional algorithms such as simulated annealing, making the close-to-optimal regime a black-box to the optimization algorithms. We have introduced an algorithm to identify the optimal states of these systems
  • We have introduced an algorithm to identify slow-evolving variables in an optimization problem, by which one can obtain hints to identify highly-correlated variables to optimize black-box problems
Impact
  • The insights generated can improve our understanding on the optimization procedures of black-box optimization problems
  • The insights obtained can also help improve existing optimization approaches for black-box optimization problems, and to derive new physics-inspired algorithms for the problems
Selected Output
  1. Y. Z. Xu, C. H. Yeung, H.-J. Zhou, D Saad, Entropy Inflection and Inaccessible Low-Energy States: Defensive Alliance Example, Physical Review Letters 121 (21), 210602 (2018).
  2. J. Rocchi, D. Saad, C. H. Yeung, Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems, Physical Review E 97 (6), 062154 (2018).
Biography of Principal Investigator

Dr YEUNG Chi Ho Bill is an Associate Professor of Department of Science and Environmental Studies. Dr Yeung’s research interests include statistical physics, physics of disordered systems, interdisciplinary applications of statistical physics, optimization, models of complex systems, transportation networks, complex and social networks, recommender systems, deep learning, and STEM education.
Funding Source

General Research Fund