Matriz Q0

Em matemática , uma -matriz é uma matriz quadrada real que fornece propriedades particulares para problemas de complementaridade linear . São eles que garantem a existência de uma solução tão logo o problema seja viável. Q0{\ displaystyle \ mathbf {Q_ {0}}}

Definições

Algumas notações

Para um vetor , a notação significa que todos os componentes do vetor são positivos. v∈Rnão{\ displaystyle v \ in \ mathbb {R} ^ {n}}v⩾0{\ displaystyle v \ geqslant 0}veu{\ displaystyle v_ {i}}

Denotamos o orthant positiva de . R+não: ={x∈Rnão:x⩾0}{\ displaystyle \ mathbb {R} _ {+} ^ {n}: = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0 \}}Rnão{\ displaystyle \ mathbb {R} ^ {n}}

Se for uma matriz de ordem , denotamos a imagem de por  ; é um cone poliédrico (portanto, fechado). NO{\ displaystyle A}não{\ displaystyle n}NO(R+não): ={NOx:x⩾0}{\ displaystyle A (\ mathbb {R} _ {+} ^ {n}): = \ {Ax: x \ geqslant 0 \}}R+não{\ displaystyle \ mathbb {R} _ {+} ^ {n}}NO{\ displaystyle A}

Problema de complementaridade

Dada uma matriz real quadrada e um vetor , um problema de complementaridade linear consiste em encontrar um vetor tal que , e , que é escrito de forma abreviada da seguinte forma: M∈Rnão×não{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}q∈Rnão{\ displaystyle q \ in \ mathbb {R} ^ {n}}x∈Rnão{\ displaystyle x \ in \ mathbb {R} ^ {n}}x⩾0{\ displaystyle x \ geqslant 0}Mx+q⩾0{\ displaystyle Mx + q \ geqslant 0}x⊤(Mx+q)=0{\ displaystyle x ^ {\! \ top} (Mx + q) = 0}

CL(M,q):0⩽x⊥(Mx+q)⩾0{\ displaystyle {\ mbox {CL}} (M, q): \ qquad 0 \ leqslant x \ perp (Mx + q) \ geqslant 0.}

Um ponto que verifica e é considerado admissível para o problema e o conjunto x{\ displaystyle x}x⩾0{\ displaystyle x \ geqslant 0}Mx+q⩾0{\ displaystyle Mx + q \ geqslant 0}CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}

Adm(M,q): ={x∈Rnão:x⩾0, Mx+q⩾0}{\ displaystyle {\ mbox {Adm}} (M, q): = \ {x \ in \ mathbb {R} ^ {n}: x \ geqslant 0, ~ Mx + q \ geqslant 0 \}}

é chamado de conjunto admissível desse problema. O problema é dito ser viável embora . CL(M,q){\ displaystyle {\ mbox {CL}} (M, q)}Adm(M,q)≠∅{\ displaystyle {\ mbox {Adm}} (M, q) \ neq \ varnothing}

Matriz Q0

Para , apresentamos os dois cones do seguinte M∈Rnão×não{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}Rnão{\ displaystyle \ mathbb {R} ^ {n}}

QR(M): ={q∈Rnão:CL⁡(M,q) é alcançável},QS(M): ={q∈Rnão:CL⁡(M,q) tem uma solução}.{\ displaystyle {\ begin {array} {rcl} Q_ {R} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {é viável}} \}, \\ Q_ {S} (M) &: = & \ {q \ in \ mathbb {R} ^ {n}: \ operatorname {CL} (M, q) ~ { \ mbox {tem uma solução}} \}. \ end {array}}}

Obviamente , sem necessariamente haver igualdade (é o que motiva a introdução da noção de -matriz). O cone é convexo poliédrico porque é escrito como a soma de dois cones convexos poliédricos: QS(M)⊂QR(M){\ displaystyle Q_ {S} (M) \ subconjunto Q_ {R} (M)}Q0{\ displaystyle \ mathbf {Q_ {0}}} QR(M){\ displaystyle Q_ {R} (M)}

QR(M)=R+não-M(R+não){\ displaystyle Q_ {R} (M) = R _ {+} ^ {n} -M (R _ {+} ^ {n})}.

Pelo contrário, não é necessariamente convexo. Na realidade, mostramos que é uma união de cones convexos poliédricos (disjuntos independentemente se e somente se for suficiente na coluna ): QS(M){\ displaystyle Q_ {S} (M)}QS(M){\ displaystyle Q_ {S} (M)}q{\ displaystyle q}M{\ displaystyle M}

QS(M)=⋃eu⊂{1,...,não}Keu(R+não){\ displaystyle Q_ {S} (M) = \ displaystyle \ bigcup _ {I \ subset \ {1, \ ldots, n \}} \, K_ {I} (\ mathbb {R} _ {+} ^ {n })},

onde está a matriz cujas colunas são dadas por Keu{\ displaystyle K_ {I}}

(Keu)eu=-Meue(Keu)euvs=eueuvs.{\ displaystyle (K_ {I}) ^ {I} = - M ^ {I} \ qquad {\ mbox {et}} \ qquad (K_ {I}) ^ {I ^ {c}} = I ^ {I ^ {c}}.}

Vemos que os dois cones dos quais é a soma estão contidos em  ; eles são obtidos tomando e . Essas observações levam à seguinte definição. QR(M){\ displaystyle Q_ {R} (M)}QS(M){\ displaystyle Q_ {S} (M)}eu=∅{\ displaystyle I = \ varnothing}eu={1,...,não}{\ displaystyle I = \ {1, \ ldots, n \}}

Matriz Q0  -  Dizemos que uma matriz é uma matriz se satisfaz uma das seguintes condições equivalentes: M∈Rnão×não{\ displaystyle M \ in \ mathbb {R} ^ {n \ times n}}Q0{\ displaystyle \ mathbf {Q_ {0}}}

1. o problema tem solução se for viável,CL⁡(M,q){\ displaystyle \ operatorname {CL} (M, q)}
2. QS(M)=QR(M){\ displaystyle Q_ {S} (M) = Q_ {R} (M)},
3. QS(M){\ displaystyle Q_ {S} (M)} é convexo.

Denotamos o conjunto de -matrizes. Q0{\ displaystyle \ mathbf {Q_ {0}}}Q0{\ displaystyle \ mathbf {Q_ {0}}}

Apêndices

Notas

1. De acordo com Cottle, Pang e Venkateswaran (1989), os cones foram introduzidos por Samelson, Thrall e Wesler (1958) e foram estudados no contexto de problemas de complementaridade linear por Murty (1972).Keu(R++não){\ displaystyle K_ {I} (\ mathbb {R} _ {++} ^ {n})}
2. (em) H. Samelson, RM Thrall, Wesler O. (1958). Um teorema de partição para o n-espaço euclidiano. Proceedings of the American Mathematical Society , 9, 805-807.
3. (en) KG Murty (1972). Sobre o número de soluções para o problema da complementaridade e as propriedades de abrangência dos cones de complementaridade. Linear Algebra and its Applications , 5, 65–108.
4. (em) RW Cottle, JS Pang, V. Venkateswaran (1989). Matrizes suficientes e o problema da complementaridade linear. Linear Algebra and its Applications , 114, 231–249. doi

Artigos relacionados

• Complementaridade linear
• Matriz P

Bibliografia

• (en) RW Cottle, J.-S. Pang, RE Stone (2009). O problema da complementaridade linear . Clássicos em Matemática Aplicada 60. SIAM, Filadélfia, PA, EUA.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">