Jean-Pierre Dussault
email: pierre.dussault@usherbrooke.ca.

Jean Charles Gilbert
email: jean-charles.gilbert@inria.fr

Exact computation of an error bound for the balanced linear complementarity problem with unique solution -The full report *

Keywords: Balanced linear complementarity problem, complexity, data bitlength, error bound, extreme diagonal matrix, matrix inverse norm, P-matrix, rowwise convex combination of matrices, separable function, strong duality, 15A60, 49N15, 65F35, 65Y20, 90C33, 90C46, 90C60 functions . . . . . . . . . . . . . . .

This paper considers the balanced form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang and published in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that, when any rowwise convex combination of two square matrices is nonsingular, the ℓ ∞ norm of the inverse of these rowwise convex combinations is maximized by an extreme diagonal matrix.

Introduction

Error bounds play a prominent role in the analysis of mathematical problems and the algorithms to solve them, in particular in numerical optimization [START_REF] Pang | Error bounds in mathematical programming[END_REF]. This paper focuses on error bounds discovered by Chen and Xiang [9; 2006] for the linear complementarity problem with a P-matrix and simplifies the expression of its upper factor. The paper also deduces some consequences of this new expression.

In its standard form [START_REF] Cottle | The Linear Complementarity Problem[END_REF], the linear complementarity problem (LCP) reads

0 x ⊥ (M x + q) 0, (1.1)
where the unknown is x ∈ R n (the set of real vectors with n components), while M ∈ R n×n (the set of real matrices of order n) and q ∈ R n are data. Inequalities on vectors must be understood componentwise (for example x 0 in (1.1) means x i 0 for all i ∈ [1 : n], the set of the first n integers). The compact writing of the problem in (1.1) means that one has to find a vector x in R n + := {x ∈ R n : x 0} such that M x + q 0 and x T (M x + q) = 0 (the superscript " T " is used to denote vector or matrix transposition).

A matrix M ∈ R n×n is said to be a P-matrix if all its principal minors are positive (i.e., the determinant det M II > 0, for all I ⊆ [1 : n]; by convention det M ∅∅ = 1). One denotes by P the class of P-matrices. It is known that problem (1.1) has a unique solution, whatever q is, if and only if M ∈ P [34; 1958]. There are many other characterizations of the P-matricity [START_REF] Cottle | The Linear Complementarity Problem[END_REF], including algorithmic ones [START_REF] Ben Gharbia | An algorithmic characterization of P-matricity[END_REF][START_REF] Ben Gharbia | An algorithmic characterization of P-matricity II: adjustments, refinements, and validation[END_REF].

For the sake of generality and for taking advantage of its symmetric formulation, which allows us to shorten some proofs, this paper considers an LCP in a slightly more general form than (1.1), namely 0 (Ax + a) ⊥ (Bx + b) 0,

where A, B ∈ R n×n and a, b ∈ R n are the data. By comparison with problem (1.1), we name this problem the balanced LCP. This is a special case of the so-called (extended) vertical LCP, which uses more than two matrices and vectors in its formulation (see [START_REF] Cottle | A generalization of the linear complementarity problem[END_REF][START_REF] Sznajder | The generalized order linear complementarity problem[END_REF]). Throughout this work, we assume that problem (1.2) has a unique solution x. Conditions on A and B ensuring this property, whatever the vectors a and b are, will be recalled in proposition 3.1. An error bound associated with a set S is an estimate of the distance to S by quantities that are easier to evaluate than this distance, usually those that are used to define the set. The set considered in this paper is the solution set of the LCP (1.2), which has been said to be reduced to the singleton {x}, while the quantity used to estimate the distance to x is defined as follows.

Let • denote an arbitrary norm on R n . The natural residual [START_REF] Luo | Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem[END_REF][START_REF] Mangasarian | New improved error bounds for the linear complementarity problem[END_REF] associated with the linear complementarity problem (1.2) is the function r : R n → R n whose value at x ∈ R n is given by r(x) := min(Ax + a, Bx + b), (1.3) where the minimum operator "min" acts componentwise (for two vectors u, v ∈ R n and i ∈ [1 : n]: [min(u, v)] i = min(u i , v i )). It is clear that x solves (1.2) if and only if r(x) = 0, since min(Ax + a, Bx + b) = 0 if and only if, for all i ∈ [1 : n], (Ax + a) i 0, (Bx + b) i 0 and either (Ax + a) i or (Bx + b) i vanishes. Therefore r(x) is a possible measure of the proximity of x to x. In this paper, we consider error bounds of the form

∀ x ∈ R n : β r(x) x -x β r(x) ,
where β and β are positive constants (independent of x), that we call the lower and upper error bound factors, respectively. Error bounds for the LCP have been the subject of many contributions, see [START_REF] Robinson | Some continuity properties of polyhedral multifunctions[END_REF][START_REF] Pang | Inexact Newton methods for the nonlinear complementarity problem[END_REF][START_REF] Mathias | Error bounds for the linear complementarity problem with a P-matrix[END_REF][START_REF] Luo | Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem[END_REF][START_REF] Mangasarian | New improved error bounds for the linear complementarity problem[END_REF][START_REF] Luo | New error bounds for the linear complementarity problem[END_REF][START_REF] Chen | Computation of error bounds for P-matrix linear complementarity problems[END_REF][START_REF] Chen | Perturbation bounds of P-matrix linear complementarity problems[END_REF][START_REF] Dai | Error bounds for linear complementarity problems of DB-matrices[END_REF][START_REF] Li | Some new error bounds for linear complementarity problems of H-matrices[END_REF][START_REF] Chen | Error bounds for linear complementarity problems of MB-matrices[END_REF] for entry points.

For P and Q ∈ R n×n , we define

[P, Q] := {X ∈ R n×n : P X Q},
where the inequalities act again componentwise (i.e., P X Q means P ij X ij Q ij for all i, j ∈ [1 : n]). Hence, for the identity matrix I, [0, I] is a compact notation for the set of diagonal matrices with diagonal elements in the interval [0, 1]. Note also that the set of extreme points of [0, I], denoted by ext[0, I], is the set of diagonal matrices with diagonal elements in {0, 1} (see [33; p. 162] for the definition of an extreme point of a convex set; one can use [16; proposition 2.12] for a meticulous proof of this claim).

For D ∈ [0, I], we denote by

C D := (I -D)A + DB (1.4)
the rowwise convex combination of the matrices A and B ∈ R n×n . Proposition 3.1 recalls, as a straightforward extension of [1; lemma 2.1], that the LCP (1.2) has a unique solution whatever the vectors a and b are, if and only if

∀ D ∈ [0, I] : C D is nonsingular. (1.5)
Therefore, this assumption is made throughout this paper. When this assumption holds, proposition 3.2 recalls that the following lower and upper error bounds hold:

∀ x ∈ R n : max D∈[0,I] C D -1 r(x) x -x max D∈[0,I] C -1 D r(x) , (1.6)
where • denotes a norm on R n and the induced matrix norm.

In this paper, we are interested in giving more precision on the way the lower and upper error bound factors appearing in (1.6) can be computed, when the ℓ ∞ norm is used. If the lower bound factor is easy to evaluate (see section 3.2), the upper bound factor

β := max D∈[0,I] C -1 D ∞ (1.7)
raises more difficulty. This concern makes perfect sense because, as far as we know, this upper error bound factor is the best one obtained so far for the LCP (1.1) with M ∈ P; in particular, it is smaller, hence better, than the one of Mathias and Pang [START_REF] Mathias | Error bounds for the linear complementarity problem with a P-matrix[END_REF] (see [9; theorem 2.3]). We shall show that the evaluation of β can be simplified since one has

β = max D∈ext[0,I] C -1 D ∞ . (1.8)
This extends to higher dimensions the simple observation that, when n = 1, the map

D ∈ [0, 1] → C -1 D ∞ is monotone, so that it attains its maximum on [0, 1] at a point in {0, 1}. For n > 1, however, D kk ∈ [0, 1] → C -1
D ∞ may be nonmonotone (see the example in section 4.2), so that an analysis along this line is troublesome. Furthermore, this map can be neither convex nor concave (see example 3.3). For these reasons, we shall present a specific, rather long and indirect, proof of (1.8). The simplification (1.8) of (1.7) may look minor at first glance, but it may be interesting for reasons that are discussed in section 4.4: it provides a way of computing β exactly, it simplifies its computation for small n and it may be crucial for giving an upper estimate of β in terms of the data bitlength in some complexity analysis.

The paper is organized as follows. The next section presents two results that will play an important role in getting the expression (1.8) of β: the first one deals with the norm of a matrix inverse and the second deals with min-max duality in optimization. Section 3 is dedicated to the proof of (1.8). Section 4 illustrates the result and its proof by several examples or counter-examples. We conclude by some thoughts on complexity issues.

Notation

The unit closed ball associated with a norm • is denoted by B := {x : x 1} and the unit sphere by ∂B := {x : x = 1}.

Preliminaries

Once a result is discovered, one may then look for a more direct proof. When first hunting for certainty it is reasonable to use whatever tools one possess (sic).

Jonathan M. Borwein [6; 2016].

This section presents two results that will play a major part in our strategy to get the desired result in section 3. The first one (lemma 2.1) gives an expression of A -1 , for a nonsingular matrix A ∈ R n×n , in terms of an optimization problem. Consequences of this expression for the ℓ ∞ norm are given in corollary 2.2 and in the technical lemma 2.3. The second result (lemma 2.4) highlights conditions to have strong duality on a product space X × [1 : p] for a pairing function that has a separable property.

Norm of a matrix inverse

For a given nonsingular matrix function

z ∈ R p → A(z) ∈ R n×n , analyzing the map [A(•)] -1
min v =1 Av = A -1 -1 .
(2.1a)

In addition, v solves the problem in the left-hand side of (2.1a) if and only if w :=

A -1 Av solves the problem in the left-hand side of max w =1

A -1 w = A -1 .

(2.1b)

Proof. 1) Let us first prove (2.1a). By the nonsingularity of A, the following identity holds α := min

v =1 Av = min A -1 w =1 w . (2.2)
Note that α > 0 by the nonsingularity of A and the compacity of ∂B. Then A -1 w 1 for any w verifying w = α (since otherwise w := w/ A -1 w would verify A -1 w = 1 and w = w / A -1 w < α, contradicting the fact that α is the optimal value of the problem in right-hand side of (2.2)). This implies that max

w =α A -1 w = 1,
since any solution w to the problem in the right-hand side of (2.2) is such that w = α and A -1 w = 1. The identity (2.1a) now follows by

1 = max w =α A -1 w = α max w =1 A -1 w = α A -1 .
2) Let v solve the problem in the left-hand side of (2.1a) and define w := Av/α. Then w = 1 and A -1 w = v /α = 1/α = A -1 , which shows that w solves the problem in the left-hand side of (2.1b).

Reciprocally, suppose that w solves the problem in the left-hand side of (2.1b) and set v := αA -1 w. Then, v = α A -1 w = α A -1 = 1 and Av = α, so that v solves the problem in the left-hand side of (2.1a). ✷

For the ℓ 2 -norm, the identity (2.1a) can also be obtained by using the relation between the smallest λ min and the largest λ max eigenvalues of inverse symmetric matrices:

min v 2 =1 Av 2 2 = λ min (A T A) = 1 λ max (A -1 A -T ) = 1 A -T 2 2 = A -1 -2 2 .
Nevertheless, the infinity norm is used below, as well as the link highlighted in lemma 2.1 between the vectors v giving the minimum in (2.1a) and the vectors w giving the maximum in (2.1b).

As we just said, in the sequel, the infinity vector and its induced matrix norms, both denoted by • ∞ , are used. For this reason, we consider this case in corollary 2.2 below and bring some precision. We denote by e i the ith basis vector of R n and set e := i∈[1 : n] e i , which is the vector of all ones. By definition and computation [19; § 5.6.5] (see also (2.8a)-(2.8d) in the proof of corollary 2.2 below), for a matrix A ∈ R n×n , one has

A ∞ := max w ∞=1 Aw ∞ = max i∈[1 : n] A i : 1 , (2.3)
where A i : := (e i ) T A denotes the ith row of A and v

1 := i∈[1 : n] |v i | denotes the ℓ 1 -norm of v ∈ R n .
We also denote by "sign" the maximal monotone multifunction R ⊸ R that is the subdifferential of the absolute value function: it associates with t ∈ R the following set of R:

sign t :=    {-1} if t < 0 [-1, 1] if t = 0 {1} if t > 0.
(2.4)

One finds other definitions of sign(0), in particular to make the map "sign" a single-valued function, but our choice of definition is important for the sequel, like in the formulas (2.5b) below. Recall that • 1 is the dual norm of • ∞ with respect to the Euclidean scalar product, which means that

v 1 = max w ∞=1 v T w = max w ∞=1 |v T w|. (2.5a)
The solution sets of these maximum problems are Arg max

w ∞ =1 v T w = (sign v) ∩ ∂B ∞ and Arg max w ∞=1 |v T w| = (± sign v) ∩ ∂B ∞ , (2.5b)
where, for a vector

v ∈ R n , sign v := (sign v 1 )ו • •×(sign v n ) ⊆ R n (hence sign 0 R n = B ∞ ), ± sign v := (sign v) ∪ (-sign v)
and the boundary ∂B ∞ of B ∞ is present only to deal with the case where v = 0. For a nonsingular square matrix A, we adopt the following notation

W ∞ (A) := Arg max w ∞=1 A -1 w ∞ = {w ∈ ∂B ∞ : A -1 w ∞ = A -1 ∞ }, (2.6a)
V ∞ (A) := Arg min v ∞ =1 Av ∞ = {v ∈ ∂B ∞ : Av ∞ = A -1 -1 ∞ }. (2.6b)
The second equality in (2.6a) comes from the definition of the induced matrix norm • ∞ in (2.3), while the second equality in (2.6b) is deduced from the identity (2.1a). The next corollary gives other expressions of these sets.

Corollary 2.2 (ℓ ∞ -norm of a matrix inverse) Suppose that A ∈ R n×n is a non- singular matrix. Set β := A -1 ∞ and α := 1/β. Then, W ∞ (A) = ± sign(A -T e i ) : (A -1 ) i : 1 = β , (2.7a) V ∞ (A) = α A -1 W ∞ (A) . (2.7b) Proof. [(2.7a)] Observe first that β = max w ∞=1 A -1 w ∞ [definition of the matrix norm • ∞ ] (2.8a) = max w ∞=1 max i∈[1 : n] |(e i ) T A -1 w| [definition of the vector norm • ∞ ] (2.8b) = max i∈[1 : n] max w ∞=1 |(e i ) T A -1 w| [the max's commute] (2.8c) = max i∈[1 : n] A -T e i 1 [(2.5a)]. (2.8d)
We can now establish the identity (2.7a).

[⊆] If w ∈ W ∞ (A), w solves the problem in (2.8a)-(2.8b), by definition. Let ī ∈ [1 : n] be a solution to the inner problem max{|(e i ) T A -1 w| : i ∈ [1 : n]} appearing in (2.8b).

Then, the pair ( w,ī) maximizes the map (w, i)

∈ ∂B ∞ × [1 : n] → |(e i ) T A -1 w|.
It follows that ī solves to the problems in (2.8c)-(2.8d) and w is a solution to the inner problem max{|(e ī) T A -1 w| : w ∞ = 1} appearing in (2.8c). Hence, by (2.5b), w ∈ ± sign(A -T e ī) and, by (2.8d), β = A -T e ī 1 = (A -1 ) ī : 1 .

[⊇] Suppose now that w ∈ ± sign(A -T e ī) for some ī ∈ [1 : n] satisfying A -T e ī 1 = β.

-By this last identity, ī solves the problem in (2.8d), hence the problem in (2.8c).

-By the nonsingularity of A -T , one component of A -T e ī does not vanish, so that w ∈ ± sign(A -T e ī) ∩ ∂B ∞ . By (2.5b), this implies that w solves the problem max{|(e ī) T A -1 w| : w ∞ = 1}. It results from these last two observations and (2.8a)-(2.8c), that w solves the problem in (2.8a)-(2.8b). We have shown that w ∈ W ∞ (A).

[(2.7b)] This is a consequence of the last claim in lemma 2.1, according to which v ∈ V ∞ (A) if and only if v = α A -1 w with w ∈ W ∞ (A). ✷
We conclude this section by synthesizing in the following lemma a mechanism that, despite its innocuous appearance, plays a major part in the proof of proposition 3.4 below. As shown in the lemma's proof, this mechanism is only operational when some element of A -1 vanishes, but this fact is revealed indirectly, through a property of a vector v ∈ V ∞ (A).

Lemma 2.3 (technical)

Suppose that A ∈ R n×n is nonsingular, that α := A -1 -1 ∞ and that v ∈ V ∞ (A) has the property that |(Av) k | < α for some k ∈ [1 : n]. Then, there exists a v ′ ∈ V ∞ (A) such that (Av ′ ) k = 0.
Proof. Let β := 1/α. Since v ∈ V ∞ (A), the vector defined by w := βAv is in W ∞ (A), by (2.7b). By assumption, (Av) k ∈ (-α, α), so that w k ∈ (-1, 1). These two facts on w and (2.7a) imply that there must be some index i such that w ∈ ± sign(A -T e i ), (A -1 ) i : 1 = β and (A -1 ) ik = 0.

Define the vector w ′ ∈ R n by vanishing the kth component of w:

w ′ i := w i if i = k 0 otherwise.
Then, we also have w ′ ∈ ± sign(A -T e i ), implying that w ′ ∈ W ∞ (A). The sought vector is v ′ := αA -1 w ′ . Indeed, on the one hand, v ′ ∈ V ∞ (A) by (2.7b). On the other hand, Av ′ = αw ′ implying that (Av ′ ) k = 0, as desired. ✷

Strong duality for separable functions

Let be given a set X and p functions ϕ i : X → R. Usually, equality does not hold in the weak duality inequality [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF][START_REF] Golshtein | Modified Lagrangians and Monotone Maps in Optimization[END_REF][START_REF] Bonnans | Numerical Optimization -Theoretical and Practical Aspects[END_REF][START_REF] Ch | Fragments d'Optimisation Différentiable -Théorie et Algorithmes. Lecture Notes[END_REF]]

inf x∈X max i∈[1 : p] ϕ i (x) max i∈[1 : p] inf x∈X ϕ i (x).
(2.9)

Take for example, X = R, p = 2, ϕ 1 (x) = (x + 1) 2 and ϕ 2 (x) = (x -1) 2 , in which case the left-hand side value is 1, while the right-hand side value is 0 (see [17; lemma 4.5] for a way of modifying (2.9) that ensures equality). The situation is very different, more elementary and more favorable, when X is a Cartesian product X = X 1 × • • • × X p of sets X i and each function ϕ i only depends on the ith component x i ∈ X i of x = (x 1 , . . . , x p ) ∈ X; then equality holds above with some other interesting properties. This particular situation, which occurs below, is analyzed in the next lemma. In this one, the problems

inf x∈X max i∈[1 : p] ϕ i (x i ) and max i∈[1 : p] inf x i ∈X i ϕ i (x i ).
are called the primal and dual problems, respectively. A primal (resp. dual) solution is a solution to this primal (resp. dual) problem.

The following pictures illustrate this particular situation and help to have a good understanding of the next lemma, which is useful for the sequel.

R v v

The first p integers i are given in abscissa and the values of the ϕ i (x i )'s are given in ordinate. We shall see that there is no duality gap for this problem: the common primal and dual optimal value, denoted by v, is represented by the horizontal (red) line in the two pictures.

For each integer i ∈ [1 : p], the horizontal short bar gives the value inf{ϕ i (x i ) : x i ∈ X i }, which may or may not be equal to v, but is always less than this optimal value, by the right-hand side of (2.10a). In the left-hand side picture, the crosses are the values ϕ i (x i ) for some x ∈ X (hence, for a particular abscissa, a cross is always above the horizontal short bar), while in the right-hand side picture, the crosses are the values ϕ i (x i ) for some primal solution x ∈ X, which must not exceed v by left-hand side of (2.10a). The dual problem consists in determining the indices i ∈ [1 : p] for which the short bar values inf{ϕ i (x i ) : x i ∈ X i } are maximal; in the pictures, the dual solution set is {2, 4, 5}. The primal problem consists in determining x ∈ X such that the maximum of the ϕ i (x i )'s (the ordinate of the highest crosses) is as small as possible. The next lemma not only shows the lack of duality gap for the separable case, but also describes the sets of primal and dual solutions. It also shows how to construct a primal solution from the dual solutions, as well as a dual solution from the primal solutions. Lemma 2.4 (strong duality for separable functions) Let X := X 1 × • • • × X p be the Cartesian product of nonempty sets X i and let ϕ i :

X i → R, i ∈ [1 : p], be arbitrary functions. An x ∈ X is written x = (x 1 , . . . , x p ), with x i ∈ X i for i ∈ [1 : p]. 1) (No duality gap) The following identity holds inf x∈X max i∈[1 : p] ϕ i (x i ) = max i∈[1 : p] inf x i ∈X i ϕ i (x i ).
(2.10a)

Denote by v the common value of the two sides of this identity. 2) (Set of primal solutions) The set of primal solutions is the possibly empty set

X := X1 × • • • × Xp , where Xi := {x i ∈ X i : ϕ i (x i ) v}. (2.10b)
3) (Set of dual solutions) The set of dual solutions is the nonempty set

Ī := {i ∈ [1 : p] : ϕ i (x i ) v for all x i ∈ X i }. (2.10c) 4) (Saddle-point property)
The following properties are equivalent: (2.10e) 6) (Deducing a dual solution from the primal solutions) Suppose that X = ∅. Then,

(i) (x,ī) ∈ X × Ī, (ii) (x,ī) is a saddle-point of the map (x, i) ∈ X × [1 : p] → ϕ i (x i ), meaning that ∀ (x, i) ∈ X × [1 : p] : ϕ i (x i ) ϕ ī(x ī) ϕ ī(x ī), (2.10d)
ī ∈ Ī if and only if, for all x ∈ X, ī maximizes i ∈ [1 : p] → ϕ i (x i ),
Proof. 1) By the weak duality property (2.9) and the fact that ϕ i only depends on the ith component of x, the inequality " " holds in (2.10a). Let us prove the reverse inequality. Let ε > 0. For any i ∈ [1 : p], there is an

x ε i ∈ X i such that ϕ i (x ε i ) inf x i ∈X i ϕ i (x i ) + ε. Therefore, max i∈[1 : p] ϕ i (x ε i ) max i∈[1 : p] inf x i ∈X i ϕ i (x i ) + ε. (2.11)
It is here that the separability assumption intervenes. Since the left-hand side of (2.11) is the value at

x ε := (x ε 1 , . . . , x ε p ) of the function x = (x 1 , . . . , x p ) ∈ X → max i∈[1 : p] ϕ i (x i ),
the following inequality certainly holds

inf x∈X max i∈[1 : p] ϕ i (x i ) max i∈[1 : p] ϕ i (x ε i ).
Combining with (2.11), we get

inf x∈X max i∈[1 : p] ϕ i (x i ) max i∈[1 : p] inf x i ∈X i ϕ i (x i ) + ε.
Since ε > 0 is arbitrary, the inequality " " holds in (2.10a).

2) The point x = (x 1 , . . . , xp ) is a primal solution if and only if

max i∈[1 : p] ϕ i (x i ) inf x∈X max i∈[1 : p] ϕ i (x i ) = v or ∀ i ∈ [1 : p] : ϕ i (x i ) v.
This fact reads x ∈ X, for the given X.

3) It is clear that Ī is nonempty, since the dual problem consists in taking the maximum of p values in R ∪ {-∞}. An index ī ∈ [1 : p] is a solution to the dual problem if and only if

inf xī∈Xī ϕ ī(x ī) max i∈[1 : p] inf x i ∈X i ϕ i (x i ) = v or ∀ x ī ∈ X ī : ϕ ī(x ī) v.
This fact reads ī ∈ Ī, for the given Ī. 4) By (2.10a), there is no duality gap. Then, by the standard minmax duality theory [15; proposition VI.1.2] (see also [16; theorem 14.3]), the equivalence (i) ⇔ (ii) follows. Now, condition (iii) is just another way of expressing (2.10d).

5) According to (2.10c), for i / ∈ Ī, there is an xi

∈ X i such that ϕ i (x i ) < v. Let x ∈ X be defined by xi = xi i ∈ Ī xi otherwise.
For i ∈ Ī = ∅, one has

ϕ i (x i ) = ϕ i (x i ) [definition of x] = inf{ϕ i (x i ) : x i ∈ X i } [assumption on xi ] = v [i ∈ Ī and definition of v].
And, for i / ∈ Ī, one has

ϕ i (x i ) = ϕ i (x i ) [definition of x] < v [i / ∈ Ī and definition of xi ]. Since ϕ i (x i ) v for all i ∈ [1 : p],
(2.10b) shows that x is a primal solution. Furthermore, xī = xī for all ī ∈ Ī, so that the first identity in (2.10e) holds. We also have that Arg max{ϕ i (x i ) : i ∈ [1 : p]} = Ī, which is the second identity in (2.10e).

6) The implication "⇒" follows from the implication (i) ⇒ (iii) in point 4.

We prove the implication "⇐" by contraposition. Suppose that ī is not a dual solution. Then, by (2.10c), one can find xī ∈ X ī such that ϕ ī(x ī) < v. For some primal solution x, which exists by assumption, we construct the point x ∈ X whose ith component is given by

xi = xi if i = ī xī if i = ī. Since ϕ i (x i ) v for all i ∈ [1 : n] (this is because ϕ i (x i )
v for all i ∈ [1 : n] and ϕ ī(x i ) < v), the vector x is also a primal solution, by (2.10b). However,

ϕ ī(x ī) = ϕ ī(x ī) < v = max i ϕ i (x i ) shows that ī does not maximize i ∈ [1 : p] → ϕ i (x i ). ✷ 3

On the balanced LCP

For the sake of precision and for the reader's convenience, we recall some known results on the balanced LCP (1.2).

The next proposition gives equivalent conditions ensuring the uniqueness of the solution to (1.2) whatever the vectors a and b are. Condition (iv) is the general assumption (1.5). This one has been shown to be equivalent to the row W-property in [37; lemma 2.2] and the latter property has been shown to be equivalent to (i) in [36; theorem 3]. The equivalence (i) ⇔ (ii) is related to [29; 1990, proposition 2], which considers another form of balanced LCP, but our proof is different. The equivalence (ii) ⇔ (iv) extends [1; lemma 2.1], which assumes that A is a positive diagonal matrix. The equivalence of (i) with the row W-property is extended to the vertical LCP in [36; theorem 3]. Proof. [(i) ⇔ (ii)] Let us show that (i) implies that A is nonsingular. Since A is a square matrix, it suffices to prove its injectivity. Let u be such that Au = 0. Consider the LCP in x:

0 Ax ⊥ (Bx + |Bu|) 0,
where |Bu| is the vector made of the absolute values of the components of Bu. This LCP admits the solutions x = 0 and x = u. Hence u = 0 by the assumed uniqueness property of (1.2). Assume now that A is nonsingular. Then, the solutions y to the following standard LCP 0 y ⊥ (BA -1 y + b -BA -1 a) 0.

(3.1) are in bijection with the solutions x to (1.2) through the relation y = Ax + a. Therefore, existence and uniqueness of the solution to (1.2) is equivalent to the existence and uniqueness of the solution to (3.1), a property that is known to be equivalent to BA -1 ∈ P (recalled after the definition of the P-matricity in the introduction).

[(i) ⇔ (iii)] This follows from the equivalence (i) ⇔ (ii), by symmetry of the balanced LCP (1.2).

[(ii) ⇔ (iv)] When (iv) holds, A is nonsingular (take D = 0 in (iv)). Now, when A is nonsingular, (iv) is equivalent to the property

∀ D ∈ [0, I] : (I -D) + D(BA -1 )
∈ R n , one has min(u, v) -min(ū, v) = (I -D)(u -ū) + D(v -v), (3.2a)
where D is the diagonal matrix, dependent on (u, v, ū, v), that has its diagonal element D ii , for i ∈ [1 : n], defined by

D ii :=          arbitrary in [0, 1] if u i = v i and ūi = vi , 0
if u i v i and ūi vi , with one strict inequality, 1 if u i v i and ūi vi , with one strict inequality,

u i -ū i -min(u i ,v i )+min(ū i ,v i ) (u i -ū i )-(v i -v i )
otherwise.

The four cases are clearly disjoint. The fourth and last case above corresponds to the cases where (u i v i and ūi > vi ) or (u i v i and ūi < vi ) ; in these cases, the denominator of the fraction defining D ii is nonzero. They observe that D ∈ [0, I], which is still the case here. Indeed, this is imposed in the first three cases above and for the fourth case, it follows from

r if u i v i and ūi > vi , one has D ii = (ū i -vi )/((ū i -vi ) + (v i -u i )) ∈ [0, 1] ; r si u i v i and ūi < vi , one has D ii = (u i -v i )/((u i -v i ) + (v i -ūi )) ∈ [0, 1].
Now, for a solution x to the LCP (1.2), define u := Ax + a, v := Bx + b, ū := Ax + a and v := B x + b. Clearly, min(u, v) = r(x), min(ū, v) = 0 and, therefore, (3.2a) yields

r(x) = [(I -D)A + DB](x -x) = C D (x -x).
(3.2b)

One deduces from this identity that

r(x) C D x -x , (3.2c)
Furthermore, since D ∈ [0, I], C D is nonsingular by the assumption (1.5), so that one also deduces from (3.2b):

x -x C -1 D r(x) , (3.2d
C D ∞ -1 , (3.3)
can be easily computed. Observe first that, for two vectors u and v and a vector norm • , one has

max t∈[0,1] (1 -t)u + tv ) = max( u , v ) = max t∈{0,1} (1 -t)u + tv ). (3.4) Next, max D∈[0,I] C D ∞ = max D∈[0,I] max i∈[1 : n] (1 -D ii )A i : + D ii B i : 1 [(1.4) and (2.3)] = max i∈[1 : n] max D ii ∈[0,1] (1 -D ii )A i : + D ii B i : 1 [the max's commute] = max i∈[1 : n] max( A i : 1 , B i : 1 ) [(3.4)] = max( A ∞ , B ∞ ) [the max's commute]. (3.5)
This shows that (3.3) can be easily computed. Note that, in view of (3.5), the maximum in (3.3) is obtained for D ∈ {0, I}.

Computation of the upper error bound factor

Before stating the precise result, let us consider the next example, which shows that the function that is maximized in (1.7) can be rather nonlinear; in particular, it may neither be convex nor concave. Therefore, the optimal value of the optimization problem in (1.7) and its solutions may not be easy to compute.

By looking at

C -1 D ∞ on the segment D 11 ∈ [0, 1] → (D 11 , 1 -D 11
), the diagonal of the square, we get the maximum of two functions, which has the following form For a small ε > 0, the first part of the max is a concave function of D 11 ∈ [0, 1] around its maximum at D 11 = √ 3 -1 ≃ 0.7321 (for ε = 0). The graph of this function is given in the figure above (for ε = 10 -3 ); note that the first part of the max gives the second arch in the figure. Therefore, for the given matrix M , the map

D 11 ∈ [0, 1] → max(1 + D 11 , 2 -(1 -ε)D 11 ) 1 -(1 -ε)D 11 +
D ∈ [0, I] → C -1 D ∞ is neither convex nor concave.
Actually, the maximum of C The goal of this section is to show that the value β can be obtained by restricting the feasible set of problem (3.6) to ext[0, I], the set of extreme diagonal matrices of [0, I]:

β = max D∈ext[0,I] C -1 D ∞ . (3.8)
The key mechanism of the proof of the main result of this paper, proposition 3.4 below, is based on lemma 2.3 and is illustrated in section 4.3 in the particular case where A = I and B = M .

Proposition 3.4 (validity of (3.8)) Suppose that A and B ∈ R n×n satisfy (1.5) and that D solves the optimization problem in (3.6). Then, if Dkk ∈ (0, 1) for some k ∈ [1 : n], D remains optimal if Dkk is changed to any value in [0, 1]. In particular, the value of β defined by (3.6) is also given by (3.8).

Before starting the analysis, let us observe that the objective of problem (3.6) is made of the composition of the nonlinear smooth function D → C -1 D and the convex function • ∞ , but this objective is maximized, not minimized, so that the theory developed for the class of composite problems [7,31,[START_REF] Bonnans | Second order optimality conditions based on parabolic second order tangent sets[END_REF] does not apply. For this reason, we provide a specific proof of proposition 3.4. This one is postponed to page 17, after the following preliminary considerations on problem (3.6).

Part of the analysis is based on the following rewriting of β, defined by (3.6) (some more justifications are given after (3.9e), C D is defined by (1.4)):

max D∈[0,I] C -1 D ∞ = max D∈[0,I] min v ∞ =1 C D v ∞ -1 [(2.1a)] (3.9a)
= min

D∈[0,I] min v ∞ =1 C D v ∞ -1 (3.9b) = min v ∞ =1 min D∈[0,I] C D v ∞ -1 [the min's commute] (3.9c) = min v ∞ =1 min D∈[0,I] max i∈[1 : n] |(C D v) i | -1 [definition of • ∞ ] (3.9d) = min v ∞ =1 max i∈[1 : n] min D ii ∈[0,1] |(1 -D ii )(Av) i + D ii (Bv) i | -1 , (3.9e)
where we have been able to switch min D and max i from (3.9d) to (3.9e), without duality gap, thanks to point 1 of lemma 2.4 and the fact that

[0, I] = [0, 1] × • • • × [0, 1] (n times) is a Cartesian product and that |(C D v) i | = |(1 -D ii )(Av) i + D ii (Bv) i | only depends on D ii .
In (3.9c), we have a minimum in v (i.e., the infimum is attained), since by (3.9b) the function (D, v) → C D v ∞ has a minimizer ( D, v) on [0, I] × ∂B ∞ , which implies that v solves the problem in (3.9c) (this property of nested optimization problems is discussed around [16; corollary 1.10]). Let us deduce some consequences of the identities in (3.9).

According to (3.6), the value of the left-hand side in (3.9a) is β > 0 and, according to (3.7), the optimal values of the optimization problems inside the parentheses in (3.9b)-

(3.9c) is α > 0, so that α = min D∈[0,I] min v ∞ =1 C D v ∞ , (3.10a)
= min Proof of proposition 3.4. Suppose that A and B ∈ R n×n satisfy (1.5) and that D solves the optimization problem in (3.6). Since the last claim of the proposition is clear, we only focus on the first part of it, assuming that Dkk ∈ (0, 1) for some k ∈ [1 : n]. By (3.11)-(3.12), there is a v ∈ V ∞ (C D ) such that ( D, v) solves the problems in (3.10). The goal of the proof is now to show that one can replace Dkk by any value in [0, 1], to form a diagonal matrix D′ that is still a solution to (3.6). Sometimes (case 1 below), this goal will be reached with the chosen initial v ; other times (case 2 below), it will be necessary to change the optimal D and v ∈ V ∞ (C D) several times (infinitely often is not excluded, with a limit argument) to reach the goal. Before introducing these cases, we highlight the principal argument that is used in the proof.

v ∞ =1 min D∈[0,I] C D v ∞ . ( 3
Principal argument. Recall that the optimal value of (3.6) is denoted by

β := C -1 D ∞ , which is positive, and that α := 1/β = C D v ∞ for the chosen v ∈ V ∞ (C D)
. Now, we want to determine the other values that the kth diagonal element Dkk of the optimal D can take, if any, while keeping the optimality of the resulting diagonal matrix. Here is the mechanism that allows us to change Dkk . By point 2 of lemma 2.4, for the current v and for any value D′ kk taken in the interval

[a k , b k ] := {D kk ∈ [0, 1] : |(1 -D kk )(Av) k + D kk (Bv) k | α}, (3.16)
the diagonal matrix D′ defined by 2) Case where min

D′ ii := D′ kk if i = k Dii otherwise,
D kk ∈[0,1] |(1 -D kk )(Av) k + D kk (Bv) k | < α. (3.18)
In that case, the interval [a k , b k ] defined by (3.16) is not guaranteed to contain 0 or 1.

By modifying the vector v, however, we show that one can find intervals of substitutes for Dkk , maintaining the optimality of the diagonal matrix, that cover all the interval [0, 1]; this is the desired result. It suffices to extend the interval [a k , b k ] of optimal values for Dkk to the left so that it contains 0, because, by symmetry, the interval [a k , b k ] can then also be extended to the right so that it contains 1 (switch A and B and replace D by I -D).

One can assume that a k > 0, since otherwise there is nothing to prove. This implies that α < A ∞ (because, by optimality of D, one has

α = C D v ∞ C 0 v ∞ = Av ∞ A ∞ and α = A ∞ since otherwise |(Av) k | Av ∞ = α and a k = 0 by (3.16)).
We do this extension by an iterative procedure whose iterates, indexed by j ∈ N, are pairs ( Dj , vj ) verifying ( Dj , vj ) solves the problems in (3.10), (3.19a)

Dj ii = Dii for i = k, (3.19b
)

(1 -Dj kk )(Av j ) k + Dj kk (Bv j ) k = 0, (3.19c) 0 < Dj+1 kk (1 -α/(2 A ∞ )) Dj kk . (3.19d)
The iterative process is interrupted as soon as 0 is in the interval

[a j k , b j k ] := {D kk ∈ [0, 1] : |(1 -D kk )(Av j ) k + D kk (Bv j ) k | α}, (3.20)
that is, as soon as a j k = 0. It will be clear from the construction of these intervals that their union will be formed of solutions for Dkk . Actually, the reasoning below does not control directly a j k but it controls Dj kk ∈ [a j k , b j k ], which tends to zero by (3.19d).

r Let us determine ( D0 , v0 ) and verify (3.19a)- (3.19c) for j = 0 ((3.19d) for j = 0 will be verified when D1 kk will be determined, in the next point). When (3.18) holds, point 2 of lemma 2.4 ensures that changing Dkk in order to have |(C D v) k | < α will not change the optimality of D, so that we can actually assume that

|(C D v) k | < α. Then, lemma 2.3 with A = C D and v = v ∈ V ∞ (C D ) tells us that one can find a v0 ∈ V ∞ (C D ) such that (C D v0 ) k = 0, which reads (1 -Dkk )(Av 0 ) k + Dkk (Bv 0 ) k = 0.
Therefore, setting D0 := D, we see that (3.19b) and (3.19c) hold. Furthermore, (3.19a) also holds since, by (3.12), the fact that D0 solves (3.6) and that v0 ∈ V ∞ (C D0 ) implies that ( D0 , v0 ) solves the problems in (3.10).

r Let us now show how to construct ( Dj+1 , vj+1 ) from ( Dj , vj ), if this is necessary.

Assume that a j k > 0 (otherwise, there is no reason to pursue the iterative process). Then, 0 = (Av j ) k = (Bv j ) k (otherwise a j k = 0) and by definition of a j k in (3.20):

(

1 -a j k )(Av j ) k + a j k (Bv j ) k = α sign((Av j ) k ). (3.21) Indeed, if (1-a j k )(Av j ) k + a j k (Bv j ) k = α, one has, by definition of a j k , (1-t)(Av j ) k + t(Bv j ) k > α for all t ∈ [0, a j k ), in particular (1 -0)(Av j ) k + 0(Bv j ) k > α, so that (Av j ) k > α > 0. Similarly, (1 -a j k )(Av j ) k + a j k (Bv j ) k = -α implies that (Av j ) k < 0.

Discussion

Optimal diagonal elements in [0, 1]

It may occur that the kth diagonal element of a solution D to (3.6) can be any number in [0, 1]. This is clearly the case when A = B, since then C D given by (1.4) is the matrix A and, therefore, is independent of D ∈ [0, I]. Similarly, and more generally, if the kth row of A -B vanishes, C D is independent of D kk ∈ [0, 1], so that any number in [0, 1] can be taken for the kth element of an optimal diagonal matrix. See also section 4.3 for a less trivial example.

No Cartesian product structure

The goal of this section is to show that there is no guaranteed Cartesian product structure for the elements of the diagonal matrices solving problem (3.6) and that this lack of guaranteed Cartesian product structure also holds for the solution pairs ( D, v) to the problems in (3.10). The example also illustrates case 1 of the proof of proposition 3.4, which occurs when (3.17) holds. Consider the P-matrix

M = 1/2 1 -1 1/2 . ( 4.1)
We have The matrix (4.1) allows us to illustrate case 1 of the proof of proposition 3.4, which occurs when (3.17) holds.

M D = 1 -D 11 /2 D 11 -D 22 1 -D 22 /2 and M -1 D = 1 ∆ 1 -D 22 /2 -D 11 D 22 1 -D 11

M -1

D ∞ and the rightmost vertical line, made of the maximizers of this function). Therefore,

M -1 D = 2 0 -6 D22 1+4 D22 1 1+4 D22 . Then, (M -1 D ) 1 : 1 = 2, while (M -1 D ) 2 : 1 = (1 + 6 D22 )/(1 + 4 D22
) ranges in [1, 7/5], so that β = 2 by (2.3), α := 1/β = 1/2 and the optimal set of D's is Diag({1}, [0, 1]).

To illustrates case 2 of the proof of proposition 3.4, which occurs when (3.18) holds, consider the following solution pair ( D, v) to the problems in (3.10):

D = 1 0 0 3/4 and v = 1 -17/32
.

For the given D, one computes easily the set

V ∞ (M D) = ({-1} × [7/16, 11/16]]) ∪ ({1} × [-11/16, -7/16]]),
to which the given v must belong. Observe that (3.18) holds for k = 2: min

D 22 ∈[0,1] |(1 -D 22 )v 2 + D 22 (M v) 2 | = min D 22 ∈[0,1] | -17/32 + (7/8)D 22 | = 0 < α = 1/2.

Complexity issues

The simplification (1.8) of the error bound factor β given by (1.7) allows us to compute it by evaluating the map D ∈ [0, I] → C -1 D ∞ at the 2 n extreme points of [0, I], which are the diagonal matrices D with diagonal entries in {0, 1}. This is an improvement. Nevertheless, for large n, this exponential number of evaluations can make this exact exhaustive computation approach very time consuming. Now, it is not unlikely that, for special classes of matrices, the simplification (1.8) can yield an efficient way of computing the error bound factor. Finally, we are also exploring the possibility to simplify this comprehensive evaluation by a specific algorithm based on the developments made in this paper.

Another interest of the simplified formula (1.8) of β deals with the complexity analysis of some algorithms for solving the balanced linear complementarity problem (1.2) with matrices A and B verifying (1.5) (equivalent to the P-matricity of M if (A, B) = (I, M )) and integer (or rational) data. When the complexity is expressed in terms of the data bitlength, which is the number of bits required to represent the problem data in the computer memory, and when the error bound (1.6) intervenes, the question may arise to know whether the upper error bound factor can be bounded above by a formula using the data bitlength or the bitlength of the matrix A and B, denoted L(A, B) say, since the data bitlength is certainly larger than L(A, B). It is known from [27; paragraph straddling pages 209-210] (probably also implicit in [START_REF] Khachiyan | A polynomial algorithm in linear programming[END_REF]), that, for an arbitrary nonsingular matrix Without (1.8), formula (4.2) could fail to hold and the upper bound of max{ C -1 D ∞ : D ∈ [0, I]} could be in terms of L(C D), which could be infinite since the optimal diagonal matrix D could then have irrational numbers in some entries. Therefore, thanks to (1.8), for the balanced linear complementarity problem (1.2), with matrices A and B verifying (1.5), one has the error bound

M ∈ R n×n , M -1 ∞ n 2 L(M )+1 .
∀ x ∈ R n : x -x ∞ n 2 L(A,B)+1 min(Ax + a, Bx + b) ∞ , (4.3)
where x is the unique solution to the balanced LCP.

(

  iii) xī minimizes ϕ ī on X ī and ī maximizes ϕ i (x i ) on [1 : p]. 5) (Deducing a primal solution from the dual solutions) Suppose that, for any dual solution ī ∈ Ī, the problem inf{ϕ ī(x ī) : x ī ∈ X ī} has a solution xī , then the primal problem has a solution x ∈ X satisfying xĪ = xĪ and Ī = Arg max i∈[1 : p] ϕ i (x).

  Finitely computable error bounds for the LCPThis section focusses on the exact computation of the lower and upper error bound factors in(1.6). More specifically, its main result, proposition 3.4, shows that a solution to (1.7) can always be found in ext[0, I], the set of extreme points of [0, I] (one may find solutions with a diagonal element in (0, 1) however; examples are given in sections 4.1 and 4.3).

Proposition 3 . 1 (

 31 well-posedness of the balanced LCP) The following properties are equivalent (i) the LCP (1.2) has a unique solution whatever the vectors a and b are, (ii) A is nonsingular and BA -1 ∈ P, (iii) B is nonsingular and AB -1 ∈ P, (iv) (I -D)A + DB is nonsingular for all D ∈ [0, I].

) 3 . 2

 32 Of course D in (3.2c) and (3.2d) depends on x and x, but, since D ∈ [0, I], one certainly has (1.6) by taking the maximum in D ∈ [0, I] in these two estimates. ✷ Computation of the lower error bound factor Before focusing in section 3.3 on the main objective of this paper, which is the simplification of the upper error bound factor in (1.6), let us mention that the lower error bound factor in (1.6), with the ℓ ∞ norm, namely max D∈[0,I]

Example 3 . 3 ( 1 D∞

 331 nonlinearity of D → C -) For A = I and B ∈ P, the map D ∈ [0, I] → C -1 D ∞ has no guaranteed convexity or concavity property. Consider the LCP (1.2) with A = I and B = 1 + ε 1 1 1 ∈ P, where ε > 0 is a small number. One computes easily -D 22 1 + εD 11 , where ∆ := 1 + εD 11 -D 11 D 22 is the determinant of C D , which is positive on [0, I]. Using (2.3), one gets C -1 D ∞ = max(1 + D 11 , 1 + εD 11 + D 22 ) ∆ .

- 1 D

 1 ∞ is obtained for D = Diag(1, 1), which is not on the segment D 11 ∈ [0, 1] → (D 11 , 1 -D 11 ), on which the map presents two hills, as shown by the figure above. ✷ By the compactness of [0, I] and the continuity of D ∈ [0, I] → C -1 D ∞ , the maximization problem (1.7), recalled below β := max D∈[0,I] , say D. Since C D is nonsingular, β given by (3.6) is finite and positive. Then, one can also define the positive number α := β -1 .(3.7)

  .10b) Therefore, one can write D solves (3.6) ⇐⇒ ∃ v such that ( D, v) solves problems (3.10).(3.11)

  is a solution to problem(3.13a). By(3.14), we get that D′ is a solution to problem(3.6). In conclusion, for any v ∈ V ∞ (C D) with D solving (3.6), the interval [a k , b k ] defined by(3.16) is a set of optimal values for Dkk . These intervals depend on v. Our objective is to show that the union of these intervals [a k , b k ] for some well chosen v ∈ V ∞ (C D ) and solutions D to (3.6) is [0, 1] (the reasoning only holds when Dkk ∈ (0, 1)). In case 1 below, one has [a k , b k ] = [0, 1], immediately. In case 2 below, the objective is realized by changing v and D, alternatively, possibly infinitely often.By optimality of D for (3.13a), we have|(C D v) k | α (recall that (C D v) k = (1 -Dkk ) (Av) k + Dkk (Bv) k only depends on Dkk ). Therefore, either min{|(C D v) k | : D kk ∈ [0, 1]} = α or min{|(C D v) k | : D kk ∈ [0, 1]} < α.We now examine these two complementary cases.1) Case where minD kk ∈[0,1] |(1 -D kk )(Av) k + D kk (Bv) k | = α.(3.17) By lemma 3.5, with ν = (Av) k and µ = (Bv) k , the solution set of problem (3.17) is either {0}, {1} or [0, 1]. From (3.16) and (3.17), this solution set is also the interval [a k , b k ]. Therefore, by the principal argument described above, for the considered vector v solving (3.10b), the kth element of the optimal D can be {0}, {1} or any value in [0, 1]. Since Dkk ∈ (0, 1), by asumption, one has [a k , b k ] = [0, 1], which concludes the proof in this case.

/ 2 , 1 D ∞ = 1 ∆ max 1 + D 11 -1 2 D 22 , 1 -1 2 D 11 + D 22 = ( 1 + 1 0∞ 1 I∞

 211111222121122111 where ∆ := det M D = 1 -1 2 (D 11 + D 22 ) + 5 4 D 11 D 22 . Therefore, by (2.3), M -D 11 -1 2 D 22 )/∆ if D 11 D 22 (1 -1 2 D 11 + D 22 )/∆ otherwise. The right-hand side plot shows the level curves of D ∈ [0, 1] 2 → M -1 D ∞ and its two (red) dots are the points at which this function is maximized. Observe that D 11 → M -1 D ∞ is monotone increasing for D 22 = 0 and monotone decreasing for D 22 = 1. It is pure calculation to see that (1 + D 11 -1 2 D 22 )/∆ is increasing with D 11 and decreasing with D 22 on [0, 1] 2 , so that the first part of the max above is maximized for D = Diag(1, 0), in which case M -1 D ∞ = 4. Symmetrically, the second part of the max above, namely (1 -1 2 D 11 + D 22 )/∆, is obtained by switching D 11 and D 22 in the first part of the max. It is therefore maximized for D = Diag(0, 1) for which M -1 D ∞ = 4. Therefore, for the matrix M in (4.1), problem (3.6) has two solutions D = Diag(1, 0) and D = Diag(0, 1) and the optimal value of (3.6) is β = 4. Now M -= I ∞ = 1 and M -= M -1 ∞ = 6/5, so that neither Diag(0, 0) nor Diag(1, 1) is a solution. This shows that the solution set of (3.6) is not the image by Diag of a Cartesian product.

22 α = 1 / 2 Figure 4 . 1 :rr

 221241 Figure 4.1: Illustration of the proof of proposition 3.4. See the description in the text. proof of proposition 3.4 (case 2); see figure 4.1. r The first iterate ( D0 , v0 ) satisfying (3.19a)-(3.19d) is defined with D0 = D and a v0 = (1, -9/16) ∈ V ∞ (M D0 ) given by lemma 2.3. Il follows that the interval defined by (3.20) is [a 0 2 , b 0 2 ] = [1/12, 1]. r The second iterate ( D1 , v1 ) satisfying (3.19a)-(3.19d) is defined as follows. Only the second (k = 2) component of D0 is modified to get D1 : one sets D1 11 = D11 = 1 and D1 22 = 1 2 (a 0 2 + D0 22 ) = 5/12 (see (3.22)). Then |(M D1 v0 ) 2 | = 1/4 < α = 1/2 (the lefthand side point in figure 4.1 is ( D1 22 , |(M D1 v0 ) 2 |))) and a v1 = (1, -15/32) ∈ V ∞ (M D1 ) is given by lemma 2.3. Il follows that the interval defined by (3.20) is [a 1 2 , b 1 2 ] = [0, 31/36]. Gathering the two intervals computed during these two iterations, we get [0, 31/36] ∪ [1/12, 1] = [0, 1]. Hence, for this special case, the procedure terminates after two stages.

Thanks to the formula ( 1 . 8 )

 18 of β, the upper error bound factor is equal to C -1 D ∞ , for some D ∈ ext[0, I]. Therefore, the rows of C D defined by (1.4) are those of A or B. As a result, one certainly has L(C D) L(A, B). (4.2) As a result, with D ∈ ext[0, I] solving the optimization problem in (1.8), one has max D∈[0,I]C -1 D ∞ = C -1 D ∞ n 2 L(C D )+1 n 2 L(A,B)+1 .

  is nonsingular. By [1; lemma 2.1], this last property is equivalent to BA -1 ∈ P. ✷ Consider now the lower and upper error bounds (1.6) for the LCP (1.2). This is a straighforward adaptation to problem (1.2) of the error bound of Chen and Xiang [9], who consider problem (1.1). The upper error bound is also proved in [37; theorem 3.1]. Denote by • an arbitrary norm on R n and its induced matrix norm, denote by r the natural residual (1.3) and define C D by (1.4). If (1.5) holds, then the lower and upper error bounds (1.6) hold. Proof. Chen and Xiang [9; 2006, § 2] start by observing that, for u, v, ū and v

	Proposition 3.2 (error bounds for the balanced LCP) Consider the	LCP
	(1.2).

Acknowledgments

We would like to thank the referees for their helpful comments and suggestions.

We also have D solves (3.6) v ∈ V ∞ (C D) ⇐⇒ ( D, v) solves problems (3.10). (3.12) This is because, when D solves (3.6) and v ∈ V ∞ (C D ) (i.e., v minimizes C Dv ∞ on ∂B ∞ by (2.6b)), ( D, v) solves the problems in (3.10). Reciprocally, when ( D, v) solves the problems in (3.10), then D solves (3.6) by (3.11) and v minimizes C Dv ∞ on ∂B ∞ , which also reads v ∈ V ∞ (C D) by (2.6b).

Pursuing along the vein that exploits (3.9), we see that the optimal value of the optimization problems inside the parentheses in (3.9d)-(3.9e) is also α > 0, so that, for a v such that ( D, v) solves the problems in (3.10) for some D ∈ [0, I], one has

We shall also use the following implication: We conclude this preliminary discussion with an elementary lemma. Proof. By (3.15):

Note first that ν and µ must not vanish and must have the same sign, since, otherwise, the minimum value in (3.15) would be zero, which would contradict α > 0. Then, three cases can occur.

Subtracting side by side (3.19c) from (3.23), using

which is (3.19d).

We still have to determine

Then, lemma 2.3 with

(the last membership comes from the fact that ( Dj+1 , vj ) solves the problems in (3.10) and the implication "⇐" in (3.12)) tells us that one can find a

The first membership implies (3.19a) with j + 1 replacing j, by the implication "⇒" of (3.12) (note that Dj+1 solves (3.6) by the implication "⇐" of (3.12)). The second identity reads (3.19c) with j + 1 replacing j.

By the two previous points, the iterative procedure defining ( Dj , vj ), for j ∈ N, is well defined, unless it is interrupted by the fact that a j k = 0 for some j ∈ N, which is a desirable property since then D is solution to (3.6)

) and the intervals defined by (3.16) are

which give indeed the diagonal elements of the considered D.

) and the intervals defined by (3.16) are

which also give the diagonal elements of the considered D.

r For D = Diag(0, 1), one gets This example also shows that there is no Cartesian product structure in the solutions ( D, v) ∈ R n×n × R n to the problems in (3.10).

Illustration of the proof of proposition 3.4

This section provides a nontrivial example of matrix M for which any number in [0, 1] can be chosen for a diagonal element of an optimal D (compare with section 4.1, where this possibility is trivially verified). For this, it is necessary to have an element of M -1 D that vanishes (see also the proof of lemma 2.3). Along the way, the example illustrates case 2 of the proof of proposition 3.4, which occurs when (3.18) holds.

Consider the P-matrix M = 1/2 0 3 5 .

We have