# US 2023/0267170 A1 · Information processing system, information processing method, and non-transitory computer-readable recording medium for information processing program

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

- Number: US 2023/0267170 A1
- Document ID: US20230267170A1
- Status: Published application
- Kind: A1
- Application number: 17/901,923
- Filed: 2022-09-02
- Published: 2023-08-24
- Earliest claimed: 2022-02-18
- Assignees: Hitachi, Ltd.
- Applicants: Hitachi, Ltd.
- Inventors: Takuya OKUYAMA
- Web page: https://patentgrep.com/patent/US20230267170A1

## CPC

- G06F 17/12: Simultaneous equations {, e.g. systems of linear equations}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- 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: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Search for an optimal solution of a constrained optimization problem that includes search for a ground state of an interaction model is sufficiently executed. An information processing system executes a first search process of performing search for an optimal solution of a first variable vector that optimizes an augmented Lagrange function in an alternating direction method of multipliers, using an optimization algorithm of an unconstrained mixed-binary quadratic programming problem, and a second search process of performing search for an optimal solution of a second variable vector that optimizes the augmented Lagrange function in the alternating direction method of multipliers, using another algorithm. The information processing system repeatedly executes the second search process performed using the optimal solution of the first variable vector determined by the first search process and the first search process performed using the optimal solution of the second variable vector determined by the second search process.

## Claims

### Claim 1

An information processing system for performing search for an optimal solution of a constrained mixed-binary quadratic programming problem, the information processing system comprising a processing unit executing a process in cooperation with a storage unit, wherein
the processing unit executes a conversion process of converting the constrained mixed-binary quadratic programming problem to an augmented Lagrange function that includes an objective function of the constrained mixed-binary quadratic programming problem, a constraint expression of the constrained mixed-binary quadratic programming problem and a penalty term based on the constraint expression, with a first variable vector and a second variable vector as variables;
executes a first search process of performing search for an optimal solution of the first variable vector that optimizes the augmented Lagrange function in an alternating direction method of multipliers, using a predetermined optimization algorithm of an unconstrained mixed-binary quadratic programming problem, and a second search process of performing search for an optimal solution of the second variable vector that optimizes the augmented Lagrange function in the alternating direction method of multipliers, using another algorithm different from the predetermined optimization algorithm; and
repeatedly executes the second search process performed using the optimal solution of the first variable vector determined by the first search process and the first search process performed using the optimal solution of the second variable vector determined by the second search process.

### Claim 2 (depends on 1)

The information processing system according to claim 1, wherein
the predetermined optimization algorithm is an algorithm including:
a conversion process of converting the unconstrained mixed-binary quadratic programming problem to a quadratic programming problem indicated by an objective function that includes a product of a first state variable vector, a predetermined matrix and a second state variable vector; and
a state update process of performing stochastic update of the first state variable vector and the second state variable vector by repeating a process of calculating a first vector by multiplying the predetermined matrix and the first state variable vector, performing stochastic update of the second state variable vector based on a stochastic distribution that includes a parameter based on the first vector, calculating a second vector by multiplying the predetermined matrix and the second state variable vector and performing stochastic update of the first state variable vector based on a stochastic distribution that includes a parameter based on the second vector; and
the other algorithm is a continuous optimization algorithm.

### Claim 3 (depends on 1)

The information processing system according to claim 1, wherein
the processing unit searches for feasible optimal solution candidates of the constrained mixed-binary quadratic programming problem based on the optimal solution of the first variable vector and the optimal solution of the second variable vector, using a local solution search algorithm; and
newly searches for an optimal solution of the first variable vector and an optimal solution of the second variable vector using the feasible optimal solution candidates, in the first search process and the second search process.

### Claim 4 (depends on 3)

The information processing system according to claim 3, wherein
the processing unit searches for such feasible optimal solution candidates of the first variable vector and feasible optimal solution candidates of the second variable vector that a distance between the optimal solution of the first variable vector and the optimal solution of the second variable vector is the shortest, within a range of observing the constraint expression.

### Claim 5 (depends on 3)

The information processing system according to claim 3, wherein
the processing unit searches for such feasible optimal solution candidates of the first variable vector and feasible optimal solution candidates of the second variable vector that a weighted sum of a distance between the optimal solution of the first variable vector and the optimal solution of the second variable vector and the objective function of the constrained mixed-binary quadratic programming problem is minimized, within a range of observing the constraint expression.

### Claim 6 (depends on 3)

The information processing system according to claim 3, wherein
the processing unit updates a Lagrange multiplier of the augmented Lagrange function based on the optimal solution of the first variable vector and the optimal solution of the second variable vector; and
executes the first search process and the second search process for the augmented Lagrange function to which the updated Lagrange multiplier is applied, to newly search for an optimal solution of the first variable vector and an optimal solution of the second variable vector.

### Claim 7 (depends on 6)

The information processing system according to claim 6, wherein
the processing unit repeatedly executes the first search process and the second search process while updating the Lagrange multiplier and the feasible optimal solution candidates until a predetermined end condition is satisfied.

### Claim 8

An information processing method executed by an information processing system, the information processing system being for performing search for an optimal solution of a constrained mixed-binary quadratic programming problem, wherein
in cooperation with a storage unit, an information processing unit of the information processing system
executes a conversion process of converting the constrained mixed-binary quadratic programming problem to an augmented Lagrange function that includes an objective function of the constrained mixed-binary quadratic programming problem, a constraint expression of the constrained mixed-binary quadratic programming problem and a penalty term based on the constraint expression, with a first variable vector and a second variable vector as variables;
executes a first search process of performing search for an optimal solution of the first variable vector that optimizes the augmented Lagrange function in an alternating direction method of multipliers, using a predetermined optimization algorithm of an unconstrained mixed-binary quadratic programming problem, and a second search process of performing search for an optimal solution of the second variable vector that optimizes the augmented Lagrange function in the alternating direction method of multipliers, using another algorithm different from the predetermined optimization algorithm; and
repeatedly executes the second search process performed using the optimal solution of the first variable vector determined by the first search process and the first search process performed using the optimal solution of the second variable vector determined by the second search process.

### Claim 9

A non-transitory computer-readable recording medium for storing a program for causing a computer to execute a process for performing search for an optimal solution of a constrained mixed-binary quadratic programming problem, the process comprising:
converting the constrained mixed-binary quadratic programming problem to an augmented Lagrange function that includes an objective function of the constrained mixed-binary quadratic programming problem, a constraint expression of the constrained mixed-binary quadratic programming problem and a penalty term based on the constraint expression, with a first variable vector and a second variable vector as variables;
first searching for an optimal solution of the first variable vector that optimizes the augmented Lagrange function in an alternating direction method of multipliers, using a predetermined optimization algorithm of an unconstrained mixed-binary quadratic programming problem; and
second searching for an optimal solution of the second variable vector that optimizes the augmented Lagrange function in the alternating direction method of multipliers, using another algorithm different from the predetermined optimization algorithm;
wherein the second searching using the optimal solution of the first variable vector determined by the first searching and the first searching using the optimal solution of the second variable vector determined by the second searching are repeatedly executed.

### Claim 10 (depends on 9)

The non-transitory computer-readable recording medium according to claim 9, wherein
the predetermined optimization algorithm is an algorithm including:
a conversion process of converting the unconstrained mixed-binary quadratic programming problem to a quadratic programming problem indicated by an objective function that includes a product of a first state variable vector, a predetermined matrix and a second state variable vector; and
a state update process of performing stochastic update of the first state variable vector and the second state variable vector by repeating a process of calculating a first vector by multiplying the predetermined matrix and the first state variable vector, performing stochastic update of the second state variable vector based on a stochastic distribution that includes a parameter based on the first vector, calculating a second vector by multiplying the predetermined matrix and the second state variable vector and performing stochastic update of the first state variable vector based on a stochastic distribution that includes a parameter based on the second vector; and
the other algorithm is a continuous optimization algorithm.

### Claim 11 (depends on 9)

The non-transitory computer-readable recording medium according to claim 9, wherein
feasible optimal solution candidates of the constrained mixed-binary quadratic programming problem based on the optimal solution of the first variable vector and the optimal solution of the second variable vector are searched for using a local solution search algorithm, and
a new optimal solution of the first variable vector and a new optimal solution of the second variable vector are searched for using the feasible optimal solution candidates in the first searching and the second searching.

### Claim 12 (depends on 11)

The non-transitory computer-readable recording medium according to claim 11, wherein
such feasible optimal solution candidates of the first variable vector and feasible optimal solution candidates of the second variable vector are searched for that a distance between the optimal solution of the first variable vector and the optimal solution of the second variable vector is the shortest within a range of observing the constraint expression.

### Claim 13 (depends on 11)

The non-transitory computer-readable recording medium according to claim 11, wherein
such feasible optimal solution candidates of the first variable vector and feasible optimal solution candidates of the second variable vector are searched for that a weighted sum of a distance between the optimal solution of the first variable vector and the optimal solution of the second variable vector and the objective function of the constrained mixed-binary quadratic programming problem is minimized within a range of observing the constraint expression.

### Claim 14 (depends on 11)

The non-transitory computer-readable recording medium according to claim 11, wherein
a Lagrange multiplier of the augmented Lagrange function is updated based on the optimal solution of the first variable vector and the optimal solution of the second variable vector, and
a new optimal solution of the first variable vector and a new optimal solution of the second variable vector are searched for in the first searching and the second searching for the augmented Lagrange function to which the updated Lagrange multiplier is applied.

### Claim 15 (depends on 14)

The non-transitory computer-readable recording medium according to claim 14, wherein
the first searching and the second searching are repeated while updating the Lagrange multiplier and the feasible optimal solution candidates until a predetermined end condition is satisfied.
