The Solution Set Characterization and Error Bound for the Extended Mixed Linear Complementarity Problem

Assumption 2.1. For the matrices M, N, Q involved in the EMLCP, we assume that the matrix $$ is positive semidefinite.

Theorem 2.2. Suppose that Assumption 2.1 holds; the following conclusions hold.

• (i)

  If (x₀; y₀) is a solution of the EMLCP, then

  $$ ()

where X = {(x; y) ∈ R²ⁿ∣Mx + p ≥ 0, Nx + Qy + q ≥ 0, Ax + By + b ≥ 0, Cx + Dy + d = 0}, and X^* denotes the solution set of EMLCP.

• (ii)

  If (x₁; y₁) and (x₂; y₂) are two solutions of the EMLCP, then

  $$ ()

• (iii)

  The solution set of EMLCP is convex.

Proof. (i) Set

For any $$, since (x₀; y₀) ∈ X, we have

Since $$, using the similar arguments to that in (2.4), we have Combining (2.4) with (2.5), one has By (2.6), we have By Assumption 2.1, one has Combining (2.7) with (2.8), we have That is, Using $$ again, we have Using $$ again, using the similar arguments to that in (2.11), we have From (2.9), (2.4), and (2.11), one has Combining (2.5) with (2.12) yields Combining this with (2.13) yields From (2.10) and (2.15), one has By (2.10) and (2.16), we obtain that $$ follows.

On the other hand, for any $$, then $$, and

and one has Using (2.18), one has Thus, we have that $$.

(ii) Since (x₁; y₁) and (x₂; y₂) are two solutions of the EMLCP, by Theorem 2.2  (i), we have

Combining this with (Mx₁ + p) ^⊤(Nx₁ + Qy₁ + q) = (Mx₂ + p) ^⊤(Nx₂ + Qy₂ + q) = 0, one has On the other hand, from Mx_i + p ≥ 0,  Nx_i + Qy_i + q ≥ 0,  i = 1,  2, we can deduce From (2.21) and (2.22), thus, we have that Theorem 2.2  (ii) holds.

(iii) If solution set of the EMLCP is single point set, then it is obviously convex. In this following, we suppose that (x¹; y¹) and (x²; y²) are two solutions of the EMLCP. By Theorem 2.2  (i), we have

For the vector (x; y) = τ(x¹; y¹) + (1 − τ)(x²; y²),  for  all  τ ∈ [0,1], by (2.23), we have Using the similar arguments to that in (2.24), we can also obtain Combining (2.24) and (2.25) with the conclusion of Theorem 2.2 (i), we obtain the desired result.

Corollary 2.3. Suppose that Assumption 2.1 holds. Then, the solution set for EMLCP has the following characterization:

Proof. Set

For any $$, then $$, combining this with (x₀; y₀) ∈ X^*. Using the similar arguments to that in (2.5) and (2.12), we have Combining this with $$, one has From $$, we have Thus, by Theorem 2.2  (i), one has $$.

On the other hand, for any $$, by Theorem 2.2  (i), we have $$, $$, and $$, that is,

Thus, $$.

Definition 2.4. A solution $$ of the EMLCP is said to be nondegenerate if it satisfies

Theorem 2.5. Suppose that Assumption 2.1 holds, and the EMLCP has a nondegenerate solution, say (x₀; y₀). Then, the following conclusions hold.

• (i)

  The solution set of EMLCP

  $$ ()

• (ii)

  If the matrices $$ and Q_α are the full-column rank, where α = {i∣(Mx₀ + p) _i > 0, i = 1,2, …, m}, $$, then (x₀; y₀) is the unique nondegenerate solution of EMLCP.

Proof. (i) Set

From Corollary 2.3, one has $$. In this following, we will show that $$. For any $$, then (x; y) ∈ X, combining this with (x₀; y₀) ∈ X^*. Using the similar arguments to that in (2.14), we have Combining this with $$, one has Combining Mx + p ≥ 0, Nx + Qy + q ≥ 0 with (2.36), one has Since (x₀; y₀) is a nondegenerate solution, combining this with (2.37), we have (Mx + p) ^⊤(Nx + Qy + q) = 0. That is, (x; y) ∈ X^*.

(ii) Let $$ be any nondegenerate solution. Since (x₀; y₀) is a nondegenerate solution, then we have

Combining (2.38) with (2.39), we have If i ∉ α, then (Nx₀ + Qy₀ + q) _i > 0 by (2.39). By (2.38) again, we can deduce that On the other hand, for the (x₀; y₀) and $$ which are solutions of EMLCP, and combining Theorem 2.2  (ii), we have $$. Using (Nx₀ + Qy₀ + q) _i > 0,   for  all    i ∉ α, we can deduce that Combining Theorem 2.2  (ii) again, we also have For any i ∈ α, that is, (Mx₀ + p) _i > 0, and combining (2.43), we obtain Combining this with the fact that $$, we can deduce that From (2.41) and (2.42), we obtain Thus, $$ by the full-column rank assumption on $$. Using $$, combining (2.40) with (2.44), we can deduce that That is, $$ by the full-column rank assumption on Q_α. Thus, the desired result follows.

Lemma 3.1. For polyhedral cone P = {x ∈ Rⁿ∣D₁x = d₁, B₁x ≤ b₁} with D₁ ∈ R^l×n, B₁ ∈ R^m×n, d₁ ∈ R^l and b₁ ∈ R^m, there exists a constant c₁ > 0 such that

Lemma 3.2. Suppose that (x₀; y₀) is a solution of EMLCP, and let

then, there exists a constant τ > 0, such that for any (x; y) ∈ R²ⁿ, one has

Proof. Similar to the proof of (2.14), we can obtain

We consider the following linear programming problems From the assumption, we know that (x₀, y₀) is an optimal point of the linear programming problem. Thus, there exist optimal Lagrange multipliers $$, $$, and λ₄ ∈ R^t such that From (3.6), we can easily deduce that Thus, for any (x; y) ∈ R²ⁿ, from the first equation in (3.6), we have Where ν ≥ 0 is a constant. Let τ = max {∥λ₁∥, ∥λ₂∥, ∥λ₃∥, ν}, then the desired result follows.

Theorem 3.3. Suppose that Assumption 2.1 holds. Then, there exists a constant η > 0 such that for any (x; y) ∈ R²ⁿ, there exists (x^*; y^*) ∈ X^* such that

where

Proof. Using Corollary 2.3 and Lemma 3.1, there exists a constant μ₁ > 0, for any (x; y) ∈ R²ⁿ, and there exists (x^*; y^*) ∈ X^* such that

Where (x₀; y₀) is a solution of EMLCP. Now, we consider the right-hand-side of expression (3.11).

Firstly, by Assumption 2.1, we obtain that

is a convex function. For any (x; y) ∈ R²ⁿ, we have Combining this with H(x₀; y₀) = 0, we can deduce that

Secondly, we consider the last item in (3.11). By Assumption 2.1, there exists a constant μ₂ > 0 such that for any (x; y) ∈ R²ⁿ,

where the first equality is based on the Taylor expansion of function H(x, y) on (x₀; y₀) point, the second inequality follows from the fact that (x₀; y₀) is a solution of EMLCP and the fact that a + b ≤ a₊ + b₊ for any a, b ∈ R, and the last inequality is based on Lemma 3.2. By (3.11)–(3.15), we have that (3.9) holds.

Theorem 3.4. Suppose that the assumption of Theorem 2.5 holds. Then, there exists a constant η₁ > 0, such that for any (x; y) ∈ R²ⁿ, there exists a solution (x^*; y^*) ∈ X^* such that

where s(x, y) is defined in Theorem 3.3.

Proof. From Theorem 2.5, using the proof technique is similar to that of Theorem 3.3. For any (x; y) ∈ R²ⁿ, there exist (x^*; y^*) ∈ X^* and a constant μ₄ > 0 such that

Combining this with (3.14), we can deduce that (3.16) holds.