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 acquisi...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2022-04-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.4.023062 |
| _version_ | 1797210805680209920 |
|---|---|
| author | Syun Izawa Koki Kitai Shu Tanaka Ryo Tamura Koji Tsuda |
| author_facet | Syun Izawa Koki Kitai Shu Tanaka Ryo Tamura Koji Tsuda |
| author_sort | Syun Izawa |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-24T10:16:26Z |
| format | Article |
| id | doaj.art-9886eb803d044127bc6de8c3f03a019e |
| institution | Directory Open Access Journal |
| issn | 2643-1564 |
| language | English |
| last_indexed | 2024-04-24T10:16:26Z |
| publishDate | 2022-04-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj.art-9886eb803d044127bc6de8c3f03a019e2024-04-12T17:20:08ZengAmerican Physical SocietyPhysical Review Research2643-15642022-04-014202306210.1103/PhysRevResearch.4.023062Continuous black-box optimization with an Ising machine and random subspace codingSyun IzawaKoki KitaiShu TanakaRyo TamuraKoji TsudaA 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.http://doi.org/10.1103/PhysRevResearch.4.023062 |
| spellingShingle | Syun Izawa Koki Kitai Shu Tanaka Ryo Tamura Koji Tsuda Continuous black-box optimization with an Ising machine and random subspace coding Physical Review Research |
| title | Continuous black-box optimization with an Ising machine and random subspace coding |
| title_full | Continuous black-box optimization with an Ising machine and random subspace coding |
| title_fullStr | Continuous black-box optimization with an Ising machine and random subspace coding |
| title_full_unstemmed | Continuous black-box optimization with an Ising machine and random subspace coding |
| title_short | Continuous black-box optimization with an Ising machine and random subspace coding |
| title_sort | continuous black box optimization with an ising machine and random subspace coding |
| url | http://doi.org/10.1103/PhysRevResearch.4.023062 |
| work_keys_str_mv | AT syunizawa continuousblackboxoptimizationwithanisingmachineandrandomsubspacecoding AT kokikitai continuousblackboxoptimizationwithanisingmachineandrandomsubspacecoding AT shutanaka continuousblackboxoptimizationwithanisingmachineandrandomsubspacecoding AT ryotamura continuousblackboxoptimizationwithanisingmachineandrandomsubspacecoding AT kojitsuda continuousblackboxoptimizationwithanisingmachineandrandomsubspacecoding |