Linear complementarity problem

In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968. Formulation Given a real matrix M and vector q, the linear complementarity problem LCP(q, M) seeks vectors z and w which satisfy the following constraints:

w, z \geqslant 0, (that is, each component of these two vectors is non-negative)
z^Tw = 0 or equivalently \sum\nolimits_i w_i z_i = 0. This is the complementarity condition, since it implies that, for all i, at most one of w_i and z_i can be positive.
w = Mz + q

A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite. If M is such that LCP(q, M) has a solution for every q, then M is a Q-matrix. If M is such that LCP

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (5)

Related publications

Related people

Related units

Related concepts (1)

Related concepts

Related courses (3)

Related courses

Related lectures (7)

Related lectures

EP theorems and linear complementary problems

Let A be a rational n × n square matrix and b be a rational n-vector for some positive integer n. The linear complementarity problem (abbreviated by LCP) is to find a vector (x, y) in R^(2n) satisfying y = Ax + b (x, y) >= 0 and the complementarity condition: xi yi = 0 for all i = 1 ,... , n. The LCP is known to be NP-complete, but there are some known classes of matrices A for which the LCP is polynomially solvable, for example the class of positive semi-definite (PSD-) matrices. In this paper, we study the LCP from the view point of EP (existentially polynomial time) theorems due to Cameron and Edmonds. In particular, we investigate the LCP duality theorem of Fukuda and Terlaky in EP form, and show that this immediately yields a simple modification of the criss- cross method with a nice practical feature. Namely, this algorithm can be applied to any given A and b, and terminates in one of the three states: (1) a solution x is found; (2) a solution to the dual LCP is found (implying the nonexistence of a solution to the LCP); or (3) a succinct certificate is given to show that the input matrix A is not “sufficient”. Note that all PSD-matrices and P- matrices are sufficient matrices.

1998

The existence of a short sequence of admissible pivots to an optimal basis in LP and LCP

We say an LP (linear programming) is fully nondegenerate if both the primal and the dual problems are nondegenerate. In this paper, we prove the existence of a sequence of |B∖B| admissible pivot from any basis B (not necessarily feasible) to the unique optimal basis B, if the given LP has an optimal solution and is fully nondegenerate. Here admissible pivots are those pivots (satisfying certain sign conditions) that exist if the current LP dictionary is not terminal, i.e., neither optimal, inconsistent nor dual inconsistent. A natural extension of the result to LCPs (linear complementarity problems) with sufficient matrices is given. The existence itself does not yield a strongly polynomial pivot algorithm for LPs but provides us with a good motivation to study the class of admissible pivot methods for LPs, as opposed to the narrower class of simplex methods for which the shortest sequence of pivots is not known to be polynomially bounded.

1997

On extremal behaviors of Murty's least index method

In this small note, we observe some extremal behaviors of Murty's least index method for solving linear complementarity problems. In particular, we show that the expected number of steps for solving Murty's exponential example with a random permutation of variable indices is exactly equal to n, where n is the size of the input square matrix.

1994

Simplex algorithm

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and wa

ME-454: Modelling and optimization of energy systems

The goal of the lecture is to present and apply techniques for the modelling and the thermo-economic optimisation of industrial process and energy systems. The lecture covers the problem statement, the solving methods for the simulation and the single and multi-objective optimisation problems.

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

FIN-472: Computational finance

Participants of this course will master computational techniques frequently used in mathematical finance applications. Emphasis will be put on the implementation and practical aspects.