OPTIMIZATION METHOD AND INFORMATION PROCESSING APPARATUS
An object is to efficiently solve a quadratic programming problem having a k-hot constraint (k is a positive integer) for binary variables. A preferred aspect of the invention is an optimization method for, using an information processing apparatus, solving a quadratic programming problem in which one or more independent k-hot constraints are imposed on binary variables, the information processing apparatus including a processor, a storage device, an input device, and an output device. The information processing apparatus relaxes the binary variables into continuous values by adding correction values to a nonlinear coefficients of the binary variables on which the k-hot constraints are imposed, and the information processing apparatus executes a solution search while satisfying the k-hot constraints by executing a state transition such that a sum of a set of continuous variables on which the k-hot constraint is imposed is constant.
1 . An optimization method for, using an information processing apparatus, solving a quadratic programming problem in which one or more independent k-hot constraints (k is a positive integer) are imposed on binary variables, the information processing apparatus including a processor, a storage device, an input device, and an output device, wherein
the information processing apparatus relaxes the binary variables into continuous values by adding a correction values to nonlinear coefficients of the binary variables on which the k-hot constraints are imposed, and
the information processing apparatus executes a solution search while satisfying the k-hot constraints by executing state transitions such that a sum of a set of continuous variables on which the k-hot constraint is imposed is constant.
2 . The optimization method according to claim 1 , wherein
the correction value of the nonlinear coefficient of the binary variables on which the k-hot constraint is imposed is determined based on an eigenvalue of a principal submatrix obtained by the information processing apparatus extracting the nonlinear coefficients between the binary variables on which the k-hot constraint is imposed.
3 . The optimization method according to claim 1 , wherein
the information processing apparatus stores two variable groups x and y each having N variables, stores an N-dimensional real symmetric matrix J defined by the nonlinear coefficients and a vector h defined by a linear coefficient between the variables of the quadratic programming problem, and calculates a connection strength w, which is determined based on information on an eigenvalue of the N-dimensional real symmetric matrix J, between an i-th variable pair x i , y i of the two variable groups.
4 . The optimization method according to claim 3 , wherein
the solution search is executed by executing a ground state search for an interaction model in which, between the two variable groups x and y, the N-dimensional real symmetric matrix J acts as an adjacent matrix, the vector h acts as a bias coefficient for x and y, and an undirected graph with x and y expressed as nodes is a complete bipartite graph structure.
5 . The optimization method according to claim 4 , wherein
the ground state search is executed by sequentially executing a state transition of the variables by a stochastic state transition according to an algorithm of simulated annealing.
6 . The optimization method according to claim 5 , wherein
the state transition is executed simultaneously for a plurality of variables belonging to the variable group x or Y,
a next state is stochastically determined by markov chain monte carlo methods such that variables on which the k-hot constraint is not imposed are independent and a sum of the variables on which the k-hot constraint is imposed is constant for a set of variables.
7 . The optimization method according to claim 1 , wherein
the quadratic programming problem is a mixed binary quadratic programming problem.
8 . The optimization method according to claim 1 , wherein
the information processing apparatus randomly determines the set of continuous value variables.
9 . The optimization method according to claim 1 , wherein
the information processing apparatus determines the set of continuous value variables such that changes in the variables in the state transition are equal to or greater than a predetermined threshold.
10 . An information processing apparatus including a processor, a storage device, an input device, an output device, and an arithmetic device, and for solving a quadratic programming problem in which one or more independent k-hot constraints (k is a positive integer) are imposed on binary variables, the information processing apparatus comprising:
an energy arithmetic execution unit configured to relax, into continuous values, the binary variables on which the k-hot constraints are imposed; and
a connection strength calculation unit configured to calculate a correction value to be added to a nonlinear coefficient of the binary variables on which the k-hot constraint is imposed, wherein
under control of the energy arithmetic execution unit, the arithmetic device executes a solution search while satisfying the k-hot constraint by executing a state transitions such that a sum of a set of continuous variables on which the k-hot constraint is imposed is constant.
11 . The information processing apparatus according to claim 10 , wherein
the connection strength calculation unit calculates the correction value of the nonlinear coefficient of the binary variables on which the k-hot constraint is imposed, based on an eigenvalue of a principal submatrix obtained by extracting the nonlinear coefficient between the binary variables on which the k-hot constraint is imposed.
12 . The information processing apparatus according to claim 11 , wherein
the arithmetic device is implemented by a semiconductor integrated circuit, and includes a variable memory configured to store two variable groups x and y each having N variables, and a nonlinear coefficient memory configured to store an N-dimensional real symmetric matrix J defined by the nonlinear coefficient between the variables of the quadratic programming problem, and
the connection strength calculation unit calculates, based on information on the nonlinear coefficient memory, a connection strength w, which is determined based on information on an eigenvalue of the N-dimensional real symmetric matrix J, between an i-th variable pair x i , y i of the two variable groups.
13 . The information processing apparatus according to claim 12 , wherein
the arithmetic device includes a linear coefficient memory configured to store a vector h that is a bias coefficient for x and y, and
the arithmetic device executes a ground state search for an interaction model in which, between the two variable groups x and y, the N-dimensional real symmetric matrix J acts as an adjacent matrix, the vector h acts on x and y, and an undirected graph with x and y expressed as nodes is a complete bipartite graph structure.
14 . The information processing apparatus according to claim 13 , wherein
the arithmetic device executes the ground state search by sequentially executing a state transition of the variables by a stochastic state transition according to an algorithm of simulated annealing.
15 . The information processing apparatus according to claim 14 , wherein
the state transition is executed simultaneously for a plurality of variables belonging to the variable group x or y,
a next state is stochastically determined by markov chain monte carlo methods such that variables on which the k-hot constraint is not imposed are independent and a sum of the variables on which the k-hot constraint is imposed is constant for a set of variables.