The Frank-Wolfe TheoremIn 1956 Marguerite Frank and Philip Wolfe published an importantexistence result for quadratic programming. (See Appendix (i) of thepaper: M. Frank and P. Wolfe, An algorithm for quadratic program-ming, Naval Research Logistics Quarterly 3 (1956), 95–110.)Theorem. If a quadratic function Q is bounded below on a nonemptypolyhedron C, then Q attains its infimum on C. (That is, there existsa vector ¯x ∈ C such that Q(¯x) ≤ Q(x) for all x ∈ C.)The Frank-Wolfe TheoremTheorem. If a quadratic function Q is bounded below on a nonemptypolyhedron C, then Q attains its infimum on C. (That is, there existsa vector ¯x ∈ C such that Q(¯x) ≤ Q(x) for all x ∈ C.)Proof. We may assume C is noncompact; otherwise the theorem isvalid for any continuous function. Accordingly we may writeC = {x : Bx ≤ d} = {p + λs : p ∈ P, s ∈ S, λ ≥ 0},where P is a polytope and S is the intersection of a finite cone andthe unit sphere in Rn. Note that both P and S are compact sets.Since C is noncompact, the set S is nonempty.We use induction on the dimension of C.It is not restrictive to assume that C has a nonempty interior.The assertion is clearly true for one-dimensional sets.Inductively, we assume that n>1 and the theorem holds for allnonempty polyhedral convex sets of dimension less than n.Let γ be a lower bound for Q on C.Now if x = p + λs ∈ C, we haveQ(x)=Q(p + λs)=Q(p)+λ(cT+ pTD)s +12λ2sTDs ≥ γ.It follows that sTDs ≥ 0 for all s ∈ S.Case 1: sTDs > 0 for all s ∈ S. Since P and S are compact, there existconstants α and β independent of p and s such that α>0 >β,sTDs ≥ α>0 for all s ∈ S,and(cT+ pTD)s ≥ β for all p ∈ P, s ∈ S.HenceQ(p + λs)=Q(p)+λ(cT+ pTD)s +12λ2sTDs ≥ Q(p)+λβ +12λ2α.For fixed p and s, the minimizer of Q(p + λs) subject to λ ≥ 0 ismax{0, −(cT+ pTD)s/sTDs}while that of Q(p)+λβ +12λ2α is −β/α>0. The larger of these is −β/α.Hence we may seek the minimum of Q over the compact set{p + λs : p ∈ P, s ∈ S, λ ∈ [0, −β/α]}.This set clearly contains a point ¯x such thatQ(¯x) = min{Q(x):x ∈ C}.Case 2: ¯sTD¯s =0for some ¯s ∈ S.We now have x + λ¯s ∈ C for all λ ≥ 0 andQ(x + λ¯s)=Q(x)+λ(cT+ xTD)¯s ≥ γfor all x ∈ C and all λ ≥ 0. Hence(cT+ xTD)¯s ≥ 0 for all x ∈ C.Suppose there exists x ∈ C such that x + λ¯s ∈ C for all λ ∈ R.We must then have B(x + λ¯s) ≤ d for all λ ∈ R.This implies B¯s =0from which it follows that y + λ¯s ∈ C for all y ∈ C.Moreover, we have (cT+ xTD)¯s =0for all x ∈ C and hence Q(x + λ¯s)=Q(x)for all x ∈ C and all λ ∈ R.Thus, Q is unaffected by projecting C onto a hyperplane orthogonal to ¯s.The inductive hypothesis applies there and gives the result we seek.Suppose instead that for each x ∈ C there exists a scalar λ ∈ R such thatx + λ¯s 6∈ C.Defineλx= min{λ ∈ R : x + λ¯s ∈ C}.Then for all x ∈ C we have λx∈ (−∞, 0] and x + λx¯s ∈ bdy C. HenceQ(x + λx¯s)=Q(x)+λx(cT+ xTD)¯s ≤ Q(x).This inequality implies that the minimum of Q can be sought on bdy C whichhas lower dimension than C does.The boundary of C is covered by the inductive hypothesis, so the minimum of Qon C must be attained there.Implications for the LCPGiven the LCP (q, M)q + Mz ≥ 0z ≥ 0zT(q + Mz)=0we see that if z ∈ FEA (q, M) then zT(q + Mz) ≥ 0.Implications for the LCPGiven the LCP (q, M)q + Mz ≥ 0z ≥ 0zT(q + Mz)=0we see that if z ∈ FEA (q, M) then zT(q + Mz) ≥ 0.We may think of zT(q + Mz) ≥ 0 as a quadratic function (even if Mis not symmetric).zT(q + Mz) ≡ qTz +12zT(M + MT)zBy the Frank-Wolfe theorem, this quadratic function attains its mini-mum on FEA (q, M) whenever this set is nonempty.EXISTENCE AND MULTIPLICITYWe are interested in knowing what sorts of linear complementarityproblems are guaranteed to have nonempty solution sets.For the time being, we approach this analytically rather than by meansof algorithms.The Associated Quadratic ProgramThe LCP (q, M) gives rise to an associated quadratic program (AQP)minimize zT(q + Mz)subject to q + Mz ≥ 0z ≥ 0Notice that we can writezT(q + Mz) ≡ qTz +12zT(M + MT)z =: ϕ(z).If FEA(q, M) 6= ∅, then quadratic function ϕ is bounded below (byzero) on the polyhedral set FEA(q, M). Hence ϕ attains its (global)minimum there.Lemma. If the LCP (q, M) is feasible, the AQP has an optimal z∗.Moreover, there exists a vector u∗such thatq +(M + MT)z∗− MTu∗≥ 0(z∗)T(q +(M + MT)z∗− MTu∗)=0u∗≥ 0(u∗)T(q + Mz∗)=0The vectors z∗and u∗satisfy:(z∗− u∗)i(MT(z∗− u∗))i≤ 0 for all i =1,...,n.Proof. The AQP has an optimal solution by the Frank-Wolfe theo-rem. Apply the KKT theorem at a (local) minimum. The first fourconditions above are the KKT conditions.At the componentwise level, these conditions implyz∗i(MT(z∗− u∗))i≤ 0 for all i =1,...,n.We also get−u∗i(MT(z∗− u∗))i≤ 0 for all i =1,...,n.The final claim(z∗− u∗)i(MT(z∗− u∗))i≤ 0 for all i =1,...,nfollows by adding the last two sets of inequalities.By adding these n inequalities we obtain(z∗− u∗)TMT(z∗− u∗) ≤ 0.The latter implies(z∗− u∗)TM(z∗− u∗) ≤ 0.Positive definite and semi-definite matricesDefinition. A matrix M ∈ Rn×nis positive definite (PD)ifzTMz > 0 for all z 6=0.This definition does not require the symmetry of M.If M ∈ PD thenMT∈ PD;PMPT∈ PD for every permutation matrix P ;Mαα∈ PD for all αThis last property says that PD is a complete class in the sense thatit contains all the principal submatrices of each of its members.Definition. A matrix A ∈ Rm×nis called an S-matrix if there existsx ∈ Rnsatisfying the strict inequalitiesAx > 0 and x>0.It is easy to show that every positive definite matrix is an S-matrix.(This was done in MS&E 311.)Note that the class of square matrices in S is not a complete class.Theorem. Let M ∈ Rn×n∩ PD. Then for every q ∈ Rn, the LCP(q, M) has a unique solution.Proof. Since PD ⊂ S, every LCP (q, M) is feasible. Hence the AQPhas an optimal solution z∗. Let u∗be the Lagrange multiplier vectorfor the constraints q + Mz ≥ 0. Then as we know,(z∗− u∗)TM(z∗− u∗) ≤ 0.Since M is positive definite, z∗= u∗, and (z∗)T(q + Mz∗)=0. Sincez∗∈ FEA(q, M), it now follows that z∗∈ SOL(q, M). Since theobjective function of the AQP is strictly convex in this case, the AQPhas a unique global solution. Hence (q, M) has a unique