TY - JOUR
T1 - Fast Design Space Exploration of Nonlinear Systems
T2 - Part I
AU - Narain, Sanjai
AU - Mak, Emily
AU - Chee, Dana
AU - Englot, Brendan
AU - Pochiraju, Kishore
AU - Jha, Niraj K.
AU - Narayan, Karthik
N1 - Publisher Copyright:
© 1982-2012 IEEE.
PY - 2022/9/1
Y1 - 2022/9/1
N2 - System design tools are often only available as input-output blackboxes: for a given design as input, they compute an output representing system behavior. Blackboxes are intended to be run in the forward direction. This article presents a new method of solving the 'inverse design problem,' namely, given requirements or constraints on output, find an input that also optimizes an objective function. This problem is challenging for several reasons. First, blackboxes are not designed to be run in reverse. Second, inputs and outputs can be discrete and continuous. Third, finding designs concurrently satisfying a set of requirements is hard because designs satisfying individual requirements may conflict with each other. Fourth, blackbox evaluations can be expensive. Finally, evaluations can sometimes fail to produce an output due to nonconvergence of underlying numerical algorithms. This article presents CNMA, a new method of solving the inverse problem that overcomes these challenges. CNMA tries to sample only the part of the design space relevant to solving the inverse problem, leveraging the power of neural networks, mixed-integer linear programs, and a new learning-from-failure feedback loop. This article also presents a parallel version of CNMA that improves the efficiency and quality of solutions over the sequential version and tries to steer it away from local optima. CNMA's performance is evaluated against conventional optimization methods for seven nonlinear design problems of 8 (two problems), 10, 15, 36 and 60 real-valued dimensions and one with 186 binary dimensions. Conventional methods evaluated are stable, off-the-shelf implementations of the Bayesian optimization with the Gaussian Processes, Nelder-Mead, and Random Search. The first two do not even produce a solution for problems that are high dimensional, having both discrete and continuous variables or whose blackboxes fail to return values for some inputs. CNMA produces solutions for all problems. When conventional methods do produce solutions, CNMA improves upon their performance by 1%-87%.
AB - System design tools are often only available as input-output blackboxes: for a given design as input, they compute an output representing system behavior. Blackboxes are intended to be run in the forward direction. This article presents a new method of solving the 'inverse design problem,' namely, given requirements or constraints on output, find an input that also optimizes an objective function. This problem is challenging for several reasons. First, blackboxes are not designed to be run in reverse. Second, inputs and outputs can be discrete and continuous. Third, finding designs concurrently satisfying a set of requirements is hard because designs satisfying individual requirements may conflict with each other. Fourth, blackbox evaluations can be expensive. Finally, evaluations can sometimes fail to produce an output due to nonconvergence of underlying numerical algorithms. This article presents CNMA, a new method of solving the inverse problem that overcomes these challenges. CNMA tries to sample only the part of the design space relevant to solving the inverse problem, leveraging the power of neural networks, mixed-integer linear programs, and a new learning-from-failure feedback loop. This article also presents a parallel version of CNMA that improves the efficiency and quality of solutions over the sequential version and tries to steer it away from local optima. CNMA's performance is evaluated against conventional optimization methods for seven nonlinear design problems of 8 (two problems), 10, 15, 36 and 60 real-valued dimensions and one with 186 binary dimensions. Conventional methods evaluated are stable, off-the-shelf implementations of the Bayesian optimization with the Gaussian Processes, Nelder-Mead, and Random Search. The first two do not even produce a solution for problems that are high dimensional, having both discrete and continuous variables or whose blackboxes fail to return values for some inputs. CNMA produces solutions for all problems. When conventional methods do produce solutions, CNMA improves upon their performance by 1%-87%.
KW - Blackbox optimization
KW - constrained optimization
KW - mixed-integer linear program~(MILP)
KW - neural networks (NNs)
KW - optimization
KW - sample efficiency
UR - http://www.scopus.com/inward/record.url?scp=85106087201&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85106087201&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2021.3118963
DO - 10.1109/TCAD.2021.3118963
M3 - Article
AN - SCOPUS:85106087201
SN - 0278-0070
VL - 41
SP - 2970
EP - 2983
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 9
ER -