OPTIMIZATION APPARATUS, METHOD IMPLEMENTED BY OPTIMIZATION APPARATUS, AND NON-TRANSITORY COMPUTER-READABLE STORAGE MEDIUM FOR STORING PROGRAM

• US 20200133988A1
• Filed: 09/12/2019
• Published: 04/30/2020
• Est. Priority Date: 10/24/2018
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Konoshima, Makiko, Ohkubo, Jun
• Granted Patent: US 11,443,012 B2
• Time in Patent Office: Days
• CPC Class Codes: A61N 5/103 Treatment planning systems
• CPC Class Codes: A61N 5/1045 using a multi-leaf collimator, e.g. for intensity modulated radiation therapy or IMRT
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/047 Probabilistic or stochastic networks
• CPC Class Codes: G06N 3/063 using electronic means
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

An optimization apparatus includes: a memory; and a processor coupled to the memory, the processor being configured to (a): execute transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “Legendre transformation,” “Lagrange function,” and “Wolfe'"'"'s duality theorem,” (b): execute binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function, (c): execute Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and (d): execute reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.

Claims

1. An optimization apparatus comprising:

a memory; and

a processor coupled to the memory, the processor being configured to execute transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “

Legendre transformation,”

“

Lagrange function,” and

“

Wolfe'"'"'s duality theorem,”

execute binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function,

execute Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and

execute reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.

2. The optimization apparatus according to claim 1,

wherein the transformation processing is configured to

carry out Legendre transformation regarding a discontinuous function included in the first cost function, and

carry out transformation to the second cost function by incorporating a first function into the first cost function instead of the discontinuous function;

the first function being a function obtained through finding a dual problem based on “

Wolfe'"'"'s duality theorem”

on basis of an expression after the Legendre transformation.

3. A method implemented by an optimization apparatus, the method comprising:

executing transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “

Legendre transformation,”

“

Lagrange function,” and

“

Wolfe'"'"'s duality theorem,”

executing binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function,

executing Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and

executing reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.

4. The method according to claim 3,

wherein the transformation processing is configured to

carry out Legendre transformation regarding a discontinuous function included in the first cost function, and

carry out transformation to the second cost function by incorporating a first function into the first cost function instead of the discontinuous function;

the first function being a function obtained through finding a dual problem based on “

Wolfe'"'"'s duality theorem”

on basis of an expression after the Legendre transformation.

5. A non-transitory computer-readable storage medium for storing a program which causes a processor to perform processing, the processing comprising:

executing transformation processing that includes transforming an input first cost function to a second cost function by using at least any one of “

Legendre transformation,”

“

Lagrange function,” and

“

Wolfe'"'"'s duality theorem,”

executing binary expansion processing that includes acquiring values in an Ising format by carrying out binary expansion for values relating to coefficients of the second cost function,

executing Ising machine processing that includes seeking values that represent a ground state regarding the values in the Ising format relating to the coefficients of the second cost function, and

executing reverse binary expansion processing that includes acquiring values that minimize the first cost function by carrying out reverse binary expansion for the sought values that represent the ground state.

6. The non-transitory computer-readable storage medium according to claim 5,

wherein the transformation processing is configured to

carry out Legendre transformation regarding a discontinuous function included in the first cost function, and

carry out transformation to the second cost function by incorporating a first function into the first cost function instead of the discontinuous function;

the first function being a function obtained through finding a dual problem based on “

Wolfe'"'"'s duality theorem”

on basis of an expression after the Legendre transformation.