Tensor method improves search for valid solutions in discrete optimization
Constraint-Aware Discrete Black-Box Optimization Using Tensor Decomposition
Machine Learning
Summary
Many problems require finding the best choice from a list of options, but not all options are allowed because of certain rules. Existing methods struggle to learn these rules and avoid impossible choices. The authors introduce a new mathematical model that better understands these rules while searching, making the search more efficient. They tested it on examples including designing a pressure vessel and showed it helps find good, allowed options faster.
What this means in practice
- •For engineering design teams: Optimize design parameters efficiently while meeting complex logical constraints, such as in pressure vessel manufacturing.
- •For automated configuration teams: Guide search procedures to quickly find feasible configurations subject to many logical rules in software or hardware setups.
Authors
Keisuke Onoue, Ryosuke Kojima
Abstract
Discrete black-box optimization is often addressed using approaches such as Sequential Model-Based Optimization (SMBO), which aims to improve sample efficiency by fitting surrogate models that approximate a costly objective function over a discrete search space. In many real-world problems, the set of feasible inputs is often given by logical constraints known in advance. However, existing surrogate modeling techniques generally fail to capture the symbolic rules governing feasibility in discrete input spaces. In this paper, we propose a surrogate modeling approach based on tensor decomposition that captures the structure of discrete search spaces while directly integrating feasibility information. To implement this approach, we formulate surrogate model training as a constrained polynomial optimization problem and solve a relaxed formulation using a differentiable penalty term derived from T-norms. Our experiments on both synthetic and real-world benchmarks, including a pressure vessel design task, demonstrate that the proposed method improves sample efficiency by effectively guiding the search away from infeasible regions.