Complémentarité linéaire

Résumé

En mathématiques, et plus spécialement en recherche opérationnelle et en optimisation, un problème de complémentarité linéaire est défini par la donnée d'une matrice M\in\R^{n\times n} et d'un vecteur q\in\R^n et consiste à trouver un vecteur x\in\R^n tel que ses composantes et celles de y:=Mx+q soient positives et tel que x et y soient orthogonaux pour le produit scalaire euclidien de \R^n : x\geqslant 0,\qquad Mx+q\geqslant 0 \qquad\mbox{et}\qquad x^{!\top}(Mx+q)=0, où x^{\top} désigne le vecteur x transposé. Ce problème peut être vu comme un cas particulier d'inéquation variationnelle. Ces problèmes sont souvent NP-difficiles et donc difficiles à résoudre lorsque la dimension n du problème devient grande. La combinatoire du problème vient du fait qu'il faut déterminer quelles sont les composantes de la solution qui sont nulles et il y a

Source officielle

https://fr.wikipedia.org/wiki/Compl%C3%A9mentarit%C3%A9_lin%C3%A9aire

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (5)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (1)

Concepts associés

Chargement

Cours associés (3)

Cours associés

Chargement

Séances de cours associées (7)

Séances de cours associées

Chargement

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

Chargement

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

Chargement

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

Chargement