komplementaritetsproblem

Komplementaritetsproblem, ofte forkortet KLP, er en type matematisk problemstilling der man søker et vektor x i R^n som oppfyller en komplementaritetsrelasjon mellom x og en funksjon F(x). For en funksjon F: R^n → R^n er målet å finne x ≥ 0 og F(x) ≥ 0 slik at x_i F_i(x) = 0 for alle i. Dette innebærer at hvert koordinatpar enten er null eller har en positiv verdi, men ikke begge samtidig.

Spesiell sak er det lineære komplementaritetsproblemet (LCP): Gitt M ∈ R^{n×n} og q ∈ R^n skal man finne z ≥ 0 og w = M z + q ≥ 0 med z^T w = 0. LCP beskriver ofte likevekter og kontaktbetingelser i en lineær ramme.

Relasjon til variational inequalities: LCP kan ses som et spesialtilfelle av variational inequality (VI) med K = R_+^n. Generell VI(K, F) søker x ∈ K slik at F(x)^T(y − x) ≥ 0 for alle y ∈ K. Dette rammeverket kobler KLP til bredere optimaliserings- og likevektsteori.

Metoder: For LCP er Lemke’s algoritme en sentral metode, ofte brukt i praksis. Andre tilnærminger inkluderer pivot‑baserte metoder, interior-point-metoder for ikke‑lineære KLP-er, samt smoothing- og Newton‑typer metoder for ikke-lineære komplementaritetsproblemer.

Anvendelser: KLP brukes i økonomi og spillteori for å modellere likevekt, i ingeniørfag som kontakt og friksjon i mekaniske systemer, samt i trafikknettverk og ulike nettverksbaserte likevektsproblemer.

Existens og betingelser: eksistens og unikhet av en løsning avhenger av egenskaper ved F eller M; for eksempel kan visse klasser som P-matriser sikre eksistens og unik løsning for alle q i LCP.