0

次の 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 は制約に関する例外をスローしているようです。

これまでに試したこと

x1 のベクトルを掛けてコードを変更します。

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

これを修正するにはどうすればよいですか?

4

1 に答える 1

0

この Web ページの glpk ソルバーの使用法に従うべきだと思います: https://github.com/benmoran/L1-Sudoku/blob/master/sudoku.py

これに正確に従ってください。この glpk ソルバーを修正して正しく使用します...

def solve_plain_l1(A, b, solver='glpk'):

'''Find x with min l1 such that Ax=b,
using plain L1 minimization'''

n = A.size[1]

c0 = ones_v(2*n)

G1 = concathoriz(A,-A) # concatenate horizontally
G2 = concathoriz(-A,A)
G3 = -eye(2*n)
G = reduce(concatvert, [G1,G2,G3]) # concatenate vertically
hh = reduce(concatvert, [b, -b, zeros_v(2*n)])

u = cvxopt.solvers.lp(c0, G, hh, solver=solver)

v = u['x'][:n]

return v
于 2013-11-19T10:58:55.520 に答える