P E R G A M O N Applied Mathematics Letters 12 (1999) 7-12 Applied Mathematics Letters The Reformulat ion of Nonl inear C o m p l e m e n t a r i t y Prob lems using the F i scher-Burmeis ter Funct ion R. ANDREANI* Department of Computer Science and Statistics, University of the State of S. Paulo (UNESP), C.P. 136, CEP 15054-000, S~Lo Jos6 do Rio Preto-SP, Brazil andr eani0nimitz, dote. £b£1ce. unesp, br J. MARTfNEZf Department of Applied Mathematics, IMECC-UNICAMP, University of Campinas, CP 6065, 13081-970 Campinas SP, Brazil mart inez©ime, uni camp. br (Received May 1998; revised and accepted November 1998) A b s t r a c t - - A bounded-level-set result for a reformulation of the box-constrained variational in- equality problem proposed recently by Facchinei, Fischer and Kanzow is proved. An application of this result to the (unbounded) nonlinear complementarity problem is suggested. (~ 1999 Elsevier Science Ltd. All rights reserved. Keywords- -Complementar i ty , Unconstrained minimization, Reformulation. 1. M A I N R E S U L T S Given F : R n --* R" , F E C I ( R n ) , the Box-Const ra ined Variat ional Inequal i ty Problem (BVIP) consists on finding x E ~ such t h a t (F(x) , z - x) >_ O, for all z E 12, (1) where ~ is the compac t box = {x E R" I ~ < x < r } . (2) The Nonlinear Complemen ta r i t y Problem (NCP) is problem (1) when ~ = {x E R n I x > 0}. Facchinei, Fischer and Kanzow [1] proposed a reform,llation of the B V I P as the following opt imiza t ion problem: n n Minimize liE(x) - u + vii 2 + ~ ~(ui, x, - e~) 2 + ~ ~(vi, rs - x~) =, (3) i = 1 i = l *This author was supported by FAPESP (Grants 96/1552-0 and 96/12503- 0). fThis author was supported by PRONEX, FAPESP (Grant 90-3724-6), CNPq and FAEP-UNICAMP. We are indebted to two anonymous referees for helpful comments. 0893-9659/99/$ - see front matter. (~) 1999 Elsevier Science Ltd. All rights reserved. Typeset by .AAzIS-TEX PII: S0893.9659(99)00049-X 8 R. ANDREANI AND J. M. MARTiNEZ where II" II is the Eucl idian no rm and ~ is the F ischer -Burmeis te r funct ion ~(a , b) = v ~ a 2 + b 2 - a - b, for all a, b E R. T h e i m p o r t a n c e of the F i scher -Burmeis te r reformula t ion of c o m p l e m e n t a r i t y p rob lems lies on the fact t h a t the original p rob lem is reduced to a s imple p rob lem for which m a n y effective techniques exist. (Of course, this character is t ic is shared by o ther re formula t ions t h a t have been proposed in recent l i terature . ) I f the n u m b e r of variables is large and the Jacob ian of F is not very sparse, it is in teres t ing to use mat r ix- f ree a lgor i thms to solve (3). I t is wor th ment ioning t h a t in ter ior -point techniques t h a t do not rely on reformula t ions (see [2,3] and references therein) seem to be very efficient for solving complemen ta r i t y problems, a t least when handl ing (sparse) fac tor iza t ions of mat r ices is possible. F rom now on we call f ( x , u, v) the object ive funct ion of (3). I t is easy to see t h a t f ( x* , u*, v*) = 0 if and only if, x* is a solut ion of the BVIP. In [1] it was proved tha t if (x*, u*, v*) is a s t a t iona ry point of f and F' (x* ) is a P0-mat r ix it necessari ly holds t h a t f ( x * , u*, v * ) = 0. T h e first result of this note will be to prove tha t , below a crit ical value, the level sets of f are bounded. T H E O R E M 1. Assume that - c o < g~ < ri < co, [or a11 i = 1 , . . . , n and ( r i - ~) < - - for all i = 1 , . . . , n. ' Then the set S - { ( x , u , v ) 6 ]R 3n [ f ( x , u , v ) < a s} is bounded. PROOF. Let (x, u, v) be such t h a t f ( x , u, v) < a s. Suppose t h a t xi - gi < -c t . T h e n This implies t h a t f ( x , u, v) > a2. Therefore , if (x, u, v) 6 S we necessari ly have t h a t xi _> ~i - c~, for all i = 1 , . . . , n. (4) T h e same reasoning allows us to prove t h a t u i _ > - ~ , x i _ < r i - a , and v i _ > - ~ , (5) for all i = 1 , . . . , n . Suppose now t h a t S is unbounded . There fore S contains an unbounded sequence (x k, u k, vk). k By (4),(5) this implies t h a t there exists i 6 { 1 , . . . , n } such t h a t u i -+ co or there exists i E { 1 , . . . , n} such t h a t v/k --+ oo. Consider the first case. We have t h a t k k 2 a s _> ( [ F + v , ) So, k k Since I[F(xk)]~l is bounded , this implies t h a t v/k --, co. Analogously, if we assume v k --+ co we necessari ly ob ta in t h a t u k --* co, too. So, we can assume t h a t there exists i 6 {1 . . . . . n} such k t h a t bo th u i ---* oo and v k --+ co. Taking an appropr i a t e subsequence, assume, w i thou t loss of k * Therefore , generali ty, t h a t {x/k } is convergent , say, x i --+ x i . l ira + - - k.=..~ oo Reformulation of Nonlinear Complementarity So, ;iiI j/m-- (xf-t?i) -u” =&--x5. Analogously, Now, (6) (7) Therefore, by (6),(7), o2 2 (xf - eij2 + (~5 -Ti)2. (8) But the minimum value of the right-hand side of (8) is (ri - !i)2/2. So, by the definition of o, we arrived to a contradiction. I Counterexample In this counterexample, we show that the previous result is sharp. That is to say, the level set defined by f (x, u, v) 5 p2 can be unbounded, where p = min 1 (ri - ei), i = 1 - 4 ,,...ln. 1 Define F(x) = EX (E 1 0) and R = {z E W ] 0 5 x 5 1). So, f(x, 21, v) = (EX - u + v)2 + (p(u, x)2 + cp(v, 1 - x)2. The sequence {y” E (l/2, k, k), k = 0, 1,2, . . . } is unbounded. However, f(y") = (;-k+k)‘+2p 2 2. APPLICATION TO THE NCP The Fischer-Burmeister function has been applied by many authors to the nonlinear comple- mentarity problem NCP by means of the reformulation Minimize 2 cp(xi, [F(x)]~)~. i=l (9) 10 R. ANDREANI AND J. M. MARTiNEZ See the references of [1]. If x* is a stat ionary point of (9) and F ( x * ) is a P0-matrix, it can be ensured that x* is a solution of the NCP. If F is a uniform P-function it can also be proved that the objective function of (9) has bounded level sets, but this property could not hold under weaker assumptions. In fact, consider the NCP defined by F(x) = 1 - e -x. This function is strictly monotone and 0 is a solution. However, the level sets o f the function (9) are not bounded. In fact, for all x > 0, qo (x ,F(x ) ) 2 = 2 + ( 1 _ e - ~ ) 2 - ( x + l - e -x <1. So, it is natural to ask whether the bounded-level-set result proved in the previous section can help to establish bounded-level-set reformulations of the NCP using the Fischer-Burmeister function. Let us define L = ( L , . . . , L) • R = and consider the box aL = { x • R = l0 < x < L } . The NCP is naturally connected with the BVIP defined by F and ~'~L. In the Facchinei-Fischer- Kanzow reformulation, the corresponding objective function is n ' n = - ~o (u~, x i ) + ~ qo (vi, L - x~) 2 (10) f(x,u,v) liE(x) u+vl[2+5-~. 2 i=1 i=1 Clearly, f (0 , 0, 0) = [[F(0)[[ 2. Therefore, if we take L > [[F(0)[[2/2, Theorem 1 guarantees that {x • R n I f ( x , u, v) <_ f(O, O, 0)} is bounded. This implies tha t s tandard unconstrained minimization algorithms, which usually generate se- quences satisfying f ( x k+1, u k+l, v k+l) < f ( x k, u k, v k) for all k will generate bounded sequences, if (x °, u °, v °) = (0, 0, 0). As a consequence, algorithms of tha t class will find stat ionary points, which, under the assumptions of [1], will be solutions of the BVIP defined by F and 12L. So, in order to solve the NCP we only need to guarantee that solutions of this BVIP are solutions of the NCP. An answer to this question is given in the following theorem. THEOREM 2. Assume that ~ there exists a solution of the NCP that belongs to ~L and that, for all x, y • R n, ([F (x)]i - [ f (y)]i) (xi - y,) _< 0, for all i = 1 , . . . , n implies that ([F (x)]i - [F (Y)]i) (xi - Yi) = 0, for all / = 1 , . . . , n. Then, every stationary point o f f (defined by (10)) is a solution of the NCP. PROOF. Let x* be a stat ionary point of f . The condition imposed to F in the hypothesis implies tha t max {(Fi (x) - Fi (y)) (xi - yi)} _ 0. i:xi~yi Therefore, by Theorem 5.8 of [3], F is a is P0-function and F'(x) is a P0-matrix for all x • R n. In particular, Fl(x *) is a P0-matrix. So, by [1], x* is a solution of the BVIP defined by ~L- That i s [E (x*)]i >_ 0, if x[ = 0, (11) [E (x*)]i = 0, if 0 < x* < L, (12) Reformulat ion of Nonl inear Complementar i ty i 1 and IF (x*)] i _< 0, if x; = L. Assume tha t £ is a solution of the NCP. This implies tha t IF (x)]i -> 0, if ~i = 0 and [F (x)]i = 0, By (11)-(14) we have that (13) if £i > 0. (14) ( [F - IF (x ; - < 0, (15) for all i = 1 , . . . , n . Let us define Z = {i • { 1 , . . . , n } IF(z*)] i < 0, x* = L}. (16) Assume, by contradiction, that Z ~ 0. Then there exists j • {1, . . . ,n} such that [F(x*)]j < 0 and x j = L. Therefore, 0 > [F (x*)]j x; _> [ f (z*)]j x; - I f (x*)]j ~j - [F (~)]j x; + [F (~)]j ~j (17) = ( I F - t F - But (15) and (17) contradict the hypothesis of the theorem. Therefore, Z -- 0. Since x* is a solution of the BVIP, this implies that x* is a solution of the NCP, as we wanted to prove. | REMARKS. In the linear case ( F ( x ) = M x + q) the hypothesis of Theorem 2 means that the matrix M is column-sufficient. If F is monotone ( ( F ( x ) - F ( y ) , x - y) >_ 0 for ull x, y • R n) or, even, if F is a P-function (maxl<_i<_n{(Fi(x) - F i ( y ) ) ( x i - Yi)} > 0) this hypothesis holds, but the reciprocal is not true. For example, the matrix: :[00 :] is column-sufficient, but not positive semidefinite, therefore, F is not monotone. Moreover, M is not a P-matr ix either, so F is not a P-function. Finally, let us show that the hypothesis of this theorem is sharp and cannot be relaxed to, say, P0-funetion. In fact, consider the following matrix This is a P0-matrix, but F ( x ) = M x + q does not verify the hypothesis of Theorem 2, since M is not column-sufficient. Obviously, (0, 0) is a solution of the NCP. However, taking L = 2, we have tha t all the points of the form (t, 2) for t • [2/3, 2], are solutions of the BVIP defined by F ( x ) = M x + q, ~ = 0, r = L. So, these points are stationary points of the associated optimization problem but, clearly, they are not solutions of the NCP. C O N C L U S I O N S When, for some nonlinear programming reformulation of a complementarity or variational inequality problem, it is known that every stationary point is a solution, it can be conjectured that standard minimization algorithms will be effective for finding a solution, since these algorithms generally find, in the limit, stationary points. However, at least from the theoretical point of view, the effectiveness of the minimization approach is not proved unless, eventually, a bounded level set can be reached. Otherwise, there could be no convergent subsequence at all. In this paper we proved tha t a reformulation of nonlinear complementarity problems satisfies the desired requirements under weaker conditions than the ones established in previous works. 12 R. ANDREANI AND J. M. MARTfNEZ REFERENCES 1. F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: The case of box constraints, In Complementarity and Variational Problems: State of Art, (Edited by M. C. Ferris and J.-S. Pang), pp. 76-90, SIAM, Philadelphia, (1997). 2. M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems, In Lecture Notes in Computer Science, Volulme 538, Springer-Verlag, Berlin, (1991). 3. J.J. Mor~ and W.C. Rheinboldt, On P- and S-functions and related classes of n-dimensional nonlinear mappings, Linear Algebra and Its Applications 6, 45-68, (1973). 4. T. Wang, I~.D.C. Monteiro and J.-S. Pang, An interior point potential reduction method for constrained equations, Mathematical Programming 74, 159-195, (1996).