Synergistic Integration of Machine Learning and Mathematical Optimization for Difficult Optimization Problems

14 Apr 2022 06.00 PM - 07.00 PM Zoom: https://ntu-sg.zoom.us/j/87059071692 (Meeting ID: 870 5907 1692 Passcode: 123456) Public

Professor Peter Luh
Department of Electrical Engineering, National Taiwan University

Electrical and Computer Engineering, University of Connecticut

 

Chaired by Professor Su Rong
 
Co-organized by
EEE Centre for System Intelligence and Efficiency
IEEE Control Systems Society Singapore Chapter
 
 
Abstract: 
 
Many important optimization problems in manufacturing, power, communication and VLSI circuit design involve discrete decision variables.  Since derivatives of an objective function with respect to discrete decision variables do not exist, there is generally no necessary optimality condition.  As a result, partial enumeration of discrete variables is usually needed.  Consequently, the complexity to obtain an optimal solution increases exponentially as the problem size increases, limiting solution quality or the sizes of problems that can be practically solved.  Also, there is “no learning” in mathematical optimization – after a problem is solved by using an algorithm, to solve a slightly different problem, we usually start from ground zero.  Machine learning has been tried to solve such optimization problems indirectly, e.g., learning which constraints are inactive and can be removed from consideration, or which branches are most promising and should be explored first in a branch-and-bound process.  When machine learning is used to directly solve difficult optimization problems with discrete decision variables, success is generally limited to small to medium size problems.  This is because for large problems, (1) they require large training data sets in view of so many possible solutions (increases exponentially as the problem size increases); (2) good training data sets are hard to obtain since it takes time to have high quality solutions; and (3) training may require an excess amount of time in view of the above.  Furthermore, quality of solutions is difficult to quantify, and results are difficult to explain or justify. 
 

In this talk, a fundamental resolution of such problems is presented through a synergistic integration of machine learning and mathematical optimization for near-optimal solutions with quantifiable quality in a computationally efficient way.  The novelties include:  

  • a decomposition and coordination (D&C) framework to exploit the exponential reduction of complexity upon decomposition; 
  • a novel D&C method that overcomes major difficulties of traditional D&C approaches by requiring only “good enough” subproblem solutions but guaranteeing the dual solutions to converge to the optimal while providing lower bounds to the optimal cost to quantify solution quality; 
  • using machine learning to provide good enough subproblem solutions – much easier than to providing quality solutions to the original problem, within the iterative coordination processes; and
  • novel integration of supervised and unsupervised learning (the latter from both “good enough” and not “good enough” cases) for enhanced and streamlined offline/online learning.
In addition, by exploiting the fact that Lagrange multipliers are shadow prices, the results are partially explainable and justifiable.  The above ideas will be presented using unit commitment of power systems as the problem context.  Through the synergistic integration of mathematical optimization and offline/online machine learning, it is possible to provide near-optimal solutions with quantifiable quality in a computationally efficient way for important and difficult problems of practical sizes.  
 
 
Speaker: 
 
Prof. Peter Luh received his BSEE from National Taiwan University in 1973, M.S. in Aeronautics and Astronautics from M.I.T. in 1977, and Ph.D. in Applied Mathematics from Harvard University in 1980.  He was with the University of Connecticut from 1980 to 2020, and was a Board of Trustees Distinguished Professor and the SNET Professor of Communications & Information Technologies upon retirement on January 1, 2021.  He is now a Distinguished Chair Professor and a Yushan Scholar at the Department of Electrical Engineering at the National Taiwan University.  Professor Luh is a Life Fellow of IEEE, was the Chair of IEEE TAB Periodicals Committee (2018-19) overseeing 200 IEEE journals and magazines from cradle to grave, and the Chair of IEEE TAB Periodicals Review and Advisory Committee (2020-21).  He was the VP of Publications of IEEE Robotics and Automation Society (RAS, 2008-2011); the founding Editor-in-Chief of the IEEE Transactions on Automation Science and Engineering (T-ASE, 2003-2007); and an Editor-in-Chief of IEEE Transactions on Robotics and Automation (1999-2003).  He was also a Co-Founder of the IEEE Conferences on Automation Science and Engineering, and the Founding Chair of its Steering Committee (2006-2011).  He is now a member-at-large of the IEEE Publication Services and Products Board (-2024), and the Chair of its Publishing Conduct Committee.  His research interests include smart grid, intelligent manufacturing, and energy-smart buildings with optimization cutting across them all.  He received RAS 2013 Pioneer Award, RAS 2017 George Saridis Leadership Award, and IEEE T-ASE 2019 Best Paper Award.  
 

Categories