INFORMATION PROCESSING SYSTEM, INFORMATION PROCESSING METHOD, AND NON-TRANSITORY COMPUTER-READABLE RECORDING MEDIUM FOR INFORMATION PROCESSING PROGRAM
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.
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.
2 . 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.
3 . 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.
4 . 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.
5 . 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.
6 . 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.
7 . 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.
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.
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.
10 . 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.
11 . 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.
12 . 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.
13 . 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.
14 . 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.
15 . 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.