次の 2 人ゼロサム ゲームのナッシュ均衡を計算するために cvxopt を使用しています。
[-5, 3, 1, 8]
[ 5, 5, 4, 6]
[-4, 6, 0, 5]
これが私が使用しているコードです(doctestを使用)。
from cvxopt import matrix, solvers
from cvxopt.modeling import op, dot, variable
import numpy as np
def solve_lp(a, b, c):
"""
>>> a = matrix([[-5., 3., 1., 8., 1.],
... [ 5., 5., 4., 6., 1.],
... [-4., 6., 0., 5., 1.],
... [-1.,-1.,-1.,-1., 0.],
... [ 1., 1., 1., 1., 0.],
... [-1., 0., 0., 0., 0.],
... [ 0.,-1., 0., 0., 0.],
... [ 0., 0.,-1., 0., 0.],
... [ 0., 0., 0.,-1., 0.]])
>>> b = matrix([0.,0.,0.,0.,1.])
>>> c = matrix([0.,0.,0., 1.,-1.,0.,0.,0.,0.])
>>> solve_lp(a, b, c)
"""
variables = c.size[0]
x = variable(variables, 'x')
eq = (a*x == b)
ineq = (x >= 0)
lp = op(dot(c, x), [eq, ineq])
lp.solve(solver='glpk')
return (lp.objective.value(), x.value)
実行すると、次のエラーが生成されます。
Traceback (most recent call last):
...
TypeError: 'G' must be a dense or sparse 'd' matrix with 9 columns
ineq
モデリング例の制約の構文に従っているように見えますが、cvxopt は制約に関する例外をスローしているようです。
これまでに試したこと
x
1 のベクトルを掛けてコードを変更します。
def solve_lp(a, b, c):
variables = c.size[0]
x = variable(variables, 'x')
e = matrix(1.0, (1, variables))
eq = (a*x == b)
ineq = (e*x >= 0)
lp = op(dot(c, x), [eq, ineq])
lp.solve(solver='glpk')
return (lp.objective.value(), x.value)
少なくとも GLPK に到達すると、次のエラーが発生します。
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 8.000e+00 ratio = 8.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 6
* 0: obj = 0.000000000e+00 infeas = 0.000e+00 (0)
PROBLEM HAS UNBOUNDED SOLUTION
glp_simplex: unable to recover undefined or non-optimal solution
これを修正するにはどうすればよいですか?