lcp_lemke

Contain a Numba-jitted linear complementarity problem (LCP) solver based on Lemke’s algorithm.

class quantecon.optimize.lcp_lemke.LCPResult(z, success, status, num_iter)

Bases: tuple

namedtuple containing the result from lcp_lemke.

Methods

`count`(value, /)	Return number of occurrences of value.
`index`(value[, start, stop])	Return first index of value.

num_iter

status

success

z

quantecon.optimize.lcp_lemke.lcp_lemke(M, q, d=None, max_iter=1000000, piv_options=PivOptions(fea_tol=1e-06, tol_piv=1e-07, tol_ratio_diff=1e-13), tableau=None, basis=None, z=None)[source]

Solve the linear complementarity problem:

z >= 0
M @ z + q >= 0
z @ (M @ z + q) = 0

by Lemke’s algorithm (with the lexicographic pivoting rule).

Parameters:

Mndarray(float, ndim=2)

ndarray of shape (n, n).

qndarray(float, ndim=1)

ndarray of shape (n,).

dndarray(float, ndim=1), optional

Covering vector, ndarray of shape (n,). Must be strictly positive. If None, default to vector of ones.

max_iterint, optional(default=10**6)

Maximum number of iteration to perform.

piv_optionsPivOptions, optional

PivOptions namedtuple to set the following tolerance values:

fea_tolfloat
Feasibility tolerance (default=1e-06). (Not used in this function.)

tol_pivfloat
Pivot tolerance (default=1e-07).

tol_ratio_difffloat
Tolerance used in the the lexicographic pivoting (default=1e-13).

tableaundarray(float, ndim=2), optional

Temporary ndarray of shape (n, 2*n+2) to store the tableau. Modified in place.

basisndarray(int, ndim=1), optional

Temporary ndarray of shape (n,) to store the basic variables. Modified in place.

zndarray(float, ndim=1), optional

Output ndarray of shape (n,) to store the solution.

Returns:

resLCPResult

namedtuple consisting of the fields:

zndarray(float, ndim=1)
ndarray of shape (n,) containing the solution.

successbool
True if the algorithm succeeded in finding a solution.

statusint
An integer representing the exit status of the result:
0 : Solution found successfully
1 : Iteration limit reached
2 : Secondary ray termination
num_iterint
The number of iterations performed.

References

K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, 1988.

Examples

>>> M = np.array([[1, 0, 0], [2, 1, 0], [2, 2, 1]])
>>> q = np.array([-8, -12, -14])
>>> res = lcp_lemke(M, q)
>>> res.success
True
>>> res.z
array([8., 0., 0.])
>>> w = M @ res.z + q
>>> w
array([0., 4., 2.])
>>> res.z @ w
0.0