0

我正在使用 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

似乎 cvxopt 抛出了一个关于ineq约束的异常，即使我似乎遵循了建模示例中的约束语法。

到目前为止我尝试过的

通过乘以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

我认为您应该遵循此网页中 glpk 求解器的用法： https ://github.com/benmoran/L1-Sudoku/blob/master/sudoku.py

完全按照此操作，您将正确修复并使用此 glpk 求解器...

def solve_plain_l1（A，b，求解器='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 回答