# US 2022/0027435 A1 · Optimization device, optimization method, and non-transitory computer-readable storage medium for storing optimization program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0027435 A1
- Document ID: US20220027435A1
- Status: Published application
- Kind: A1
- Application number: 17/225,167
- Filed: 2021-04-08
- Published: 2022-01-27
- Earliest claimed: 2020-07-21
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Jiyunichi Iwata; Mari Ohfuchi
- Web page: https://patentgrep.com/patent/US20220027435A1

## CPC

- 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)}
- G06F 17/17: Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method ({G06F17/18 takes precedence } ; interpolation for numerical control G05B19/18)
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 10/00: Quantum computing, i.e. information processing based on quantum-mechanical phenomena
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

An optimization device is configured to perform an iteration processing until a predetermined condition is satisfied, the iteration processing including: processing of generating a quadratic function that is approximate to an objective function within a predetermined range from a first reference value that indicates a value of a variable of the objective function; processing of calculating a second reference value that indicates a value of the variable by seeking for an extreme value of the quadratic function; processing of calculating a third reference value that indicates a value of the variable based on the second reference value and the first reference value; and processing of updating the first reference value based on the third reference value, the predetermined condition being a condition regarding a distance between the first reference value and the second reference value or a distance between the first reference value and the third reference value.

## Claims

### Claim 1

An optimization device comprising:
memory; and
processor circuitry coupled to the memory, the processor circuitry being configured to perform processing, the processing including:
performing an iteration processing until a predetermined condition is satisfied, the iteration processing including: processing of generating a quadratic function that is approximate to an objective function within a predetermined range from a first reference value that indicates a value of a variable of the objective function; processing of calculating a second reference value that indicates a value of the variable by seeking for an extreme value of the quadratic function; processing of calculating a third reference value that indicates a value of the variable based on the second reference value and the first reference value; and processing of updating the first reference value based on the third reference value, the predetermined condition being a condition regarding a distance between the first reference value and the second reference value or a distance between the first reference value and the third reference value; and
in response that the predetermined condition is satisfied, outputting the first reference value as a value of the variable that makes the objective function have an extreme value.

### Claim 2 (depends on 1)

The optimization device according to claim 1, wherein the third reference value is a value between the second reference value and the first reference value.

### Claim 3 (depends on 1)

The optimization device according to claim 1, wherein the processing of calculating a second reference value is performed by causing an Ising machine to seek for an extreme value of the quadratic function in order to calculate the second reference value by using a result of seeking for an extreme value of the quadratic function.

### Claim 4 (depends on 1)

The optimization device according to claim 1, wherein the predetermined condition is configured to be satisfied in case where the distance between the first reference value and the second reference value or the distance between the first reference value and the third reference value becomes equal to or smaller than a threshold value.

### Claim 5 (depends on 1)

The optimization device according to claim 1, wherein a width of the predetermined range from the first reference value is updated based on a distance between the first reference value before update and the first reference value after the update.

### Claim 6 (depends on 1)

The optimization device according to claim 1, wherein the processing of updating is configured to:
calculate a first function value that is a value of the objective function in case where a value of the variable is set to the second reference value;
calculate a second function value that is a value of the objective function in case where a value of the variable is set to the third reference value; and
update the first reference value to the second reference value or the third reference value based on a magnitude relationship between the first function value and the second function value.

### Claim 7

An optimization method performed by a computer, the method comprising:
performing an iteration processing until a predetermined condition is satisfied, the iteration processing including: processing of generating a quadratic function that is approximate to an objective function within a predetermined range from a first reference value that indicates a value of a variable of the objective function; processing of calculating a second reference value that indicates a value of the variable by seeking for an extreme value of the quadratic function; processing of calculating a third reference value that indicates a value of the variable based on the second reference value and the first reference value; and processing of updating the first reference value based on the third reference value, the predetermined condition being a condition regarding a distance between the first reference value and the second reference value or a distance between the first reference value and the third reference value; and
in response that the predetermined condition is satisfied, outputting the first reference value as a value of the variable that makes the objective function have an extreme value.

### Claim 8

A non-transitory computer-readable storage medium for storing an optimization program which causes a processor to perform processing, the processing comprising:
performing an iteration processing until a predetermined condition is satisfied, the iteration processing including: processing of generating a quadratic function that is approximate to an objective function within a predetermined range from a first reference value that indicates a value of a variable of the objective function; processing of calculating a second reference value that indicates a value of the variable by seeking for an extreme value of the quadratic function; processing of calculating a third reference value that indicates a value of the variable based on the second reference value and the first reference value; and processing of updating the first reference value based on the third reference value, the predetermined condition being a condition regarding a distance between the first reference value and the second reference value or a distance between the first reference value and the third reference value; and
in response that the predetermined condition is satisfied, outputting the first reference value as a value of the variable that makes the objective function have an extreme value.
