Continuous black-box optimization with an Ising machine and random subspace coding

A black-box optimization algorithm such as Bayesian optimization finds the extremum of an unknown function by alternating the inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. Herein, we apply Ising machines to overcome the difficulty in the continuous black-box optimization. As an Ising machine specializes in optimization of binary problems, a continuous vector has to be encoded to binary, and the solution by Ising machines has to be translated back. Our method has the following three parts: (1) random subspace coding based on axis-parallel hyperrectangles from continuous vector to binary vector, (2) a quadratic unconstrained binary optimization (QUBO) defined by the acquisition function based on the nonnegative-weighted linear regression model, which is solved by Ising machines, and (3) a penalization scheme to ensure that the solution can be translated back. It is shown with benchmark tests that its performance using the D-Wave Advantage quantum annealer and simulated annealing is competitive with a state-of-the-art method based on the Gaussian process in high-dimensional problems. Our method may open up the possibility of Ising machines and other QUBO solvers, including a quantum approximate optimization algorithm using gated-quantum computers, and may expand its range of application to continuous-valued problems.

Figure 1

Software-based and hardware-assisted black-box optimization with continuous variables. To use special hardware, an appropriate encoder and decoder between continuous and binary states should be set.

Figure 2

(a) Surjective encoding for the two-dimensional case when two-dimensional hyperrectangles are used. If the continuous vector is included in the left blue hyperrectangle, the first bit is 1, while for the right red rectangle, the second bit becomes 1 if the continuous vector is located. (b) Nonsurjective encoding for the two-dimensional case. Vector 11 does not have a corresponding point. (c) Random subspace coding in the three-dimensional continuous space. Although each square is drawn on each plane, it extends in the vertical direction and forms a rectangular prism. The bits expressing the bold rectangle are 1, and the others are 0 for the red point's position.

Figure 3

Loss function $S_T$ depending on the number of iterations by random search, Add-GP, and CONBQA for the Hartmann-6 problem. CONBQA with the hybrid solver service in D-Wave Advantage (D-Wave hybrid) and that with simulated annealing perform better than CONBQA with D-Wave Advantage and that with greedy search. CONBQA with the hybrid solver or simulated annealing outperforms Add-GP based on UCB score and random search as well. Ten independent runs are performed, and the shaded region is the error.

Figure 4

Performance of CONBQA with 20, 60, and 100 bits in comparison to random search and AddGP with respect to three benchmark functions [$F_{12}$ (5D), $F_{11}$ (10D), and $F_{12}$ (10D)] [33]. Simulated annealing was used to solve the QUBO problems. Ten independent runs are performed, and the shaded region is the error.

Figure 5

Average size of the intersection of all rectangles enclosing a randomly chosen point for random subspace coding $R_I$ depending on the number of bits. Results for various dimensionalities of the problem $d$ are shown. The number of randomly chosen points is 50, and the shaded region is the error.

Figure 6

Ten visualized QUBO matrices randomly picked during the CONBQA runs on the Hartmann-6 function. The black (white) part has negative (positive) values, and the gray part has zeros. About one third of the lower triangular elements have finite positive values.

Figure 7

(a) Rate of chain breaks, (b) fraction of decodable solutions, and (c) fraction of decodable solutions after postprocessing depending on the chain strength and constraint strength for decodability.