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.

Attributes:
num_iter
status
success
z

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