An Augmented LCPLet (q, M) be an LCP of order n. Let d ∈ Rn++(d>0) and λ ∈ R+.The corresponding augmented LCP (ALCP) is (˜q,fM) where˜q =qλ,fM =Md−dT0.Question: What about the solvability of (˜q,fM)? We would needz ∈ Rn+and θ ∈ R+such thatw = q + Mz + θd ≥ 0,z≥ 0,zTw =0,σ = λ − dTz ≥ 0,θ≥ 0,θσ=0.Motivation: A solution (z∗,θ∗) of (˜q,fM) with θ∗=0would yieldz∗∈ SOL(q, M).Remarks about the ALCP(a) For any LCP (q, M) and any λ ≥ 0,d>0, FEA(˜q,fM) is thecartesian product of a simplex and a half line.(b) There exists λ ∈ R+such that λ>dTˆz where ˆz is any extremepoint of FEA(q, M). Note that if dTz = λ then z is not in thepolytope determined by the extreme points of FEA(q, M).(c) If M = MT, then (˜q,fM) is just the KKT conditions of the QPminimize qTz +12zTMz subject to dTz ≤ λ, z ≥ 0. Underthese conditions, it is clear that SOL(˜q,fM) 6= ∅. But we are notassuming that M is symmetric.(d) We shall see from Lemke’s algorithm that SOL(˜q,fM) 6= ∅. Butwe are going to “prove” this now by using some “heavy artillery.”A Slight DigressionLet f : Rn−→ Rnbe a given mapping, and let K ⊆ Rnbe a cone.Then CP(f,K) denotes the corresponding complementarity problem,namely finding a solution ofz∗∈ K, f(z∗) ∈ K∗, and hz∗,f(z∗)i =0.It is easy to show that CP(f,K) and the variational inequality problemVI(f,K) find a solution ofz∗∈ K, hz − z∗,f(z∗)i≥0 for all z ∈ Khave the same solutions, if any.The proof of equivalence depends on the assumption that K is a cone.But, in general, the variational inequality problem, VI(f, K), does notrequire that K be a cone.Theorem (Hartman-Stampacchia). Let f be a continuous mappingof Rninto itself and let K be a nonempty compact convex subset ofRn. Then there exists a vector z∗such thatz∗∈ K, hz − z∗,f(z∗)i≥0 for all z ∈ K.(That is, z∗solves VI(f,K).)The proof of the Hartman-Stampacchia Theorem uses theBrouwer Fixed Point Theorem. A continuous mapping of a compactconvex set into itself has a fixed point.This in turn rests on technical result from combinatorial topology calledSperner’s Lemma which we may come to later. This topic is coveredin the book by Border listed in Handout No. 3.End of digression.Theorem. Let (q, M) be a given LCP of order n. Then for scalar λ ≥ 0and n-vector d>0, the augmented LCP (˜q,fM) has a solution.Proof. Take f(z)=q + Mz and K = {z ∈ Rn+: dTz ≤ λ}.Clearly f is continuous on Rnand K is nonempty, compact, andconvex. By the H-S Theorem, VI(f, K) has a solution z∗∈ K.We may interpret z∗as an optimal solution of the linear programmaximize (−f(z∗))Tzsubject to dTz ≤ λz ≥ 0Let θ∗be an optimal solution of the dual of this LP.θ∗=0ifdTz∗<λor f(z∗) ≥ 0maxi{−fi(z∗)/di} otherwiseIt then follows that (z∗,θ∗) solves (˜q,fM).Corollary. Let (q, M) be an LCP of order n. If there exists a constantκ>0 such that[x ≥ 0,eTx = κ]=⇒ [xT(q + Mx) ≥ 0],then (q, M) has a solution.Proof. Pick ˜q =qκ,fM =Me−eT0. Then there exists(z∗,θ∗) ∈ SOL(˜q,fM). If θ∗=0, then z∗∈ SOL(q, M). If θ∗> 0,then eTz∗= κ and hence z∗6=0.By the hypothesis above, we have0=(w∗)Tz∗=(z∗)T(q + Mz∗)+(z∗)Tθ∗e>0.which contradicts the fact that (z∗,θ∗) ∈ SOL(˜q,fM). Hence θ∗=0and z∗∈ SOL(q, M).Remark. In this corollary, any vector d>0 can be used in place of e.Theorem. If q ∈ Rn,M∈ Rn×n,d∈ Rn++, the following areequivalent.(a) SOL(q, M) 6= ∅.(b) For every unbounded sequence {λk}⊂R+, the ALCP (˜qk,fM)with ˜qk=qλkandfM =Md−dT0has a solution (zk,θk)where 0 (zero) is an accumulation point of {θk}.(c) There is an unbounded sequence {λk}⊂R+such that the ALCP(˜qk,fM) (as in (b)) and solution (zk,θk) has the property that 0is an accumulation point of {θk}.Proof. See 3.7.6 on p. 169 of The Linear Complementarity Problem.Corollary. If the quadratic function f(z)=qTz + zTMz is boundedbelow on Rn+, then SOL(q, M) 6= ∅.Proof. Let {λk} be an unbounded sequence of positive scalars. Let{(zk,θk)} be a sequence of solutions of the corresponding ALCPs(˜qk,fM) (relative to some d>0).If inf{θk} > 0 then dTzk= λkfor all k. In this case,f(zk)=−θkλk−→ − ∞ as k −→ ∞ .This implies that f is not bounded below.This contradiction shows that inf{θk} =0. Hence the LCP (q,M)has a solution.Remark. Note the differences between this result and the Frank-WolfeTheorem as applied to the AQP based on (q, M).Copositive MatricesDefinition. A matrix M ∈ Rn×nis called copositive ifxTMx ≥ 0 for all x ≥ 0and strictly copositive ifxTMx > 0 for all 0 6= x ≥ 0.These definitions do not require that M be a symmetric matrix, but Mis copositive if and only if its symmetric part12(M + MT) is copositiveso this assumption is usually in effect when studying the values of thequadratic form over Rn+.Denote the class of copositive matrices by CP and that of strictlycopositive matrices by SCP.Some properties of copositive matrices(a) PSD ⊂ CP.(b) PD ⊂ SCP.(c) If M ∈ Rn×nand mij≥ 0 for all i, j then M ∈ CP.(When M is elementwise nonnegative, we write M ≥ 0.)(d) If M ∈ Rn×nand mij≥ 0 for all i, j and mii> 0 for all i, thenM ∈ SCP.(e) CP and SCP are complete classes. In particular,M ∈ CP =⇒ mii≥ 0 ∀ i and M ∈ SCP =⇒ mii> 0 ∀ i.(f) If CP and mii=0for some i, then mij+ mji≥ 0 ∀ j.(g) CP is a (closed) convex cone.More properties of copositive matrices(h) CP and SCP are invariant under principal rearrangement.(i) CP * Q0. For example, if M =1010, then K(M) is notconvex. Hence M/∈ Q0.(j) As we shall show, SCP ⊂ Q.(k) A matrix M ∈ CP is called copositive-plus (belongs to CP+)if[x ≥ 0 and xTMx =0]=⇒ [(M + MT)x =0].As we shall show, CP+⊂ Q0.(l) A matrix M ∈ CP is called copositive-star (belongs to CP∗)if[x ≥ 0,xTMx =0,Mx≥ 0] =⇒ [MTx ≤ 0].Still more properties of copositive matrices(m) SCP ⊂ CP+⊂ CP∗⊂ CP.(n) It can be shown that the eigenvalues of real symmetric matricesare not enough to determine copositivity. Compare1221and1 −2−21.(o) There are finite (determinantal) tests for copositivity.Theorem (Gaddum). If M ∈ Rn×nis symmetric, the following areequivalent.(a) M ∈ CP.(b) For all α ⊂{1,...,n} the systemMααxα≥ 0,xα≥ 0has a nonzero solution.Proof. (a) =⇒ (b). This follows easily from an alternative theorem.(b) =⇒ (a). The