Recent advances in nonsmooth optimization

if and only if

a > 0, b > 0, ab = 0

(1)

are of special interest. In [20] such functions tp are called N C P - f u n c t i o n s . Obviously, the one-dimensional nonlinear complementarity problem x > 0,

f(x)

> 0,

xf(x)

= 0

with / : R —> R has the same solution set as the equation V>(.T,/(X)) =

0

does. Various functions

Solution of Complementarity

Problems

89

• Q. •
(l/2)max 2 {0,a + ft},

V,(a,b)

= 0(\a - b\) - 0(a) - 8{b), where 0 : R —> R is any strictly increasing function with 0(0) = 0, see [25].

• ifia(a,b) = ab + ( l / 2 a ) ( m a x 2 { 0 , a - ab} - a2 + max 2 {0, 6 - aa} - ft2) with (a 6 (1 , oo)), see [27] and [42], [44]. During the last few years, particular attention was also paid to the following function if>(a, b) = 4>(a, b) = Va2 + b2 ~ a - b, see [5, 6, 7, 8, 11, 18, 19, 20, 37, 41]. It was developed by W. Burmeister during a discussion with the author in 1985. The function <j> turned out to possess nice proper­ ties which can be exploited for constructing new merit functions for complementarity problems. Based on this, algorithms with interesting convergence properties for the solution of complementarity problems can be developed. The present paper gives a survey of these recent results together with some improvements and will encourage further studies in this area. The paper is organized as follows. Section 2 starts with some preliminaries and contains basic properties of the function . Then, in Section 3, appropriate merit functions for the nonlinear complementarity problem will be defined. Moreover, their local and global growth behaviour with particular respect to the boundedness of level sets defined by these merit functions will be considered. Section 4 presents a damped and perturbed Newton-type method for the solution of linear complementarity problems with Po - rn at rices. For the approach that, by means of a merit function, the nonlinear complementarity problem is written as a minimiza­ tion problem Section 5 describes some basic results. Section 6 is concerned with the KKT system of constrained optimization problems, where the function will be used to transform this system into a nonlinear (nondifferentiable) system of equations. A generalized Newton method will be analyzed with regard to the conditions for superlinear or quadratic convergence. Some final remarks in Section 7 conclude the paper.

2

Preliminaries and Basic Properties of (j>

Let a function F : R" —> R71 be given and let R+ denote the nonnegative orthant of if". Then, we consider the nonlinear complementarity problem NCP(F): Find i such that

i € Rl,

F(x) e Rl,

xTF(x)

= 0.

(2)

A. Fischer

90

If F(x) = Mx + q we obtain the linear complementarity problem LCP(q, M) as a particular case: Find i such that

x G R%

Mx + qe #+,

xT(Mx

+ q) = 0.

Sometimes, by introducing a vector y of slack variables, these problems are formulated in the 2n-dimensional space. Then, the problem NCP(.F) would read as follows: Find x, y such that

x 6 R%,

y G #+,

xTy = 0,

F(x) - ?/ = 0.

(3)

As we mentioned in the Introduction it can be useful to transform the nonlinear complementarity problem into an equivalent system of equations. Using the function this can be done by F(x)-y

*(*i,Fi(*))

S(x) =

= 0

or

T(x,y) =


= 0, (Xn,yn)

where the latter equation T(x, y) = 0 corresponds to the 2n-dimensional formulation of the nonlinear complementarity problem. For simplicity let z = (x, y). The solution sets of the problems (2) and (3) are denoted by X* and Z* respectively. For a given set W C Rp the point-to-set distance is defined as usual by dist[u,jy]= inf \\v — w\\. Unless otherwise specified, .|| denotes an arbitrary norm. Further, for r > 0 the set B(W,r) is introduced by B{W,r) = { u e f l p | d i s t [ t ; , W ] < r } . Let the function h : Rp —> Rq be Lipschitz-continuous in an open neighbourhood of to G RP. Then, dBh{w) = ID I 3{u>"} : Jim w" = w, 3{Vh(wl/)},

lira Vh(w") =

DT\

was introduced in [35] and is called the B-subdifferential of h at w [34]. With this notation Clarke's Jacobian dh(w) can be written as the convex hull of dsh(w), i.e., dh(w) = codfl/i(u>). See [1] for basic properties of dh(w). At this point we are able to define semismooth functions, see [28]. The more general definition used here is taken from [36].

Solution of Complementarity

Problems

91

Again, let the function h R? —► ft' be Lipschitz-continuous in an open neigh­ bourhood of w £ Rp. The function h is said to be semismooth at w if lim {Vd'\V

£dh(w + td')\

(4)

exists for any d £ RP. Further, according to [36, 37] h is said to be strongly semismooth (or first-order semismooth) at m if h is semismooth at w and for any V £ dh(w + d), 0,

Vd-h,(w;d)

=

0(\\df),

where h'(w; d) denotes the directional derivative of h at w with respect to d. (If h is semismooth at w, then h is directionally differentiable at ID and h'(w; d) is equal to the limit in (4).) Now, let us recall some elements of the theory of complementarity problems. For more details see e.g. [2, 13, 15, 16]. At first, let / = { 1 , . . . , n). The function F is called strongly monotone if, for some c > 0, (x - y)T(F(x)

- F(y)) > c\\x - ytf

(x, y £ ft").

The function F is called strongly copositive if, for some c > 0, xT(F(x)

- F(0)) > C ||x|| 2

(x £ ft;).

This implies that the NCP(F) has a nonempty and bounded solution set. If the LCP(0, M) has the single solution x* = 0, then M is called Ro-matrix (M £ RQ). This property is equivalent to the assumption that the solution set X* of the LCP(g, M) is bounded for every q £ R" A matrix M is called positive semidefinite (respectively, positive definite) if xTMx > 0 (respectively, xTMx > 0) for &l\ x £ R". A matrix M is said to be a Po-matrix (M £ P0) if all its principal minors are nonnegative. It follows that any positive semidefinite matrix must be a Po-matrix. If M £ Ro O Po, then the solution set of LCP(g, M) is not empty for every q £ R" The matrix M is called copositive if xTMx > 0 for all x £ iPJ.. If the condition [o ^ x £ .ft"]

=>

[x, > 0 and ( M i ) , > 0 for some i £ I]

is satisfied, M is said to be semimonotone (M £ EQ). The class Eo of semimonotone matrices contains both the copositive and the /o - matrices. The latter class contains the positive semidefinite matrices. If there is a vector x / 0 such that Mx £ ft!J. and x G ft!}., then M is called 5 0 -matrix (M £ S0). If there is x £ ft+ such that (Mx), > 0 for all i £ I, the matrix M is called S-matrix (M £ S). A solution x* G X* of the linear complementarity problem LCP(q, M) is said to be nondegenerate if x* + (Mx* + q)i > 0 (i £ I).

92

A.

Fischer

T h e LCP(<7, M) is called nondegenerate if it has a nondegenerate solution. T h e remaining l e m m a s summarize some basic properties of t h e function <j>, see [5,8,41]. L e m m a 2.1 The function

is

(a)

an NCP-function,

i.e., property

(1) is

satisfied,

(b)

subadditive,

(c)

positive

(d)

convex, i.e., <j>(aw + (1 — ct)w') < a(w) + (1 — a){w') for all w,w'

i.e., <j>(w + w') < <j)(w) + 4>{w') for all w, w' E R2,

homogeneous,

i.e., <j>(aw) = ct(j>(w) for all w G R

and all a > 0, G R2

an

all a G [0,1], (e)

Lipschitz-continuous for all w,w' 6 R2,

(f)

everywhere

(g)

differentiable

with modulus L = l + \ / 2 , i.e., \(w)—<j>(w')\ < L \\w—w'\\2

directionally

differentiable,

at any point (a,b) apart from ( 0 , 0 ) .

L e m m a 2 . 2 For all w = (a, 6) ^ (0,0) we have for the partial 4>a(a, b)~l-

a/y/a2

and it holds the inequality

+ 62 G [ - 2 , 0 ] ,

derivatives

& ( a , b) = 1 - 6 / V a 2 + b2 G [ - 2 , 0 ]

(4>a(a,b))2 + (i,(a,b))2 > 3 — 2 \ / 2 > 0. More

generally,

A2 + 7 2 > 3 - 2\f2 > 0 is valid for all (A, 7) G d(j>(w) and all w G R2 T h e last inequality is i m p o r t a n t for proving results on loacal superlinear convergence without strict complementarity (see Theorems 4.3, 6.1 and 6.2). To show global convergence for t h e N e w t o n - t y p e method t h a t will be described in Section 4, property (g) of L e m m a 2.1 is of particular interest. This property together with (b) and (c) seems mainly responsible for t h e very encouraging numerical results for different m e t h o d s t h a t employ the function <j> (see [5, 8, 11, 18, 20] ). T h e next l e m m a is needed to prove the boundedness of suitable level sets (compare T h e o r e m 3.1, L e m m a 3.2 and Corollary 3.3). L e m m a 2 . 3 Let {(a",h")} C R2 (a1- —» —00)

or

with

{V —> —00)

or

for v —► 00. Then, \<j>(a", 6")| —» 00 for v —> 00.

(a" —+ 00 and b" —> 00)

d

Solution of Complementarity

Problems

93

L e m m a 2.4 The following inequalities are valid: -(2-v/2)min{a,6) — min{a,f>} < (a,b) < I

—2min{a,6}

- ( 2 + \/2)min{a,6}

(a, 6 > 0) (ab < 0) (a,6<0)

Consequently, it holds in particular ( 2 - v / 2)|min{a,6}| < |
3

{a,b e R).

Merit Functions and their Growth Behaviour

Merit functions can be used as a tool both for proving convergence properties and for the design of algorithms. For instance, merit functions appear in step length proce­ dures or serve to replace the original problem by a minimization problem. Since the actual distance from a given point to the solution set of an NCP(F) is not available in general, a merit function for the NCP(F) is used in some sense as a measure for that distance. Therefore, relations between merit functions and the actual distance are important and will be given below for two special functions. Based on the refor­ mulation of the NCP(F) as a system of equations S(x) = 0 or T(z) = 0 (see Section 2) the norm of the natural residual ||5(x)||

or

||T(*)||

(5)

is used as merit function. That means, ||5(i)|| (respectively HT'(z)ll) serves as a measure for the distance dist[i, X"} (respectively dist[z, Z*]). Theorem 3.1 Let F be Lipschitz-continuous (a)

and assume that X* / 0.

Then there is a constant CQ > 0 such that

\\s(x)\\
{xeRn),

\\T(z)\\ < c0dist[z,Z'\

{zeR2n).

(b) If either F is strongly monotone or F(x) = Mx + q with M 6 RQ, then there is a constant C\ > 0 such that
(x£R"),

(6)

dist[z,Z'}
(zeR2n)-

(7)

If F is Lipschitz-continuous only on an open subset of Rn containing X*, then the previous theorem can easily be modified. Moreover, for strongly copositive functions

A. Fischer

94

F the inequalities (6) and (7) hold for all x 6 Rn with distfa:, X*} > 1 and all z e R2n with dist[z, Z'\ > 1 resp. To prove global convergence of an algorithm it has not only to be shown that at least one of the accumulation points generated by the algorithm is a solution of the problem but also that such a point exists at all. A sufficient condition that is frequently used for the existence of an accumulation point is the boundedness of a suitably defined level set. With regard to (5) the following level sets are considered: 0 s ( r ) = {XerT\

\\S(x)\\ < r},

fir(r)

= {z € i? 2 " | ||T(z)|| < r } .

Lemma 3.2 Let the solution set X" (respectively Z*) be nonempty and bounded. Then, for an arbitrarily chosen r > 0 equation (6) (respectively (7)) implies that the level set Sls{r) (respectively flrir)) is bounded. Theorem 3.3 If either F is Lipschitz-continuous and strongly copositive or F(x) = Mx + q with X' =£ 0 and M e Ro, the level sets fis(r) and ^ ^ ( r ) ^ are bounded for an arbitrarily chosen r > 0. The following theorem (for the case of an affine linear function F) on the local growth behaviour can be found in Fischer [6]. There, a result of Robinson [38] plays an essential role for the proof. Another possibility is to exploit a result on the growth behaviour of | | m i n { i , M i + i?}|| in Luo/Mangasarian/Ren/Solodov [23], see also Luo/Tseng [24]. Theorem 3.4 Let F(x) = Mx + q with X* ^ 0. Then there is a constant C2 > 0 suck that dist[x,X'} < C2||5(i)||

(x £ B{X', 1)),

dist[z, Z*\ < C 2 ||r(z)||

(z 6 B(Z\

1)).

For additional details and general results concerning the growth behaviour of different general classes of merit functions for nonlinear complementarity, we refer to the paper of Tseng [41]. At the end of the section let us note that any norm can be used to define the merit functions (5). Moreover, it can be useful to employ the squared norm of the natural residuals ||5(«)||» or ||r(2)||2, as merit functions, see Section 5. It is easy to adapt the previous results for this case.

4

A Newton-Type Method for LCP

Throughout this section only linear complementarity problems LCP(q, M) with a Po-matrix M will be considered. The damped and perturbed Newton-type method

Solution of Complementarity

Problems

95

we are going to describe is based on [6, 8], although the assumptions used there are sometimes stronger. The method reduces the merit function ||T(z)||oo in each step by means of a step length procedure. The search direction is obtained from a modified Newton linearization applied to T(z) — 0. This modification has three main aims: • To have well defined subproblems even if T is not differentiable at a point zk, • To guarantee that all occurring subproblems are solvable, • To enable a superlinear rate of convergence under relatively mild conditions. Algorithm SO:

Choose z° € R2n and ft G (0,1]. Set k = 0.

Si:

If T(zk) = 0, then stop.

S2:

Determine Azk = (Ax*, Ayk) e R2n such that G(zk)Azk

S3:

+ T(zk) = 0.

Find the largest number tk £ { (\)j \ j £ N} such that ||T(z* + t * A z * ) | j „ < ( l - ^ ) | | r ( z * ) | U .

S4:

Set zk+1 = zk + tkAz*

and k = k + l.

Go to Si.

In view of the subsequent definition, the matrix G(z) can be regarded as a perturba­ tion of the Jacobian VT(z) (if it exists). Let G(z) =

M A(z)

-I T(z)

where the entries of the diagonal matrices A(z) = diag(A,(z)),

T(z) = diag( 7 .(z))

are given by X(z) - I MxUVi) '^ ' 1 —ff(xi) iz\ _ [
1 — o(\)i)

if

\MxirVi)\ otherwise

if

\Mx'iy>)\

>

a x

( i)

> a(y>)

otherwise

if (xi,yi) ^ (0,0). In the case that (x;,t/i) = (0,0) we set A,(z) = - 1 , v(z) = - R+ is defined by a (a) = 0.01(1 + a 2 )" 1 min{||T(z)||2XD, 1}.

A.

96

T h e o r e m 4.1 The algorithm is well defined, in particular length t^ > 0 can always be determined.

a direction

Az

Fischer

and a step

T h e o r e m 4 . 2 Each accumulation point of the iteration sequence {zk} is a solution of LCP(q,M). If the level set Qx(|jT(z 0 )||oo) is bounded, then (at least) one accumu­ lation point exists. A condition ensuring the boundedness of fir(r) is given in Corollary 3.3. T h e following two theorems on local superlinear convergence assume t h a t t h e algorithm does not end with a solution after a finite n u m b e r of steps. T h e o r e m 4 . 3 Let the linear complementarity z* = (x*,y*) which satisfies the condition xTMx //, in addition, (a)

> 0

for all

the iteration

x ^ 0

problem LCP(q, M) possess a

with

x, = 0

sequence {z } is bounded,

z" = lim zk is the unique solution

of LCP(q,

if

solution

y* > 0.

then the following

(8) holds:

M),

k~*oo

(b)

tk = 1 for all sufficiently

(c)

There is a constant

large k 6 N,

C, > 0 such

that

\\zk^-z'\\
(keN).

Condition (8) is closely related to second-order sufficient o p t i m a l i t y conditions for constrained optimization problems and implies t h a t t h e linear c o m p l e m e n t a r i t y prob­ lem LCP(<7, M) is uniquely solvable, see [26]. For stating t h e next result which avoids such a condition let ea be defined by ea = e 1 " 1 - 2 0 ' T h e o r e m 4.4 Let the LCP(q,M) Then, there is e > 0 such that:

(e > 0).

be nondegenerate

If for some a S [0,1/2) and k0 £ N the

and M be positive

conditions

dist[zko,Z'}||r(^)|r are fulfilled, that

(9) (*£/)

then tt, = 1 is valid for all k > ko and there is a constant dist[zk+\

semidefinite.

Zm] < C'dist[zk,

Z'Y~a

{k G N).

(10) C* > 0 such

Solution of Complementarity

Problems

97

Instead of a condition like (8), the LCP(g, M) is required to be nondegenerate (see Section 2). Moreover, it is assumed that the algorithm generates an iterate zk° which is (in the sense of conditions (9), (10)) sufficiently close to a nondegenerate solution. The closer a is to | , the weaker condition (10) is. On the other hand, if a tends to | , then ta goes to 0. The motivation for proving Theorem 4.4 came from interior-point methods and from the observation that the Newton-type algorithm which was suggested in [8] frequently converges superlinearly although condition (8) is violated. In contrast to interior-point methods the components of the iterates zk are also allowed to be negative or zero. In spite of this, due to the definition of G(zh) the local convergence behaviour is similar to a number of interior-point methods if the convergence to a nondegenerate solution is considered. For degenerate linear complementarity prob­ lems which satisfy condition (8) the present algorithm converges Q-quadratically, whereas all interior-point methods that belong to a general framework generate at most linearly convergent sequences [30].

5

Minimization of Merit Functions

The concept to transform the nonlinear complementarity problem into an equivalent equation ([25] and many others) is frequently closely related to the idea of reformu­ lating the complementarity problem as a minimization problem. Different possibili­ ties for using this general idea were proposed. In [11, 17, 27, 42, 44] unconstrained minimization techniques are considered whereas in [9, 4, 27, 29, 31, 33, 40] the com­ plementarity problem is reformulated as a minimization problem with nonnegativity constraints. Throughout this section let F : Rn —> Rn be continuously differentiable. A classical approach for the solution of a nonlinear equation, in our case S(x) = 0 or T(z) = 0, is to minimize the norm of the natural residual. In the previous section this was done for T(z) = 0 (with F(x) = Mx + q) for the maximum-norm ||. ||oo by applying a Newton-type method. Of course, one can use other norms. An important question which will appear in any case is the following: Which (weakest possible) condition guarantees that any minimum of the natural residual is also a global one. Apparently, if the nonlinear equation (i.e., the underlying complementarity problem) is solvable, then any global minimum will solve the complementarity problem. With regard to Section 4 the question mentioned can be answered for the case of minimizing HTWHoo (for linear as well as for nonlinear complementarity problems) by Theorem 5.1 Let V F ( i ' ) be a P0-matrix. (a) If z' = (x",y") is a minimum of \\T(z)\\<xi, then z' is also a global minimum of IIT^Hso on R2n with T(z') = 0. (b) If z" is not a minimum, then there is a descent direction d £ R2n such that ||T(z*-M 0.

A. Fischer

98

Recently, in continuation of the general approach [17], Geiger/Kanzow [11] proposed to minimize ||S(x)||2. This can be very advantageous, in particular with regard to large-scale nonlinear complementarity problems. To minimize ||f(x)|j;j or ||S(x)|| it is possible to use gradient like descent directions or a suitable combination of them with Newton-type directions, for a first approach see the algorithm in [11]. Theorem 5.2 Let VF(x') be a P0-matrix. IfV(\\S(x')\\£) minimum o/||S(x)||2 on Pc1 with S(x*) = 0.

= 0, then x' is a global

For the case of a positive semidefinite matrix VF(x') this result is given in [11]. The result for the more general case with Po-matrices is contained in an unpublished manuscript of F. Facchinei (independent of [11]). Whereas ||S(x)||2 is everywhere continuously differentiable, the function ||S(x)||2 has this property for all x £ Rn\X" For the latter function we obtain Corollary 5.3 Let VF(x')

£ P0. Then, S(x') ± 0 implies v(||S(x)|| 2 ) # 0.

The assumption VF(x') 6 P0 is (to my knowledge) the weakest known condition in order to ensure that a stationary point x' of a suitably defined unconstrained minimzation problem solves the nonlinear complementarity problem NCP(i ? ). For instance, let us consider the minimization problem n

ma{x) = ^v? Q (x,-,F,(x)) -► min, ;=i

where the NCP-function <pa given by Mangasarian/Solodov [27] (see Section 1) is used. Yamashita/Fukushima [44] proved that any stationary point x* of ma is a so­ lution of NCP(F), if VF(x*) is positive definite. By a counterexample they showed that, in general, this condition cannot be replaced by the weaker positive semidefiniteness. However, with regard to some of the papers cited above, in particular [31], the question arises whether the condition V F ( i " ) 6 Po can be further weakened, if the nonlinear complementarity problem is transformed into a constrained minimization problem. Looking to the definition of stationary points (Vn|S(x)|||J = 0), one will find the next lemma. Let [VF(x*)]i denote the principal submatrix of V F ( i ' ) corresponding to the index set T C 7 and let V = {i £ 7|x,- > 0, Fi(x) > 0}. Lemma 5.4 Let x~ 6 R^, F(x') e R\ and S(x') ± 0. If [VF(x')]v £ S0 or [VF(x*)] r £ S or [VF(x*)] z £ E0 for some index set 1 C I with I D V, then it follows thatV(\\S{x')\\l) jtO. As it was mentioned in the Introduction the class Eo contains both the P0- and the copositive matrices. Keeping the lemma in mind it seems possible to obtain results

Solution of Complementarity

Problems

99

that need similar or weaker assumptions than the one used by More [31]. He replaced the NCP(F) with the constrained minimization problem |\\H{x,v)\\l-*jmi |jy(x,!/)||2-niin

subject t t

x > 00

y > 00

where H{x, y) = (Fi(x) - yu ,.., Fn(x) ~yn,xlVu..., xnyn)T. In our case one can consider the constrained minimization problem \\T(i, y)\\2 - min

subject to

x > 00 , > 00

An important question with respect to the iterative solution of complementarity problems is how the boundedness of the iterates can be ensured. If the method reduces the merit functions ||T(z)|| or ||5(i)|| in some sense (also a nonmonotone line search [12] can be very efficient), it suffices that the corresponding level sets S7x(||T(^°)||) or ns(||5(i°)||) are bounded, compare Section 3.

6

A Newton Method for the K K T System

The Karush-Kuhn-Tucker (KKT) conditions for the optimization problem / ( s ) ^- m i n

ssbject to

{s) 9l(s) 9i

>0

(( G £ J = { l , . . . ,m})

((11

with differentiate functions /,gu.. .,gm : R* -» i? can be written as a mixed nonlinear complementarity problem. If additional bounds on the variables (s3 < 0 for all ; € J) occur in (11), then we would obtain a nonlinear complementarity problem, see e.g. [15]. Using the Lagrangian s), L(,,«) = /( Sf{s)-±u )-g>^), L{s,u) =

i=l

3gi{

the KKT conditions belonging to (11) read as follows: Vsi(s,u)=0,

Uj>,,

gj(s)>0,

ujgj{s)

=0

(t € J ) .

(12)

In [5] the function was used to toansform t h t KKK conditions into tot equivalent nonlinear and nondifferentiable system of equations '

R(s,u)= = R(s,u)

VsL(s,u)

'

f>{9l{s Ul)

'

}

== 00..

. (9m(s),Um) . Then, the local Q-quadratic convergence of the following perturbed Newton method was analyzed. For simplicity let w = (s,u) € Rn+m

100

A.

Fischer

Algorithm SO:

+m Choose w° € .R" fl"+m and eps > 0. Set k = 0.

SI:

If R(w*) fl(w*) = 0, then stop.

S2:

Choose wk € R"+m Choose Gk G dR(wk) R(wk)

S3:

such t h a t \\wk - wk\\ < min(eps,

||rt(u;*)||). \\R(wk)\\).

and compute «!*« wk+1 as t h e solution of

+ Gk(w - wk) = 0.

Set k = fck + 1 and go to Step SI.

By a suitable choice (see e.g. [5]) of t h e vectors wk it can be ensured t h a t t h e m a p p i n g R is differentiable for all occurring iterates wk). However, we note t h a t (according to t h e subsequent Theorem) t h e choice wk = wk is always possible and does not destroy t h e Q - q u a d r a t i c convergence to a K K T point (s*, «*). To formulate t h e corresponding result let the index sets J+ C J* C J be given by J' = {J G e ■ % ( * * ) = 0o

aan

J J = {j G g*\u) g*\u* > 0}o

Further, we m a k e use of t h e linear independence condition (LI) and of t h e strong second-order sufficiency condition (SSOS), see Robinson [39]: (LI) (SSOS)

T h e vectors Vjj(s*) T

s V„L(s',u*)s>0 VssL(s",u*)s>0

(j £ J*) are linearly independent for all s ^ 0 with sTV9j(s') {s*)

= 0 (; 6 JJ++)

T h e o r e m 6.1 Let f,gu---,9m be twice Lipschitz-continuously differentiable in an open neighbourhood of s" Furthermore, let w' = (^*,«•) be a point satisfying the KKT conditions (IS) and the conditions (LI) and (SSOS). If w° G B(w',e) for a sufficiently small e > 0, then the algorithm described above generates a well defined sequence {wk} C B{w',t). Moreover, if this sequence is infinite, it converges Qquadratically to w' In contrast to t h e case when certain other (differentiable) NCP-functions are used to transform the K K T conditions (12) into an equivalent nonlinear system of equations, e.g. ifii, <pa or if this transformation is done according to t h e related approach in [21], t h e previous Theorem does not need the strict complementarity condition J" = J+. On t h e other hand, in comparison with other nondifferentiable N C P - f u n c t i o n s , e.g. is moro robust (with respece to t h e existence of Gl1 far from a solution w', since is sifferentiable eor rll l o i n t s s a a r t trom ( 0 , 0 ) ) . In [5] it was mentioned (Remark 4.3) t h a t , with regard to t h e theory of Kummer [22], a superlinear rate of convergence is also possible for only one t i m e dif­ ferentiable functions f,gu...,gm with Lipschitz-continuous derivatives, if additional

Solution of Complementarity

Problems

101

assumptions are satisfied. A very nice result in this direction was recently given by Qi/Jiang [37]. They made use of semismooth functions (see Section 2) and obtained in particular the following result which generalizes Theorem 6.1 to a larger class of func­ tions such that important applications like stochastic quadratic programs and minimax problems are incorporated. Instead of (SSOS) an appropriate generalization is necessary: (SSOS') sTHs > 0 for all H € d,VaL(s,u)

and all a # 0 with sTVgj{s')

= 0 ( j £ J+)

Theorem 6.2 Let f,gi,-..,gm be Lipschitz-continuously differentiable with semismooth (respectively, strongly semismooth) derivatives in an open neighbourhood of s' Furthermore, let (s*,u') be a point satisfying the KKT conditions (12) and the conditions (LI) and (SSOS'). If w° G B(w*,t) for a sufficiently small e > 0, then the algorithm described above generates a well defined sequence {w } C B(w',e). Moreover, if this sequence is infinite, it converges Q-superlinearly (respectively, Qquadratically) to w" The algorithm considered here (see [5]) is in some sense more general than the one in [37]: We allow Gk to be taken from Clarke's Jacobian dR(iv) at w = wk or at the perturbed iterate w = wk.

7

Final Remarks

At the end of this survey some possible or imaginable extensions and generalizations shall be mentioned. The function (f> can be used to transform more general problems into an equivalent system of equations or into a minimization problem (mixed com­ plementarity problems, variational inequalities). Different results presented in this paper allow a corresponding generalization. With regard to the superlinear conver­ gence of the algorithm for LCP(g, M) in Section 4, it should be possible to prove such results also for nonlinear problems under suitably modified assumptions. A further interesting research topic is the design of algorithms for constrained optimization problems with global convergence, see [19] for a result concerning linearly constrained convex minimization problems. With regard to Section 6 as well as to a number of papers (e.g. [4, 34]), where semismoothness appears as a key for weakening differentiability requirements, one is led to employ this, in particular, for algorithms that reduce a suitable merit function (see Section 5). In order to weaken the conditions (Section 3) which ensure that an algorithm generates at least one accumulation point, it can be useful to look for modifications of the algorithm. A first approach was proposed in [7] for the special case of quadratic programming problems. Acknowledgment: The author is very much obliged to F. Facchinei, C. Kanzow,

102

A. Fischer

L. Qi and P. Tseng for discussions concerning different topics of this paper and to the anonymous referees for their remarks.

References [1] F. H. Clarke, Optimization and nonsmooth analysis, John Wiley, New York, 1983. [2] R. W. Cottle and J.-S. Pang and R. E. Stone, The linear complementarity prob­ lem, Academic Press, 1992. [3] Yu. G. Evtushenko and V. A. Purtov, Sufficient conditions for a minimum for nonlinear programming problems, Soviet Mathematics Doklady 30 (1984) 313316. [4] F. Facchinei, Minimization of SC1 functions and the Maratos effect, Preprint, Department of Informatics and System Theory, University of Rome, 1994. [5] A. Fischer, A special Newton-type optimization method, Optimization 24 (1992) 269-284. [6] A. Fischer, On the local superlinear convergence of a Newton-type method for LCP under weak conditions, Preprint MATH-NM-07-1993, Institute for Nu­ merical Mathematics, Technical University of Dresden, 1993 (revised 1994). [7] A. Fischer, A Newton-type method for sparse quadratic programming problems, 15th International Symposium on Mathematical Programming, Ann Arbor, 1994. [8] A. Fischer, A Newton-type method for positive semidefinite linear complemen­ tarity problems, Journal of Optimization Theory and Applications 86 (1995). [9] A. Friedlander and J. M. Martinez and S. A. Santos, Resolution of linear comple­ mentarity problems using minimization with simple bounds, Technical Report, Department of Applied Mathematics, University of Campinas, 1993. [10] M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Mathematical Program­ ming 53 (1992) 99-110. [11] C. Geiger and C. Kanzow, On the resolution of monotone complementarity prob­ lems. Preprint 82, Institute of Applied Mathematics, University of Hamburg, 1994. [12] L. Grippo and F. Lampariello and S. Lucidi, A nonmonotone line search tech­ nique for Newton's method, SIAM Journal on Numerical Analysis 23 (1986) 707-716.

Solution of Complementarity

Problems

103

[13] P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and non­ linear complementarity problems: A survey of theory, algorithms and applica­ tions, Mathematical Programming 48 (1990) 161-220. [14] P. T. Harker and J.-S. Pang, A damped Newton method for the linear com­ plementarity problem, in: E. L. Allgower and K. Georg (ed.), Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics Vol. 26, AMS, Providence, Rhode Island, 265-284. [15] G. Isac, Complementarity Problems, Lecture Notes in Mathematics, Vol. 1528, Springer-Verlag, Berlin, Heidelberg, 1992. [16] J. J. Judice, Algorithms for linear complementarity problems, in: E. Spedicato (ed.), Algorithms for Continuous Optimization, Kluwer Academic Publishers, 1994, 435-474. [17] C. Kanzow, Nonlinear complementarity as unconstrained optimization, Journal of Optimization Theory and Applications, to appear. [18] C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems, Preprint 72, Institute of Applied Mathematics, University of Hamburg, 1993, SIAM Journal on Optimization, to appear. [19] C. Kanzow, An unconstrained optimization technique for large-scale linearly constrained convex minimization problems, Computing 53 (1994) 101-117. [20] C. Kanzow and H. Kleinmichel, A class of Newton-type methods for equa­ lity and inequality constrained optimization, Preprint 61, Institute of Applied Mathematics, University of Hamburg, 1992, revised version 1994, Optimization Methods and Software, to appear. [21] H. Kleinmichel and K. Schonefeld, Newton-type methods for nonlinearly con­ strained programming problems - algorithms and theory, Optimization 19 (1988) 397-412. [22] B. Kummer, Newton's method for non-differentiable functions, in: J. Guddat et al. (ed.), Mathematical Research, Advances in Mathematical Optimization, Akademie Verlag, Berlin, 1988, 114-125. [23] Z.-Q. Luo and O. L. Mangasarian and J. Ren and M. V. Solodov, New error bounds for the linear complementarity problem, Mathematics of Operations Re­ search, to appear. [24] Z.-Q. Luo and P. Tseng, Error bound and convergence analysis of matrix split­ ting algorithms for the affine variational inequality problem, SIAM Journal on Optimization 2 (1992) 43-54.

104

A. Fischer

[25] O. L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations, SIAM Journal on Applied Mathemaiics 11 (1976) 89-92. [26] O. L. Mangasarian, Locally unique solutions of quadratic programs, linear and nonlinear complementarity problems, Mathemaiical Programming 19 (1980) 200212. [27] O. L. Mangasarian and M. V. Solodov, Nonlinear complementarity as unconstrained and constrained minimization, Mathemaiical Programming 62 (1993) 277-297. [28] R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization 15 (1977) 957-972. [29] R. D. C. Monteiro and J.-S. Pang and T. Wang, A positive algorithm for the nonlinear complementarity problem, Preprint, Department of Systems and Industrial Engineering, University of Arizona, Tucson, 1992. [30] R. D. C. Monteiro and S. Wright, Local convergence of interior-point algorithms for degenerate monotone LCP, Preprint MCS-P357-0493, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, 1993. [31] J. J. More, Global methods for nonlinear complementarity problems, Preprint MCS-P429-0494, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, 1994. [32] J.-S. Pang, Newton's method for B-differentiable equations. Mathemaiics of Operations Research 15 (1990) 311-341. [33] J.-S. Pang and S. A. Gabriel, NE/SQP: A robust algorithm for the nonlinear complementarity problem, Mathematical Programming 60 (1993) 295-337. [34] J.-S. Pang and L. Qi, Nonsmooth equations: motivation and algorithms, SIAM Journal on Optimization 3 (1993) 443-465. [35] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Mathemaiics of Operations Research 18 (1993) 227-244. [36] L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathemaiical Programming 58 (1993) 353-367. [37] L. Qi and H. Jiang, Karush-Kuhn-Tucker equations and convergence analysis of Newton methods and Quasi-Newton methods for solving these equations, Applied Mathematics Report AMR94/5 (revised version), School of Mathematics, The University of New South Wales, 1994.

Solution of Complementarity

Problems

105

[38] S. M. Robinson, Some continuity properties of polyhedral multifunctions, Mathematical Programming Study 14 (1981) 206-214. [39] S. M. Robinson, Generalized equations and their solutions, Part II: Applications to nonlinear programming, Mathematical Programming Study 19 (1982) 200-221. [40] K. Taji and M. Fukushima and T. Ibaraki, A globally convergent Newton method for solving strongly monotone variational inequalities, Mathematical Program­ ming 58 (1993) 369-383. [41] P. Tseng, Growth behaviour of a class of merit functions for the nonlinear comple­ mentarity problem, Technical Report, Department of Mathematics, University of Washington, Seattle, 1994. [42] P. Tseng and N. Yamashita and M. Fukushima, Equivalence of complementarity problems to differentiable minimization: A unified approach, Information Science Technical Report NAIST-IS-TR94005, Nara Institute of Science and Technology, Graduate School of Information Science, Nara, 1994. [43] A. P. Wierzbicki, Note on the equivalence of Kuhn-Tucker complementarity con­ ditions to an equation, Journal of Optimization Theory and Applications 37 (1982) 401-405. [44] N. Yamashita and M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complementarity problems, Journal of Optimization Theory and Applications, to appear.

J. B. G. Frenk and J.

106

Gromicho

Recent Advances in Nonsmooth Optimization, pp. 106-120 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

An Elementary Rate of Convergence Proof for the Deep Cut Ellipsoid Algorithm J. B. G. Frenk Econometric Institute, DR Rotterdam, The

Erasmus University Netherlands

Rotterdam,

P.O.Box

1738, NL - 3000

J. Gromicho Tinbergen & Econometric Institute, Erasmus University Rotterdam, P.O.Box 1738, NL - 3000 DR Rotterdam, The Netherlands and Departamento de Estatistica e Investigaccao Operacional, Faculdade de Ciencias, Universidade de Lisboa, Bloco C2 - Campo Grande, Cidade Universitaria, P - 1700 Lisboa, Portugal

Abstract

In the literature several variants of the ellipsoid algorithm for solving nonsmooth convex optimization problems are discussed, sometimes in combination with a rate of convergence proof. Unfortunately, almost all of these proofs lack simplicity and fail to explain the effect of so-called deep cuts on the convergence rate. In this paper we present an extremely simple and geometrically intuitive proof that overcomes these limitations. Moreover, our proof applies to a lesser known variant of the ellipsoid algorithm which tries to overcome some of the numerical instabilities of the classical versions.

1

Introduction

T h e first explicit s t a t e m e n t of the ellipsoid algorithm is due to Shor ([23, 25]) who dis­ covered this m e t h o d through his work on space dilation in subgradient optimization ([21, 22, 24]). Moreover, Yudin and Nemirovskii ([17, 26, 27]) pointed out t h e im­ plications of this algorithm in complexity issues for convex p r o g r a m m i n g . Following Shor's papers different versions of the ellipsoid algorithm appeared in t h e literature.

Deep Cut Ellipsoid

Algorithm

107

Among them we mention the versions discussed in the computational oriented pa­ pers of Ecker and Kupferschmid ([4, 5]) and Dziuban, Ecker and Kupferschmid ([3]). Around the same time Goffin ([9]) completed in detail the incomplete proofs of Shor and of Yudin and Nemirovskii and using a rather complicated proof he derived a similar rate of convergence result as discussed in the present paper covering only the central cut version applied to an unconstrained nonsmooth convex optimization prob­ lem. The proof was extended to the constrained case by Luthi ([15]) still covering only central cuts. Contrary to our elementary and geometrically intuitive approach both the proofs of Goffin and Luthi need a deep result in convex analysis about vol­ umes of so-called concave arrays. Observe that Frenk, Gromicho and Zhang gave in [8] a convergence proof of a version of the ellipsoid algorithm applied to a constrained nonsmooth convex optimization problem showing the beneficial influence of deep cuts in the convergence rate. This proof, contrary to the previous ones, is based on simple results for convex functions and can be generalized to the larger class of so-called lower subdifferentiable functions ([18]). However, the geometrical interpretation of the proof given in [8] is not immediately clear. Subsequently, the same authors sim­ plified in [7] the proof for the unconstrained case by replacing the proof given in [8] by a more geometrically intuitive approach. This approach is now extended in this paper to the constrained case using related techniques.

2

The Algorithm

The term convex programming applies to the problem of minimizing a convex function over a closed convex set. To mention some fields of quantitative decision making these problems occur frequently in engineering, economics and management science. In this paper we only consider finite dimensional instances of the problem. Therefore our universe will be the s-dimensional Euclidean space 1R3. To be more precise, a finite dimensional convex optimization problem is given by inf {/(as) .x£R3,

g,(x) < 0, t = 1 , . . . ,n)

(P)

with / , <7; : iR*—> M, i = 1, . . . , n , denoting a set of convex finite valued functions over the s-dimensional Euclidean space. Since each function
J. B. G. Frenk and J. Gromicho

108

be applied to general instances of (P) assume in most cases that the objective function f and the constraint functions gt, i = 1 , . . . , n, are differentiable ([2, 6, 14]). The ellipsoid algorithm does not require differentiability. Moreover, since the maximum of a finite number of finite valued convex functions is finite valued and convex we may take in the definition of (P), without loss of generality, the number of different constraint functions equal to one, i.e. n = 1. In fact, gt(x) < 0 for every i = 1 , . . . ,n if and only if maxi<,< n gi(x) < 0. For simplicity we denote this single constraint function by g instead of g%, A similar argument applies to the objective function / and so optimization problem (P) also covers min-max problems. In order to introduce a version of the ellipsoid algorithm to solve (P) we make the following assumption. Observe that we denote by B the open Euclidean unit ball. A s s u m p t i o n 2.1 An optimal solution x" of the optimization problem (P) exists sat­ isfying x* g ao + rB with ao g Ms and r > 0 known in advance. By the above observations we may assume (without loss of generality) that a con­ vex programming problem is defined by two convex functions, the objective function and the constraint function, and therefore it has the following description. min{/(x) : x £ Ms, g(x) < 0}.

(C)

We now introduce the definition of level sets. Definition 2.2 For a given function tp : M"—> IR the so-called level set of level a is given by £=(«) := {as € M3 : ¥>(«) = ° } while the so-called lower level set of level a has the form C^(a):={xeRs:^(x) 2R an affine function that C^(y) is an hyperplane for every y € M and so Cj^(y) is an halfspace. We shall call this set a lower halfspace. To finish this section we mention a result which is an immediate consequence of the subgradient inequality for convex functions and this result will be extremely useful in the next section. L e m m a 2.3 Let

tp(a) + h(x) for every x g M3. Now the result follows immediately by the definition of a lower level set. □

Deep Cut Ellipsoid

3

Algorithm

109

The Ellipsoid Method

In this section we assume the existence of an oracle that for each convex function involved in the definition of (C) is able to provide at every point of its domain the function value and an element of the subgradient set. Thus, we will freely use f(x) and g(x) for different instances of x and take elements of the sets df(x) and dg(x). The main idea of the ellipsoid algorithm is the following. By Assumption 2.1 there exists a sphere with center a0 containing an optimal solution. Subsequently an oracle (to be detailed) provides an hyperplane including the center of the sphere and with the property that the corresponding lower halfspace includes all the optimal solutions. Clearly, by Assumption 2.1 an optimal solution belongs to the intersection of the initial sphere and the lower halfspace and this halfsphere has half the volume of the sphere. It is now possible to compute an ellipsoid with minimal volume containing this intersection. We now replace the initial sphere by the new ellipsoid and repeat the procedure. Depending on the information available at the present stage of the algorithm it is convenient to take less than half of each ellipsoid whenever possible. We refer to the first type of cuts, going through the center of the ellipsoid, as central cuts and to the second type of cuts, that leave the center of the ellipsoid in the part to be neglected, as deep cuts.

Figure 1: The central and the deep cut ellipsoid methods In Figure 1 one can see the difference between the two types of cuts. The first picture represents a central cut on a sphere and the minimal volume ellipsoid that includes the half sphere. The second picture shows the same sphere and a cut parallel to the first but shifted halfway along the radius of the sphere. One can see in this case that the ellipsoid with minimal volume including this part of the sphere is indeed smaller than the one in the previous picture. The minimum volume ellipsoid required at each step is easy to compute if one finds such a (central or deep) cut. In order to recall how, we first need to introduce a mathematical description of an ellipsoid. A set £ C M" is called an ellipsoid if there exists a vector a G M° and a positive

110

J. B. G. Frenk and J. Gromicho

definite s X s-matrix A such that £ = £(A; a) := {x {as £ tf? R':a : (as (as -- afA-\x a)TA-1(a! -- a) a) << ll}} .. Moreover, in order to determine whether a given hyperplane in M" with normal a* intersects an ellipsoid £(A;a) we observe ([11]) that

and

min{a*Tas : as £ f(A; £(A; a)} = a*Ta - V^Atf V^Atf

(1)

max{a*Tx : as £ £(A; a)} = a*Ta + V^Atf. max{o* V^AH*.

(2)

T

This implies that the hyperplane C^(/3) with h(x) := a* (x - a) has a nonempty intersection with £{A;a) whenever -y/a^Aa* < -p < y/a*TAa* If this holds the hyperplane is called a valid cut. It is shown in [11] that for - 1 / s < a < 1 and a := ~P/y/a*TAa* a minimum volume ellipsoid containing the intersection £{A; a) (1 C% (/?) exists and this new ellipsoid has a strictly smaller volume than £{A; a). Moreover, for a = 1 the intersection of the lower halfspace and the ellipsoid reduces to a single point and there is no need to proceed. To bring the exposition into the framework of an iterative algorithm let us denote the current ellipsoid by £(Am;am) and the corresponding cut by C^Jpm) with hm(x) := < T ( x - am). Finally, denottng the depth of the current cut by 0 < am := :=

m ~f / " sJ
one can show ([1]) that the ellipsoid £(Am+1;am+i)

< < 11 with center given by

am+l •— a m - rrmmb6mm and matrix Am+1 m+l

(3)

ammbmmbTTJ := 6mm(Amm - <J

(4)

with updating values .

6m =

'-

s2(l-a2Jm)

s2-1

'

am: am:

-(, -(,

2(1 2 ( 1 +sa + samm))

l ) ( l++ QQmmy) ' + l)(l

r T:

1 +l+sa sam

- ™-:-^TT ^rr

and

\Ja*mAma*m is t , e minimum volume elliDso:J containing £(A . « ) H C- (8 ) We note here that for am = 0 (resp. 0 < am <1) the hypwplane is called a valid central cut (resp. valid deep cut).

Deep Cut Ellipsoid

Algorithm

111

Taking the same matrix Q as described on page 151 of [16] and copying with some obvious modifications the proof of Propositions 2.7 and 2.8 of [16] one can show that Am+i is positive definite given that a2m < 1 and Am is positive definite. Since in this section cuts are generated by means of subgradients the following result is useful to determine when these cuts are valid.

L e m m a 3.1 Let

Proof: Observe by the subgradient inequality, x G £{A;a)

and (1) that

0 <
= Va*TAa* and hence by (1) with /9 := £ —
D

The ellipsoid algorithm is well-known for the occurrence of numerical instabilities. These instabilities are related to the fact that each time a new ellipsoid is generated this new ellipsoid is not completely included in the previous one, bringing new points into consideration (see Figure 1). The inclusion of new points may induce the ellipsoid to elongate along one of its axes in such a way that eventually it may become "flat" on one of the other 5 — 1 axes. An effect of the potential elongation of the ellipsoid is that the center of the present ellipsoid may end up extremely far away from the initial ellipsoid. In order to try to overcome this we introduce the concept of norm cuts. Such cuts appeared first in [8]. The idea is to remember Assumption 2.1 at each iteration and not as for the basic version to use this information only to initialize the algorithm. As the next section shows the inclusion of this new cut permits a very simple convergence proof. Thus, if it happens that the center am of the current ellipsoid is outside the first ellipsoid then a cut is generated using the function n(x) := ||SE — a 0 || 2 . A geometrical interpretation of this cut is given in Figure 2. Before discussing the detailed steps of how to implement the oracles yielding the different cuts we first list the improved version of the algorithm.

J. B. G. Frenk and J. Gromicho

112

Step 0 let m := 0, Am := r2I and Ci-i := +o°; Step 1 if am satisfies some stopping criteria then stop else goto Step 2; Step 2 ifn(am) > r then (apply a norm cut] else if g{am) > 0 then (apply a constraint cut] else (apply an objective cut]; Step 3 (update the ellipsoid], let m := m + 1 and return to Step 1

v

y

The above algorithm requires the specification of four different procedures marked as framed statements. To start with a norm cut we observe the following. It follows by Lemma 2.3 and Assumption 2.1 that x' G £(Ao',ao) = ££(r) Q ^Km(r ~ n(am)) with hm(x) := Vn(a m ) T (i — a m ) and Vn(am) = ,.° m J°S, . Consequently the optimal point x* belongs to the lower halfspace £^m(/3m) with /3m := r — n(am). The validity of this norm cut follows now from i * G £(Am; am) and Lemma 3.1 and so the norm cut reduces to the following procedure. let o m := {n(am) -

r)/yJVn(a m ) T A m Vn(a m ) J

Clearly, after performing a norm cut if follows that x' £ £(Am+1;am+1), In order to apply a constraint cut we observe by Lemma 2.3 that £ | ( 0 ) C £/Tm( — 0 and so the constraint cut reduces to the next procedure.

Observe, since £J=(0) is nonempty and g(am) > 0 that a*m can not be zero. It is also clear after performing a constraint cut that x" G £(Am+i\ am+1). Moreover, to apply an objective cut we observe the following. Since / is finite and convex on 1RS it follows for every x G £j(0) that the subgradient set df(x) is nonempty ([19, 12]) and hence for every a*m G df(am) the so-called subgradient inequality /(as*) > f(am) + hm(x) holds with hm(x) := al£(x - am). Observe, if a^ = 0 then am is optimal and therefore there is no need for a cut. For a derivation of a deep or central valid cut with respect to / introduce £m := min{/(ajt) : y(a^) < 0, 0 < k < m} and observe by Lemma 2.3 that x~ G CJ{lm) C C^m((m f(am)).

Deep Cut Ellipsoid

113

Algorithm

Hence x~ must belong to the lower halfspace £ j (/?m) with /?m := £m — f(a.m)- The validity of this cut follows again by x" G £(Am;am) and Lemma 3.1. Clearly this is a valid deep cut whenever Zm < f(am) and this deep cut can be derived using only negligible additional computer effort. The objective cut now reduces to the next procedure. if f(am)

< C _ ! then let £m := f(am eJselet £m := £m-i; take a*m G df(am); if a*m = 0 then stop eise let am := (f(am) -

em)/^/a£Ama*

It is also clear after performing an objective cut that x* G £(Am+i; a m +i). Finally the update of the ellipsoid in S t e p 3 is done by applying formulas (3) to the center and (4) to the matrix. This concludes the description of the four procedures necessary to complete the ellipsoid algorithm. The technique to generate deep cuts using the subgradient inequality was first proposed by Shor and Gershovich in [25]. In the next section we give an easy and geometrically oriented rate of convergence proof for this version of the ellipsoid algorithm.

4

T h e Proof

To start this proof we need the following result. L e m m a 4.1 For each matrix A G J? 3XS with det(A) / 0 and each pair of vectors a,b€M' we have det(A + abT) = (1 + 6 T A" 1 a)det(>i). Proof: Observe by well-known properties of determinants ([13]) that det(>l + aV) = d e t ( [ ;

= det('1 + which completes the proof.

A

^ fc

] ) = det

1 -a

6T A

^f° ° T ])=(l + 6^a)det(A) n

We now assume that the ellipsoid algorithm has already performed m steps, m = 1,2,..., with centers ak, 0 < k < m, and no optimality check or stopping rule was applied.

J. B. G. Frenk and J. Gromicho

114

We may assume without loss of generality that 0 < a* < 1 and a*k ^ 0 for every 0 < k < m since a^ = 1 would mean that £(Ak+i; at+i) reduces to a point and a*k = 0, only possible for the objective function / , would make the algorithm stop. The following result is fundamental for our proof. For the definition of the se­ quences £m and /?m and the functions n and hm we refer to the previous subsection. Lemma 4.2 For each m > 0

cf(em)ncf(o)nc$(r)

C

£(Am;am)nC^(0m)

holds. Proof: Recall first that C^(r) = £"(j40;ao)- Now observe that in each iteration the ellipsoid algorithm applies either an objective, a constraint or a norm cut. By Lemma 2.3 we obtain in case of an objective cut that Cj(£m) C £ S m (/? m ), while a constraint cut satisfies £ | ( 0 ) C £j7m(/?m) and a norm cut ££(r) C Cnm(fim). The result follows now easily by induction since £m is nonincreasing and £(Am;am) n

CZjpm)C£(Am+l;am+l).

a

In order to prove the main convergence theorem we need the following regularity condition. This condition is the strong Slater condition (cf. [12]). Assumption 4.3 There exists some x € a0 + rB with g(x) < 0. The following result will also be useful for the proof of the main convergence theorem. Lemma 4.4 Let

z+^

W

with Lipschitz

£<(,).

Proof: Take x £ z + ^f^B. It follows that ||x - z\\2 < y-=£p- and this implies by the Lipschitz continuity of the function ip that y?(x) — v>(2) — IvC35) — v ( z ) l ^ Lv\\x — z\\2 < y — v(z). From this inequality we obtain that 1 and so -A- < 1.

Deep Cut Ellipsoid

Algorithm

115

Theorem 4.5 If the ellipsoid algorithm executes an infinite number of iterations then it follows that £m J. / ( * * ) . Moreover, if f is Lipschitz continuous on £ | ( 0 ) (~l C£(r) with Lipschitz constant Lj and g is Lipschitz continuous on C£(r) with constant Lg then there exists some m 0 such that

5

^-«^ ^?(i)'!^

-Qk otk

for every m > m0. Proof: We start by evaluating det(A m ). From (4) and Lemma 4.1 it follows by induction that m-1

det(Am) = det(,4o) I I (**(* ~ »*)) • k=0

Since Ao = r2I and Am is positive definite for every m we obtain after some calcu­ lations that

o<det(^)=^n(a"(i-^(^)<^(i),m and so it follows using ab > 1 that det(j4 m ) —» 0. By the convexity of £ < ( 0 ) n £ < ( r ) , Assumption 2.1 and Assumption 4.3 it follows that the line segment [£,»:*[ := {Ax + (1 — A)x" : 0 < A < 1} is contained in £<(o)n£< f(x*) for every m > 0 and so we obtain that c := lim mToo £ m exists and c > f(x*). We will now show by contradiction that c equals f(x*). Suppose therefore c > f(x'). If c < f(x) then from the continuity of / it follows that there exists an x S ]x, x'[ with f(x) = c. If c > f(x) then take x equal to x. In both cases this yields by the convexity of / that x := (x + x')/2 6 Cf (c) D £<(0) D £<(r) and therefore, since Cf{c) D £< (0) n £<(r) is an open set there exists some 6 > 0 such that x + SB C Cf(c) n £<(0) D £<(r). Hence from Lemma 4.2 and £m J. c it follows that x + SBC Cf(em) n £<(0) n £<(r) C £ ( A m ; a m ) n ££ m (/? m ). Finally, since vol(£(>l m ; a m ) ) = yfdet(Am)va the previous inclusion that

with u3 := vol(B) ([11]), we obtain from

0 < 6'v, = vol (x + SB) < vol (£{Am; am) n £^(/?m)) < i vol(£(A m ; o m )) = i y d e t ( J 4 m ) v , for every m > 0 and this contradicts det(A m ) —» 0. Hence it must follow that £m I /(**) a n < l s o t n e n r s t P a r * >s proved.

116

J. B. G. Frenk and J. Gromicho

Figure 2: A norm cut

Figure 3: Geometric interpretation of the proof

Deep Cut Ellipsoid Algorithm

117

To prove the stated inequality we first assume that every optimal solution a;* satisfies g(x') = 0. Since (m I f{x") and by our assumption / ( g ) > f(x') there exists some m, such that

/(»*) /(*') < 4, < /(«)

for every m>mx. The continuity of / enables us to create the sequence xm G [£, x'[ w i t h / ( x m ) = lm. Now we use this sequence to create the sequence xm := {xm+x')/2 (see Figure 3) and for this new sequence it follows by the convexity of / that f(xm) < Hence by Lemma 4.4 we obtain that im xm

in <(U + ^-f(*~)BcC + -Tf{ia). BcCj(lm).

Recall now from the convexity of / and lm = f(xm)

(5) (5)

that

C ~ /(»m) >^ tCm- ~ /f(x') C (»') | | x m - x m | | 2 ~ | | x« m - x«*- | | 2, and, by construction, \\xm - x'\\2 = 2||x m - x m || 2 . This yields that tm - f(xm) {lm - /(x*))/2 and thus (5) implies that

>

i.^-nc^). 2L/

(6) (6) 2Lf On the other hand, by the convexity of g we obtain that g(xm) < 0 and applying again Lemma 4.4 yields that (7) C?)

^ / " ^ S C ^ O ) . LLgg

Now, from the convexity of g, g(x") = 0, and the Lipschitz continuity of / with Lipschitz constant Lf it follows that

1 , ^ ,-J|x*-xm||2 ^ ... * » - / ( » • ) 9{x) -*(*») > --^f^) ^ f ^ ) ^^ --g^ g a2|l«*-a|l, l l s ' - £ | | , "- " ^ ^~L . 2Lj\\x--x\\ l l x ' - x l b2 -*(*») and this, together with (7), leads to + Xmm +

*

-g(x){i -g(x){£mm - / (f(x')) **))„ < K 2 L / L J x * - xx\\, | | 2 BS CC£ * 3( 0( 0)) 2L,L,\\x--

Combining (6) with (8) and observing that -g(x) Xm

+

f(X )] ' Bc 2L}Lg\\x' -x\\2 }Lg\\x'-x\\2

((8) 8

< Lg\\x' - x\\2 finally yields

C<(i„. ) n £ < ( 0 ) .

)

118

J. B. G. Frenk and J. Gromicho

Since [x,x'[ C C<(r) there exists an e > 0 such that i + J C x € [x,x*[. Taking now m2 such that for m > m2 -g{x)(£ -g{x)(£mm - /(«*)) 2L 2LfL/ IJx*-x|| g\\x'-x\\2 2

£<(r) for every

<£

"

it follows by Lemma 4.2 for m > m0 := max{m 1 , m2} that

-**®1-"

<

(f

) n £*-(()) n C^fr)

a Q£(A C£r(A n £ ^ (An). m ro; ;omro))n£^(A»).

Thus

-(^«3?-)*-«^<.*««.
and computing these volumes gives

(-g(x){lmm-f{x'))\\_ (-g(x)(i - f(x'))Y ii 2L,L \\x'-x\\ ) 9 2 2L/La||x--x|| 2 J

1 / 1 \ * /I ^ 11 I 2 . m— I 2 V./1-<M r2 T T / M ' / (1 al) r ( 1 _ a J '{lVTT^r+ akh" ' - '~2\ 2 \ | °E\ab) /iUJ J-V\

V

Dividing the previous inequality by v„ raising both sides to s" 1 and multiplying by 2L L ' '}fi~*[h yields the desired result. To complete the proof we still have to consider the case when an optimal solution x" exists satisfying g{x") < 0. It is not difficult to verify that for this case the same result holds, since in fact im can be taken equal to x* for every m > m0 for which <"-/(*•) < e with s > 0 satisfying x'+eBC £<(0) n £<(r). Thus, from Lemma 4.4 we conclude that

x. J\Xx )> Q x* i. *-m m ~ f( c £
Lf

Lf

n n

g g

and from here on one may proceed to achieve the same result.

D

Finally, we would like to remark if an unconstrained instance of (C) has to be solved then it follows from the last steps of the proof (see also Ref [7]) that

o<em

-«"^U) S^ T

/

-i

\ "I

m-1

-

^

/ ,i a*

Deep Cut Ellipsoid

Algorithm

119

References [1] R. G. Bland, D. Goldfarb and M. J. Todd, The ellipsoid method: A survey, Operations Research29 (1981) 1039-1091. [2] D. den Hertog, Interior point approach to linear, quadratic and convex program­ ming - algorithms and complexity, volume 277 of Mathematics and Applications, Kluwer Academic Publisher, 1994. [3] S. T. Dziuban, J. G. Ecker and M. Kupferschmid, Using deep cuts in an ellipsoid algorithm for nonlinear programming, Mathematical Programming Study 25(5) (1985) 93-107. [4] J. G. Ecker and M. Kupferschmid, An ellipsoid algorithm for nonlinear program­ ming, Mathematical Programming 27 (1983) 83-106. [5] J. G. Ecker and M. Kupferschmid, A computational comparison of the ellipsoid algorithm with several nonlinear programming algorithms, SIAM Journal on Control and Optimization 23(5) (1985) 657-674. [6] A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Uncon­ strained Minimization Techniques, Wiley, New York, 1968. [7] J. B. G. Frenk, J. Gromicho and S. Zhang, General models in min-max con­ tinuous location: Theory and solution techniques, Technical Report TI 93-175, Tinbergen Institute, Rotterdam, The Netherlands, 1993. To appear in Journal of Optimization Theory and Applications. [8] J. B. G. Frenk, J. Gromicho and S. Zhang, A deep cut ellipsoid algorithm for convex programming: Theory and applications, Mathematical Programming 63(1) (1994) 83-108. [9] J. L. Goffin, Convergence rates of the ellipsoid method on general convex func­ tions, Mathematics of Operations Research 8 (1983) 135-150. [10] D. Goldfarb and M. J. Todd, Linear programming, volume 1 of Handbooks in Operations Research and Management Science, chapter II. North-Holland, Amsterdam, 1989. [11] M. Grotschel, L. Lovasz and A. Schrijver, Geometric Algorithms and Combina­ torial Optimization, Springer-Verlag, Berlin Heidelberg, 1988. [12] J.-B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms I: Fundamentals, volume 305 of A Series of Comprehensive Studies in Mathematics, Springer-Verlag, Berlin, 1993.

120

J. B. G. Frenk and J. Gromicho

13] P. Lancaster and M. Tismenetsky, The Theory of Matrices, New York, second edition, 1985.

Academic Press,

14] D. G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley, Reading Massachusetts, 1984. 15] H. J. Luthi, On the solution of variational inequalities by the ellipsoid method, Mathematics of Operations Research 10 (1985) 515-522. 16] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Wiley, New York, 1988.

Optimization,

17] A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, John Wiley & Sons, Chichester, 1983. 18] F. Plastria, Lower subdifferentiable functions and their minimization by cutting planes, Journal of Optimization Theory and Applications 46(1) (1985) 37-53. 19] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. 20] R. T. Rockafellar, Conjugate Duality and Optimization, 1974.

SIAM, Philadelphia,

21] N. Z. Shor, Utilization of the operation of space dilation in the minimization of convex functions, Cybernetics 6 (1970) 7-15. 22] N. Z. Shor, Convergence rate of the gradient descent method with dilation of the space, Cybernetics 6 (1970) 102-108. 23] N. Z. Shor, Cut-off method with space extension in convex programming prob­ lems, Cybernetics 13 (1977) 94-96. 24] N. Z. Shor, Minimization Methods for Non-differentiable Functions, series in computational mathematics, Springer-Verlag, Berlin, 1985.

Springer

25] N. Z. Shor and V. I. Gershovich, Family of algorithms for solving convex pro­ gramming problems, Cybernetics 15 (1979) 502-508. 26] D. B. Yudin and A. S. Nemirovsky, Evaluation of the informational complexity of mathematical programming problems, Matekon 13(2) (1976) 3-25. 27] D. B. Yudin and A. S. Nemirovsky, Informational complexity and efficient meth­ ods for the solution of convex extremal problems, Matekon 13(3) (1977) 25-45.

Nonsmooth

Equations

by Means of Quasi-Newton

with Globalization

121

Recent Advances in Nonsmooth Optimization, pp. 121-140 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

Solving Nonsmooth Equations by Means of Quasi-Newton Methods with Globalization Marcia A. Gomes-Ruggiero, Jose Mario Martinez and S a n d r a Augusta Santos Department of Applied Mathematics, State University of Campinas, CP 6065, 13081 Campinas SP, Brazil

Abstract

We consider the utilization of quasi-Newton methods for solving nonlinear sys­ tems of equations, without smoothness assumptions. In order to improve the global convergence properties of the algorithms, we use a globalization strat­ egy based on a merit function. We adopt a tolerant procedure that permits a nonmonotone behavior of the merit function. We test our methods with a collection of large scale nonsmooth systems originated in nonlinear complemen­ tarity problems.

1

Introduction

We consider t h e resolution of nonlinear systems of equations F(x)

= 0

(1)

without smoothness assumptions on t h e m a p p i n g F : ( l C lRn —» IRn Methods for solving (1) are iterative. Quasi-Newton m e t h o d s , originally developed for smooth systems, g e n e r a t e sequences {xk} according to

xk+1 = xk- BklF(xk),

(2)

See [6], [7]. T h e quasi-Newton strategy consists in considering t h a t , choosing Bk in an a p p r o p r i a t e way, we have F{x)*Lk(x)

= Bk{x-xk)

+ F(xk),

(3)

122

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

at least in a neighborhood of the current point xk. Newton's method (for smooth systems) chooses Bk = F'(xk). See [7], [32]. Secant methods choose an arbitrary 5 0 and update the successive "Jacobian approximations" Bk in such a way that Bk+lsk

= yk

(4)

for all k = 0 , 1 , 2 , . . . , where sk = xk+i — xk and yk = F(xk+i) — F(xic). The "secant equation" (4) guarantees that the affine function Lk(x) defined on (3) satisfies Lk(xk) = F(xk)

and Lk(xk-i)

= F(xk--i).

(5)

The local convergence theory of secant methods for smooth systems of equations is well-developed. See [2], [7], [8], [25], [26]. Some authors (see [3], [4], [5], [21], [29]) studied quasi-Newton and secant methods for different nonsmooth problems, but a local convergence theory with sufficiently general assumptions is far from being complete. In spite of this limitation, the iterative approximation of a nonsmooth F by an affine interpolatory function is an appealing idea that deserves experimental investigation. This is one of the aims of this paper. In order to improve the global convergence properties of local algorithms, strate­ gies based on the minimization of a merit function / (most frequently f(x) = ||.F(£)|| 2 ) are generally used both in the smooth and the nonsmooth case. Martinez and Qi [28] considered one of these strategies in connection with the so called inexact iteration based on the Newton method. See also [20]. In this paper we generalize that strategy in order to consider completely arbitrary directions without smoothness or semismoothness hypotheses on F. We prove a global convergence theorem related to this strategy. We implement an algorithm that is able to deal with large nonsmooth systems. In this implementation we combine local (quasi-Newton) and global iterations using a tolerant strategy that calls to the global (special) iteration, which is more expensive, only when it is necessary. This strategy has been used for smooth systems in [12] and for some inverse problems in [9]. We use our methods to solve a collection of problems of dimensions 100 x 100 and 1000 x 1000. This paper is organized as follows. In Section 2 we introduce a general "global algorithm" for solving nonsmooth systems and we prove global convergence results. In Section 3 we describe a practical implementation (for large-scale problems) of the global algorithm. In Section 4 we define the quasi-Newton methods used in our study. In Section 5 we describe the tolerant strategy. The numerical experiments are reported and commented in Section 6.

2

Global Algorithm

In this section we analyze the convergence properties of a general model algorithm under minimal assumptions on F. In particular, no smoothness assumptions will be

Nonsmooth Equations by Means of Quasi-Newton with Globalization

123

made. As many methods for solving both smooth and nonsmooth equations, the algorithm is based on the monotone reduction of a merit function / . Usually, we choose

/(«) = ^ ( * ) H 2 n

(6) n

However, any function / : R -* R such that f(x) > 0 for all x £ R and f(x) = 0 iff F(x) = 0 will serve for our purposes. If F is not defined for some x € Rn, we define f(x) = oo. The main global algorithm, which use elements of the approaches of [10] for smooth problems and [28] for semismooth problems, is described below. Algorithm 2.1. Assume that cr G (0,1), 77 G (0, | ] . Choose x0 G Rn, an arbitrary initial approximation such that f(x0) < 00 and set a 0 = 1. Given xk G Mn, ctk 6 (0,1], the steps for obtaining xfc+i,ajfc+i are: Step 1. Choose dk G Rn (7) Step 2. If f{xk+akdk)
(8)

(9)

define ak+\ = 1. Otherwise, choose O/t+i 6 [yotk, (1 - r))ak].

(10)

Observe that Algorithm 2.1 is more general than line-search or backtracking meth­ ods (see [7]) since the "direction" dk can change after a failure of (8) or (9). We will take advantage of this feature in the practical implementation. We denote by K\ the set of indices of the ''very successful" iterations: K, = {keJN

I (9) holds}.

(11)

Let us now prove the convergence results related to Algorithm 2.1. The thesis of the convergence theorems will always be lim/t_0O f(xk) = 0. Clearly, if x, is a limit point of {xk} and / is continuous at x, this implies that f(x,) = 0. Lemma 2.1 Let {xk} be the sequence generated by Algorithm 2.1. If Y, log(l - o-ak) = - 0 0 ,

(12)

lim /(**) = 0.

(13)

the k —+00

124

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

Proof. By (9), for all k G Kt we have log /(x* + 1 ) < log(l - aak) + log Therefore, since f{xk+1)

f(xk).

< f(xk) for all k G W,

fog / ( * * ) <

l o g ( l ~ f f Q > ) + l o e //((ls0a ) E l°g(l~<">,•)+loe ieK, i
So, by (12), lim log f(xk) = - o o .

k—i-oo

□ D

This implies that /(x fc ) -»00

Lemma 2.2 Let {xk} be the sequence generated by Algorithm 2.1. Then, either lim^00/(xfc) = 0 or there exists K2l an infinite subset of IN, such that

lim akk = 00 and

/f(x( kx t++a^kd)k)-f(x - / (k)x t )

>>

(14) (14)

(

}

otk otk

(15)

forallkGK2. Proof. By Lemma 2.1, if (13) does not hold, either Kt is finite or E

log(l - aa
If #1 is finite, Kx C { 0 , 1 , . . . , fc0}, we have that (9) does not hold and ak+1 < (l-r,)ak for all k > k0. So, at -> 0 in ntis sase, and dth eesult ti sroved. If Kx is infinite and the series £*<=*, l°g(l - aak) converges, we necessarily have that ak -» 0 0orrcG Kt. Thereforee ak < 1 for rarge enough h G &i. Now, ,ince a* > 7<**-i) rjotk-i, we also have that «*_i -» 0 for fc G AV Moreover, since ak < 11 it follows that (9) does not hold at iteration fc - 1. So, (14) and (15) hold defining A 2 = {fcG W W|fc |fc + 1 e l ( , } . This completes the proof.

□

Lemma 2.3 Let {xk} be the sequence generated by Algorithm 2.1. Assume that there exist a G (0,1) and J, = {juj2l...}, an infinite subset of Kx such that a<*j, > |

>- ~ 7

for all i = 1,2,.... Then lim f(x /(xkfc) ) = 0. *:—oo

(16) (16)

Nonsmooth Equations by Means of Quasi-Newton with Globalization

125

Proof. By the fact that log(l - aak) < 0 for k G W and by (16), we have that £ fceft'i

log(l - aak) < Y. log(l - a a t ) < £ log(l - -r-). teJj

*=i

(17)

K

But, by the integral criterion, the series on the right hand side of (17) diverges, so the same happens with the series on the left hand side. Therefore, the desired result follows from Lemma 2.1. Q Lemma 2.3 suggests the following especialization of Algorithm 2.1. Algorithm 2.2. Assume that
f(xh + akdk) - f(xk)

(18)

< — crJ(Xk)

Oik

whenever

a at < — mk If such a choice is not possible, stop. (The algorithm breaks down.) Step 2. If (8) holds, define xk+1 = xk + a ^ . Otherwise, define Xfe+1 Step 3. If (9) holds, define ak+i = 1 and mk+l

(19)

x k-

= mk + 1.

Otherwise, choose ajt+i G [»?ai, (1 — ri)oik} and define m^+i = mk. Lemmas 2.1, 2.2 and 2.3 allow us to prove the following theorem related to Algo­ rithm 2.2. Theorem 2.4 Assume that Algorithm S.2 does not break down and that {xk} is gen­ erated by this algorithm. Then lim /(**) = 0. Proof. Let us prove first that Ki is infinite. In fact, if A'i C {0,1,...,feo} we should have mk = m^ for all k > k0. But, since k £ Ki for all k > k0, we have that Ofc+i < (1 — v)ak for all k > k0. This implies that ak —> 0 and then, for some k > fc0, ak <

a a = —. mko mk

So, by the definition of the algorithm, (18) holds at iteration k. This implies that (9) holds. So, k G Ki, which contradicts the assumption of finiteness of K%.

126

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

Therefore, from now on, we assume that K\ is infinite. Let k £ K\. If ak = 1 we clearly have that ak > ^ . (20) mjfc If ak < 1, then k — 1 ^ Ki. So, mk = rrik-\- But, since (9) does not hold at iteration k — 1, we have that (18) does not hold at this iteration and, so, by the definition of Algorithm 2.2, a a a*-i > But ak £ [»?a*_i,(l - 7/)a/t_i], so Ck > Vak-i >

■qa

mk Therefore, we proved that K\ is infinite and that for all k £ Ki, (20) holds. As a result, we are under the hypotheses of Lemma 2.3, with K\ = J\ and a = rja. So, the desired result is proved. □

3

Implementation of the Global Algorithm

In this section we describe an implementation of Algorithm 2.2 for solving nonsmooth systems of equations, remembering that we are specially interested in large-scale problems. The main tool for our practical algorithm is a method for minimizing convex quadratics with box constraints developed in [13] and [14]. The idea is to choose, at each iteration, sk = a^dk as an approximate minimizer of

Ms) = \\\Vks + F(xk)f on an appropriate trust-region (see [11]) of the form ||s||oo < A) where Vk is a suitable n x n matrix. In semismooth problems we choose Vk £ dsF(xk) (see [28] and [35]). After the computation of sk, if ak < a/mk, we test the inequality (18). If this inequality does not hold, we stop the execution (the algorithm breaks down). This necessarily happens when the problem has no solutions. The choice of the || ■ ||oo norm instead of the Euclidean allows us to deal with bounds on the variables. In this case, the || • ||cx. norm fits well with the bounds and the approximate minimizers are not difficult to find. Observe that constraints are naturally considered in our formulation since we can define / ( x ) = oo if x is infeasible. Algorithm 3.1 Let a 6 (0,1), r/ € (0, | ] , a e (0,1), tol £ (0,1), max £ IN be given independently of k. Let xo £ Mn be an arbitrary initial point, such that / ( i o ) < oo, A 0 = M, mQ = 1 and a0 = 1. Given xk £ Rn, &k > 0, mk £ N and ak £ (0,1], the steps for obtaining xjt+i, Afc+i, mk+i and ak+\ are the following: S t e p 1. Compute 5^, an "approximate solution'' of

Nonsmooth Equations by Means of Quasi-Newton with Globalization

Minimize «/>*(*) = i||V kS + F(xk)\\2

s.t. H U < A*.

127

(21)

The approximate solution of (21) is obtained by applying the method described in [13] (see also [14]), stopping when \\VpMsk)\\
(22)

(where Vpif>k(s) is the projected gradient of V>* on the box Halloo < A*) or when the number of iterations used by the algorithm [13] exceeds max. Step 2. If ak < a/mk but (18) does not hold, stop (the algorithm breaks down). Step 3 . The same as Step 2 of Algorithm 2.2. Step 4. The same as Step 3 of Algorithm 2.2. Step 5. If ajt +1 = 1, define Afc+i = M. Otherwise, define Ajt+] = ||5*:||oo/2. The parameters used in our implementation were a = 10 - 4 , a = 10 - 5 , 77 = | , M = 103, tol = ^ j , max = 300. The software used for this implementation was an adaptation of the algorithm for box constrained minimization introduced in [14]. The algorithm used for obtaining the approximate solution of (21) (see [13]) is an active set method that combines conjugate gradient iterations with projected and "chopped" gradient iterations in such a way that many active constraints can be added or dropped in a single iteration.

4

Quasi-Newton Methods

As we mentioned in the Introduction, the idea of considering a linear system as subproblem for computing each iteration, using interpolation, is very attractive, not only because of its simplicity but also because of its success in the smooth case. In this study, we consider three quasi-Newton formulae for the implementation of the local iteration (2). The first one corresponds to the classical Newton's method. This choice can be made, for example if F is semismooth (see [31], [36]). In this case we choose Bk as one of the matrices Vj, in the generalized differential set dgF(xk). In large sparse problems, where each equation depends only on a few number of variables, % is a sparse matrix. The LU factorization of Vk, which is necessary for computing xk+\ in (2) was computed using a static data structure and partial pivoting as described in [15] and [18]. The other two quasi-Newton methods considered are Broyden's method and the Column-Updating method. See [1], [17], [23], [24]. In both methods we choose B0 as in Newton's algorithm and Bk+i in such a way that the secant equation (4) is satisfied for all k = 0 , 1 , 2 , . . . and the recurrence formula for obtaining Bk+i is B^

= Bk^-B;;fk)T

(23)

128

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

where Zk =

Sk

for Broyden's method and zk = ej>, \(e")Tsk\

= \\sk\U

for the Column-Updating method, ({e 1 ,... , e"} is the canonical basis of JRn.) Applying the Sherman-Morrison formula to (23) ([16], p. 51]) we obtain ^-fy^TB;>. (zkYBk yk Formula (24) shows that B£"+i c a n D e obtained from Bk^ using 0(n2) point operations in the dense case. Moreover, B^=B^

+

fl^x = (/ + «*(*0 T W 1 .

(24) floating

(25)

where uk = (sk - B ^ 1 j / k ) / ( z t ) T B ^ 1 ^ , so B;1 = (I +

Ufe_1(^_1)

T

) . - . ( / + u0(zo)T)Bo\

(26)

for k = 1 , 2 , 3 . . . Formula ( 26) is used when n is large (see [18] and [30]). In this case, the vectors u0,... ,uit_i, 20) ...,Zk-i are stored and the product BklF(xk) is computed using (26). In this way, the computer time of iteration k is O(kn) plus the computer time of computing BQ F(xk). If k is large the process must be periodically restarted taking

Bk « J{xk).

5

Tolerant Strategy

In Sections 3 and 4 we studied two ways of approximating a solution of (1). The first is to use the merit function f(x), applying the globally convergent Algorithm 3.1. If this algorithm does not break down at some iteration k, an approximate solution of (1) is computed, in the sense that (13) holds. The second is to use the recurrence (2). The global method is based on the monotonic behavior of f(xk). Many times, to impose f(xk+i) < f(xk) for all k is not satisfactory. In fact, at least for smooth problems, efficient local methods frequently converge rapidly to a solution but the generated sequence {xk} does not exhibit monotonic behavior in f(xk). In these cases, the pure local method is much more efficient than the monotone global method. Often, the monotone method converges to a local (nonglobal) minimizer of / , while the local method converges to a solution of (1). By these reasons, it is necessary to give a chance to the local method before calling the minimization algorithm. This necessity

Nonsmooth Equations by Means of Quasi-Newton with Globalization

129

has been considered by several authors (see [19]). Here we describe a strategy that combines local algorithms and minimization methods. A similar strategy has been used in [9] for some overdetermined systems coming from inverse problems and in [12] for large-scale differentiable nonlinear systems. Let us define "ordinary iterations" and "special iterations". By an ordinary iteration we understand an iteration produced by any local (quasi-Newton) method, like the ones described in Section 4. A special iteration is an iteration produced by Algorithm 3.1. We define, for all k € IV, wk=

Argmin

{f(x0),...,f(xk)}.

For completeness, we define f{wk) = f(x0) if k < q. Ordinary and special iterations are combined by the following algorithm. Algorithm 5.1. Initialize k <— 0, FLAG <— 1. Let q > 0 be an integer, 7 G (0,1). Step 1. If FLAG = 1, obtain xk+i using an ordinary iteration. Else, obtain xk+i using a special iteration. Step 2. If

/(**+,) < 7 / K - , )

(27)

set FLAG «— 1,k <— k + 1 and go to Step 1. Else, re-define xk+\ *— wk+i. Set FLAG < 1, k <— k + 1 and go to Step 1. If the test (27) is satisfied infinitely many times, then there exists a subsequence of {xk} such that lim f(xk) = 0. k—*oo

Conversely, if (27) does not hold for all k > kQ, then all the iterations from the &oth on will be special, and the convergence properties of the sequence will be those of Algorithm 3.1. The parameters 7 and q measure the degree of tolerance in the local algorithm. If q is large we admit a large number of iterations without enough progress. On the other hand, 7 says what we mean by "enough progress". The closer the real number 7 £ (0,1) is to the unity, the more tolerant the algorithm becomes. Therefore, the parameters 7 and q are essential to a satisfactory performance of our tolerant strategy.

6

Numerical Experiments

In a recent paper, Luksan [22] published a collection of 17 large-scale differentiable nonlinear systems of equations. For each Luksan's problem g,(x) = 0,i = l,...,n,

(28)

we associated a semismooth system of equations defining: 1, = ( 1 , 0 , 1 , 0 , . . . ) T

(29)

130

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

and, for all i = 1 , . . . , n, ft.(x\ _ I 9<(x) - gi(x.), i odd; \ 9i(x) - gi(x,) + 1, i even. Finally, we denned .F(x) = ( / i ( x ) , . . . , /„(x)) T , where for all i = 1 , . . . , n , /,(x) = min {xi,hi(x)}.

(30)

In this way, x» is a solution of the system F(x) = 0, which is equivalent to the nonlinear complementarity problem (see [33], [34]) x > 0, h(x) > 0, (x,h(x))

= 0.

We used the same initial points of [22]. We worked in a SUN Sparc Station 2 and used the SUN FORTRAN compiler, using single precision in the ordinary iterations and double precision in the special iterations. In the purely local methods, convergence is declared at Xk whenever ||F(xt)||2 < y'nlO - 5 and divergence is declared if either the number of iterations performed is greater than 100 or ||jF(a!i)||oo > 1020 In the globalized methods, convergence at iteration k is declared if ||.F(xjfc)||2 < \fnl0~b or Ajt < 10 - 1 0 . In the former we have convergence to a solution to (1) whereas in the latter Xk is a "strangled point", stationary for problem (6) but not necessarily a solution of (1), which corresponds to a breakdown at step 2 of the Algorithm 3.1. The results of the global methods are sensitive to the choice of the parameters 7 and q. We used 7 = 0.9 and q = 5 for all tests. The results of this set of experiments are summarized in Tables 6.1, 6.2 and 6.3 where, respectively, we present the performance of Newton's method, Broyden's method and the Column-Updating method both in their local and global versions. In the global version, every cycle of local iterations is executed with a Newton ini­ tialization. In our tables we adopted the following notation to present the numerical results: (IT, NFI, T) for the local methods and (IT (N,G), EVALF, NFI, T) for the global ones, where IT represents the total number of iterations performed; NFI = ||.F(x)||2/v^! where x is the vector obtained in the last iteration; T is the total time spent (in seconds) in the numerical phase; N is the total number of Newton iterations; G is the total number of special iterations; EVALF is the total number of evaluations of f(x). We observe that the symbolic phase is performed twice for each problem since we have two different dimensions (n = 100 and n = 1000). For the smaller dimension, it lasts 0.01 seconds on average. For n = 1000, the average time spent in the symbolic phase is 0.1 seconds.

Nonsmooth Equations by Means of Quasi-Newton with Globalization Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Dimension

Newton Local Version

Newton Global Version

n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000

(100, 0.5E-1, 1.04) (4, 0.2E-8, 0.34) (3, 0.3E-8, 0.04) (2, 0.1E-6, 0.19) (100, 0.2E+1, 1.16) (100, 0.2E+2, 9.52) (15, 0.9E-6, 0.15) (15, 0.3E-6, 1.27) (51, 0.5E-5, 0.59) (100,0.3, 10.72) (100, 0.1E+5, 0.83) (58, 0.1E+13, 3.72) (100, 0.2E+9, 0.81) (100, 0.6E+8, 6.76) (100, 0.2E+9, 1.18) (100, 0.7E+8, 9.86) (100, 0.5E+6, 1.43) (100, 0.2E+6, 13.34) (5, 0.5E-6, 0.05) (5, 0.3E-6, 0.48) (1,0.0, 0.01) (1, 0.0, 0.05) (6, 0.1E-11,0.04) (6, 0.1E-11,0.36) (100, 0.2E-3, 0.62) (100, 0.2E-3, 4.36) (100, 0.1E+1, 0.76) (100, 0.1E+1, 6.35) (100, 0.1E+8, 2.52) (100, 0.2E+9, 23.8) (4, 0.2E-7, 0.03) (4, 0.1E-6, 0.26) (100, 0.4E+15, 0.85) overflow

(24(10,14), 276, 0.2E-1, 3.1) (4(4,0), 5, 0.2E-8, 0.34) (3(3,0), 4, 0.3E-8, 0.04) (2(2,0), 3, 0.1E-6, 0.23) (37(7,30), 642, 0.1, 8.01) (100(5,95), 1605, 0.2, 2168.7) (11(8,3), 28, 0.0, 0.35) (23(15,8), 55, 0.0, 7.01) (35(22,13), 112, 0.4E-5, 6.72) (59(38,21), 145, 0.9E-5, 96.92) (66(10,56), 1178, 0.6,21.1) (12(4,8), 189, 0.1E+1, 20.4) (11(11,3), 31, 0.2E-11, 0.34) (11(9,2), 30, 0.2E-6, 3.1) (11(9,2), 25, 0.1E-5, 0.55) (18(13,5), 46, 0.1E-6, 9.84) (28(18,10), 82, 0.1E-5, 2.2) (27(17,10), 83, 0.1E-6, 25.8) (5(5,0), 6, 0.5E-6, 0.07) (5(5,0), 6, 0.3E-6, 0.49) (1(1,0), 2, 0.0,0.01) (1(1,0), 2, 0.0, 0.04) (6(6,0), 7, 0.1E-11,0.05) (6(6,0), 7,0.1E-11, 0.36) (12(10,2), 31, 0.0, 0.24) (11(9,2), 32, 0.9E-5, 2.52) (29(7,22), 489, 0.3, 4.3) (34(10,14), 507, 0.3, 47.5) (22(16,6), 61, 0.2E-6, 4.2) (25(19,6), 55, 0.2E-6, 135.7) (4(4,0), 5, 0.2E-7, 0.04) (4(4,0), 5, 0.1E-6, 0.25) (100(8,92), 108, 0.5E-1, 59.4) overflow

Table 6.1

Newton's Method: First set of problems

131

132

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Dimension

Broyden Local Version

Broyden Global Version

n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000

(7, 0.5E-6, 0.06) (100, 0.8E+6, 14.1) (100, 0.2E+7, 1.61) (100, 0.7E+6, 14.5) (100, 0.2E+3, 1.66) (100, 0.4E+3, 14.68) (67, 0.2E+26, 0.84) (14, 0.1E+14, 0.82) (5, 0.2E+35, 0.06) (100, 0.5E+22, 0.26) (100, 0.2E+1, 1.49) (100, 0.1E+1, 13.4) (100, 0.1E+11, 1.53) (100, 0.9E+11, 13.8) (100, 0.7E-2, 1.64) (92, 0.8E-5, 12.44) (100, 0.6, 1.64) (100, 0.2E-1, 14.8) (17, 0.5E-5, 0.13) (20, 0.3E-5, 1.23) (1,0.0, 0.01) (1,0.0, 0.04) (12, 0.1E-7, 0.07) (12, 0.5E-6, 0.55) (13, 0.5E+3, 0.08) (100, 0.5E+3, 12.3) (100, 0.4E+1, 1.54) (100, 0.1E+1, 13.5) (100, 0.5E+11, 1.85) (100, 0.1E+12, 17.0) (15, 0.2E-5, 0.10) (32, 0.7E-5, 2.07) (100, 0.4E+17, 1.57) overflow

(7(1,0), 8, 0.5E-6, 0.06) (10(2,3), 12, 0.3E-6, 0.98) (10(1,1), 12, 0.3E-15, 0.1) (10(1,1), 12, 0.2E-17, 0.9) (41(6,34), 702, 0.1, 9.15) (100(4,95), 1605, 0.2, 2170.3) (20(7,6), 47, 0.1E-8, 0.56) (17(4,3), 34, 0.8E-7, 3.67) (37(14,10), 147, 0.6E-5, 7.3) (85(27,50), 420, 0.8E-5, 868.) (67(9,56), 1179,0.6,21.5) (13(3,8), 190, 0.1E+1, 20.3) (29(9,8), 62, 0.1E-5, 0.7) (42(13,12), 112, 0.7E-5, 17.9) (30(10,9), 77, 0.2E-6, 1.35) (33(9,8), 73, 0.6E-12, 12.15) (59(18,26), 210, 0.2E-7, 5.37) (61(19,28), 222, 0.9E-5, 50.3) (17(1,0), 18, 0.5E-5, 0.13) (20(1,0), 21, 0.3E-5, 1.22) (1(1,0), 2, 0.0,0.01) (1(1,0), 2, 0.0,0.04) (12(1,0), 13, 0.1E-7, 0.07) (12(1,0), 13, 0.5E-6, 0.54) (13(4,3), 31,0.0, 0.25) (13(4,3), 32, 0.9E-5, 2.45) (30(6,22), 490, 0.3, 4.31) (34(8,24), 507, 0.3, 47.2) (29(7,6), 50, 0.3E-7, 2.03) (33(11,10), 70, 0.1E-5, 169.7) (15(1,0), 16, 0.2E-5, 0.09) (15(2,1), 22, 0.2E-6, 22.5) (100(7,92), 108, 0.5E-1, 59.3) overflow

Table 6.2 - Broyden's Method: First set of problems.

Nonsmooth Equations by Means of Quasi-Newton with Globalization Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Dimension

Column-Updating Local Version

Column-Updating Global Version

n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000 n=100 n=1000

(9, 0.2E-5, 0.07) (13, 0.1E-5, 0.57) (100, 0.9E+6, 1.18) (100, 0.7E+7, 9.14) (100, 0.6E+1, 1.08) (100, 0.5E+3, 9.14) (54, 0.4E+18, 0.47) (54, 0.1E+18, 3.79) (3, 0.2E+27, 0.03) (3, 0.6E+26, 0.18) (100, 0.1E+1, 1.6) (100, 0.1E+1, 14.4) (100, 0.5E+20, 1.00) (100, 0.8E+20, 8.41) (100, 0.2E+4, 1.05) (100, 0.2E+4, 8.77) (100, 1.36, 1.11) (100, 0.1E+1, 9.59) (13, 0.3E-5, 0.09) (13, 0.3E-5, 0.58) (1, 0.0, 0.01) (1, 0.0,0.05) (12, 0.5E-6, 0.05) (12, 0.5E-6, 0.45) (100, 0.9E+3, 0.8) (100, 0.9E+3, 6.4) (100, 0.1E+4, 0.99) (100, 0.8E+3, 7.96) (100, 0.2E+11, 1.25) (100, 0.4E+12, 11.7) (63, 0.2E-5, 0.51) (34, 0.5E-5, 1.55) (100, 0.3E+16, 0.96) (overflow )

(9(1,0), 10, 0.2E-5, 0.06) (5(2,1), 7, 0.1E-5, 0.97) (11(2,1), 13, 0.3E-7, 1.23) (11(2,1), 13, 0.8E-5, 6.84) (41(6,34), 702, 0.1, 9.3) (100(5,95), 1605, 0.2, 2169.3) (20(7,6), 47, 0.1E-6, 0.54) (29(3,3), 44, 0.9E-6, 4.15) (35(14,13), 145, 0.9E-5, 7.31) (99(36,46), 422, 0.8E-5, 971.9) (67(9,56), 1179,0.6,21.1) (13(3,8), 190, 0.1E+1, 20.3) (30(9,8), 63, 0.1E-5, 0.7) (37(14,13), 110, 0.1E-5, 18.2) (27(10,9), 74, 0.2E-11, 1.33) (29(6,5), 54 , 0.7E-7, 7.49) (53(16,25), 194, 0.2E-11, 4.71) (54(16,24), 192, 0.7E-11, 43.4) (13(1,0), 14, 0.3E-5, 0.1) (13(1,0), 14, 0.3E-5, 0.6) (1(1,0), 2, 0.0, 0.01) (1(1,0), 2, 0.0,0.04) (12(1,0), 13, 0.5E-6, 0.08) (12(1,0), 13, 0.5E-6, 0.45) (13(3,2), 27, 0.6E-5, 0.21) (14(3,2), 30, 0.0,2.16) (30(6,22), 490, 0.3, 4.34) (34(8,24), 507, 0.3, 47.2) (23(7,6), 47, 0.5E-6, 1.99) (34(11,10), 71, 0.1E-5, 170.4) (20(6,6), 58, 0.3E-7, 2.41) (18(2,1), 20, 0.3E-6, 0.93) (100(7,92), 108, 0.5E-1, 59.4) (overflow)

Table 6.3 - Column-Updating Method: First set of problems

133

134

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

We proceed to the analysis of the numerical results. In the local version of New­ ton's method, 14 cases converged out of the 34 tests performed. For these 14 successful cases, the global version of Newton's method reproduced exactly the same iterations as the local version in 11 tests. In 2 other cases, the global version reached conver­ gence in a smaller number of iterations than the local one, but with an increase in the amount of total time spent in the execution. In only one case, the performance of the global version was worse than the one presented by the local version: the problem 4, n = 1000, spends more iterations to achieve the same solution of (1). In the 20 tests in which the local version of Newton's method failed to converge, the global version effectively worked in 11 tests, reaching the solution of system (1). In other 6 cases the sequence generated by the global version converged to a stationary point of (6). In the remaining 3 tests, interruption by overflow occurred, or the maximum number of iterations was achieved. Comparing the quasi-Newton methods, their performance were practically iden­ tical, with a slight advantage for the Column-Updating method in terms of running time, since in that method the number of operations is smaller than the one per­ formed by Broyden's algorithm. This fact becomes more perceptible as the dimension increases. In the local version of the quasi-Newton methods, 48 cases failed out of the 68 tests performed. For these 48 cases, the global version reached convergence to a solution of (1) in 32 tests. Other 10 cases converged to stationary points of (6) and, finally, there was failure in the remaining 6 tests. As regards the 20 tests in which the local version of the quasi-Newton methods converged, the global version reproduced the sequence of local iterations in 15 cases. In the 5 cases left, analogously to the behavior of the global Newton's method, a solution for the system (1) was obtained in fewer iterations but spending more time than in the local version. Comparing Newton and quasi-Newton methods, we observe that they behave al­ most in the same way. In figures, the local version of the Newton's method performed successfully in practically 40 % of the tests (14 out of 34). The local quasi-Newton method converged in 30 % of the tests (20 out of 68). Therefore, the globalization role is as much effective for the quasi-Newton methods as it is for Newton's algorithm. Such a behavior is quite different from the numerical results of [12], where the differentiable Luksan's problems [22] were used. When it comes to Newton's method, 15 out of 34 local tests and 24 out of 34 global ones had the same performance in terms of convergence or divergence, both in the differentiable and in the nondifferentiable problems. On the other hand, for the quasi-Newton methods, 53 out of 68 local tests and 47 out of 68 global ones performed analogously in both cases. Both Broyden's method and the Column-Updating method behave in the same way. Through these figures, we can see that Newton's method is not as robust for nondifferentiable prob­ lems as it is for differentiable ones. In fact, in the present experiments, although the local version of Newton's method reaches slightly better results than the local quasi-Newton, the globalization is quite more effective for the quasi-Newton methods than for Newton's method.

Nonsmooth

Equations by Means of Quasi-Newton with Globalization

135

We performed a second set of experiments, where
K

'

l 9i(x) - 9i(x.) + 1,

i odd or i > n / 2 ; i otherwise.

In this case, the function F is not differentiate at x,, since fe,(x.) = [x„]; = 0 if i is even and i > n/2. In Tables (6.4), (6.5) and (6.6) we report the performance of Newton's method, Broyden's method and the Column-Updating method, for n = 100.

Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Newton Local Version

Newton Global Version

(4, 0.1E-15, 0.05) (100, 0.2E-1, 1.19) (100, 0.2E+1, 1.13) (15, 0.9E-6, 0.16) (86, 0.3E-6, 0.99) (100, 0.6E+4, 0.83) (100, 0.1E+8, 0.85) (100, 0.2E+9, 1.09) (100, 0.2E+9, 1.68) (5, 0.3E-6, 0.07) (1, 0.0, 0.01) (100, 0.3E+10, 0.81) (100, 0.2E-3, 0.62) (100, 0.2E+1, 0.85) (100, 0.5E+7, 2.6) (4, 0.1E-6, 0.03) (100, 0.9E+16, 0.86)

(4(4,0), 5, 0.1E-15, 0.05) (32(13,19), 336, 0.1E-1, 5.83) (41(9,32), 657, 0.7E-1, 7.19) (11(8,3), 28, 0.0, 0.33) (100(43,57), 485, 0.3E-4, 53.1) (100(10,90), 2058, 0.2E+1, 26.0) (14(11,3), 30, 0.3E-10, 0.37) (11(9,2), 25, 0.5E-5, 0.68) (100(35,65), 698, 0.3, 27.9) (5(5,0), 6, 0.3E-6, 0.05) (1(1,0), 2, 0.0,0.01) (6(5,1), 14, 0.1E-5, 0.18) (12(10,2), 31,0.0, 0.3) (69(14,55), 1226, 0.2,37.9) (26(20,6), 60, 0.2E-6, 3.04) (4(4,0), 5, 0.1E-6, 0.04) (100(10,90), 110, 0.2E+6, 53.7)

Table 6.4 - Newton's Method: Second set of problems

136

M. A. Gomes-Ruggiero, Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

J. M. Martinez

and S. A.

Broyden Local Version

Broyden Global Version

(100, 0.1E+7, 1.57) (100, 0.1E+7, 1.57) (100, 0.1E+3, 1.61) (31, 0.34+20, 0.28) (5, 0.2E+31, 1.04) (100, 0.3E+1, 1.54) (100, 0.2E+11, 1.47) (100, 0.2, 1.56) (100, 0.4E+0, 1.64) (20, 0.6E-5, 0.16) (1, 0.0,0.01) (100, 0.6E-3, 1.55) (100, 0.3E+3, 1.5) (100, 0.3E+1, 1.62) (100, 0.3E+11, 1.90) (100, 0.3E-1, 1.56) (100, 0.5E+17, 1.57)

(11(2,1), 13, 0.6E-5, 0.18) (50(9,29), 483, 0.1E-1, 7.17) (44(8,35), 682, 0.7E-1, 7.21) (14(6,5), 39, 0.2E-5, 0.5) (36(15,16), 143, 0.9E-5, 7.41) (100(9,88), 2032, 0.2E+1, 24.5) (31(11,10), 77, 0.6E-5, 1.32) (30(10,9), 77, 0.2E-6, 1.31) (33(7,16), 325, 0.2, 6.31) (10(2,1), 12, 0.3E-5, 0.12) (1(1,0), 2, 0.0,0.01) (10(2,1), 12, 0.3E-6, 0.09) (13(4,3), 30, 0.4E-8, 0.3) (70(10,55), 1227, 0.2, 38.3) (30(10,9), 65, 0.4E-7, 4.38) (17(2,1), 19, 0.3E-6, 1.15) (100(10,90), 110, 0.2E+6, 52.9)

Table 6.5 - Broyden's M e t h o d : Second set of p r o b l e m s Problem 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Column-Updating Local Version

Column-Updating Global Version

(100, 0.4E+7, 1.05) (100, 0.9E+7, 1.11) (100, 0.4E+3, 1.15) (87, 0.5E+23, 1.86) (3, 0.2E+27, 1.02) (100, 0.2E+2, 1.05) (100, 0.5E+12, 1.00) (100, 0.2E+1, 1.02) (100,2.4 1.21) (14, 0.7E-5, 0.07) (1,0.0, 0.01) (100, 0.8E+1, 0.89) (100, 0.9E+3, 0.8) (100, 0.7E+3, 1.19) (100, 0.8E+11, 1.54) (100, 0.2E+0, 1.03) (100, 0.2E+17, 0.94)

(11(2,1), 13, 0.3E-5, 0.17) (45(7,25), 458, 0.1E-1, 6.96) (44(8,35), 682, 0.7E-1, 7.16) (14(6,5), 39, 0.2E-5, 0.5) (40(14,15), 146, 0.9E-5, 6.97) (100(9,87), 2006, 0.2E+1, 24.6) (32(11,10), 78, 0.8E-6, 1.28) (26(9,8), 68, 0.4E-6, 1.25) (60(20,28), 219, 0.2E-5, 5.92) (14(1,0), 15, 0.7E-5, 0.1) (1(1,0), 2, 0.0,0.01) (14(2,1), 23, 0.2E-5, 0.19) (16(3,2), 30, 0.6E-6, 0.23) (40(5,26), 483, 0.3, 9.79) (23(6,5), 41, 0.7E-7, 1.4) (14(2,1), 16, 0.8E-7, 0.64) (100(10,90), 110, 0.2E+6, 54.4)

Table 6.6 - C o l u m n - U p d a t i n g M e t h o d : Second set of p r o b l e m s

Santos

Nonsmooth Equations by Means of Quasi-Newton with Globalization

137

In more than 50 % of these experiments the solution obtained was different from the nondifFerentiable point a;,. A summary of these cases is given in Table (6.7). We also observe, in this set of experiments, that the pure local versions of the methods are far less efficient than the global versions.

Execution

Method

Local Version

Newton Broyden Column-Updating Newton Broyden Column-Updating

Global Version

Convergence to a solution x ^ x, 4 2 2 4 6 6

Convergence to I , 2 0 0 6 5 6

Convergence to a stationary point

3 4 3

Table 6.7 - Summary of the performance of the methods when function is not nondifFerentiable at the solution x, Following a suggestion of a referee, we observed the rate ||a;(t+i — I«||/||a;ifc ~ x*\\ a t the final iterations of the three methods tested. A typical result is shown in Table 6.8. Here, the execution reported is global, but the final four iterations are purely local. In this case, the practical behavior of the rate seems to reflect theoretical superlinearity. This property, which has been proved in [36] for Newton's method, probably holds for quasi-Newton methods in many particular situations. In fact, local convergence properties of quasi-Newton methods for nonsmooth systems represents one of the more challenging problems in this research area. Newton 0.7972983E-01 0.1338583E+00 0.1487052E-01 0.2918130E-03

Broyden 0.7176153E-01 0.8193998E-01 0.5369848E-02 0.2844602E-01

Column-Updating 0.7176153E-01 0.6818981E-01 0.4678174E-02 0.2814408E-01

Table 6.8 - Convergence rate ||z*:+i - i . | | / | | i i - x,\\ for the last four iterations of the Global Versions of the Newton, Broyden and Column-Updating Methods for the Problem 4

References [1] C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Mathematics of Computation 19 (1965) 577-593.

138

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

[2] C. G. Broyden, J. E. Dennis, and J. J. More, On the local and superlinear convergence of quasi-Newton methods, Journal of the Institute of Mathematics and Applications 12 (1973) 223-246. [3] X. Chen, On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms, Annals of the Institute of Statistical Mathematics 42 (1990) 387-401. [4] X. Chen and L. Qi, A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Computational Optimization and Applica­ tions 3 (1994) 157-179. [5] X. Chen and T. Yamamoto, On the convergence of some quasi-Newton methods for nonlinear equations with nondifferentiable operators, Computing 48 (1992) 87-94. [6] J. E. Dennis and J. J. More, Quasi-Newton methods, motivation and theory, SIAM Review 19 (1977) 46-89. [7] J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Opti­ mization and Nonlinear Equations, (Prentice-Hall, Englewood Cliffs, New Jer­ sey, 1983). [8] J. E. Dennis and H. F. Walker, Convergence theorems for least-change secant update methods SIAM Journal on Numerical Analysis 18 (1981) 949-987. [9] M. A. Diniz-Ehrhardt and J. M. Martinez, A parallel projection method for overdetermined nonlinear systems of equations, Numerical Algorithms 4 (1993) 241-262. [10] S. C. Eisenstat and H. F. Walker, Globally convergent inexact Newton meth­ ods, Research Report, Department of Mathematics and Statistics, Utah State University, USA. [11] R. Fletcher, Practical Methods of Optimization (2nd edition), (John Wiley and Sons, New York, 1987). [12] A. Friedlander, M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos, A new globalization strategy for the resolution of nonlinear systems of equations, Relatoriode Pesquisa, RP04/94, Institute of Mathematics, University of Camp­ inas, Brazil, 1994. [13] A. Friedlander and J. M. Martinez, On the maximization of a concave quadratic function with box constraints. To appear in: SIAM Journal on Optimization.

Nonsmooth Equations by Means of Quasi-Newton with Globalization

139

[14] A. Friedlander, J. M. Martinez and S. A. Santos, A new trust region algo­ rithm for bound constrained minimization. To appear in: Journal of Applied Mathematics & Optimization. [15] A. George and E. Ng, Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM Journal on Scientific and Statistical Computing 8, (1987) 877-898. [16] G. H. Golub and Ch. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore and London, 1989. [17] M. A. Gomes-Ruggiero and J. M. Martinez, The Column-Updating Method for solving nonlinear equations in Hilbert space, RAIRO Mathematical Modelling and Numerical Analysis 26 (1992) 309-330. [18] M. A. Gomes-Ruggiero, J. M. Martinez and A. C. Moretti, Comparing al­ gorithms for solving sparse nonlinear systems of equations, SIAM Journal on Scientific and Statistical Computing 13 (1992) 459-483. [19] L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM Journal on Numerical Analysis 23 (1986) 707 716. [20] S. P. Han, J. S. Pang and N. Rangaraj, Globally convergent Newton methods for nonsmooth equations, Mathematics of Operations Research 17 (1992) 586-607. [21] C. M. Ip and J. Kyparisis, Local convergence of quasi-Newton methods for B-differentiable equations, Mathematical Programming 56 (1992) 71-90. [22] L. Luksan, Inexact trust region method for large sparse systems of nonlinear equations, Technical Report no.547, January 1993, Institute of Computer Sci­ ences, Academics of Sciences of the Czech Republic. [23] J. M. Martinez, A quasi-Newton method with modification of one column per iteration, Computing 33 (1984) 353-362. [24] J. M. Martinez, On the Convergence of the Column-Updating Method, Matematica Aplicada e Computacional 12 (1993) 83-95. [25] J. M. Martinez, Local convergence theory for inexact Newton methods based on structural least-change updates, Mathematics of Computation 55 (1990) 143168. [26] J. M. Martinez, On the relation between two local convergence theories of least change secant update methods, Mathematics of Computation 59 (1992) 457481.

140

M. A. Gomes-Ruggiero, J. M. Martinez and S. A. Santos

[27] J. M. Martinez, A theory of secant preconditioners, Mathematics of Computa­ tion 60 (1993) 681-698. [28] J. M. Martinez and L. Qi, Inexact Newton methods for solving nonsmooth equations, Relatorio de Pesquisa 67/93, Institute of Mathematics, University of Campinas, Brazil, 1993, to appear in: Journal of Computational and Applied Mathematics. [29] J. M. Martinez and M. C. Zambaldi, Least Change Update Methods for non­ linear systems with nondifferentiable terms, Numerical Functional Analysis and Optimization 14 (1993) 405-415. [30] H. Matthies and G. Strang, The solution of nonlinear finite element equations, International Journal of Numerical Methods in Engineering 14 (1979) 1613 1626. [31] R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization 15 (1977) 957-972. [32] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). [33] J. S. Pang, Newton's method for B-differentiable equations, Mathematics of Operations Research 15 (1990) 311-341. [34] J. S. Pang, A B-differentiable equation based, globally, and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Mathematical Programming 51 (1991) 101-131. [35] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equa­ tions, Mathematics of Operations Research 18 (1993) 227-244. [36] L. Qi and J. Sun, A nonsmooth version of Newton's method, Programming 58 (1993) 353-368.

Mathematical

Approximate

Newton

Methods

141

Recent Advances in Nonsmooth Optimization, pp. 141-158 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

Superlinear Convergence of Approximate Newton Methods for LC1 Optimization Problems without Strict Complementarity 1 Jiye Han a n d Defeng Sun Institute of Applied Mathematics,

Acadernia

Sinica Beijing

100080, P. R.

China

Abstract

In this paper, the Q-superlinear convergence property of the approximate New­ ton or SQP methods for solving LC 1 optimization problems is established under the assumptions that the derivatives of the objective and constraint functions are semismooth, the strong second-order sufficiency condition is satisfied and the gradients to the active constraints are linearly independent. The strong second-order sufficiency condition is weaker than the second-order sufficiency condition and the strict complementarity condition.

1

Introduction Consider the s t a n d a r d nonlinear p r o g r a m m i n g minimize subject to

}(x) g(x) < 0, h(x) = 0,

(1-1)

where / , g and h are differentiable functions from Rn into R, Rp and Rq respectively. One m e t h o d for solving (1.1) is to solve t h e following linearly constrained q u a d r a t i c p r o g r a m Qk minimize

V}(xk)T(x

subject to

g(xk) h\xk)

- xk) + hx

+ Vg(xk)T{x + Vh{xk)T(x

- xk)TGk{x

-

xk)

- xk) < 0, - xk) = 0

'This work is supported by the National Natural Science Foundation of China

(L2)

142

J. Han and D. Sun

successively. Here Gk is an n x n matrix. This method is called an approximate Newton method or a SQP (sequential quadratic programming) method. If Gk is exactly the second-order derivative of the Lagrangian at xk, this is Wilson's method. See Garcia Palomares and Mangasarian (Ref. 4) and Robinson (Refs. 21-22). Before the advent of the very recent paper by Qi (Ref. 19), the proof of the superlinear convergence of such approximate Newton or SQP methods for solving nonlinear programming problems requires twice smoothness of the objective and constrained functions. Sometimes, the second-order derivatives of those functions are required to be Lipschitzian, for example, see Garcia Palomares and Mangasarian (Ref. 4), Han (Ref. 5), McCormick (Ref. 9) and Robinson (Refs. 21-22). However, the secondorder differentiability may not hold for some problems. For example, the extended linear-quadratic programming problem, recently emerged in stochastic programming and optimal control, even in the fully quadratic case, does not possess twice differentiable objective functions. However, their objective functions are differentiable and their derivatives are Lipschitzian in that case. See Rockafellar (Ref. 24) or Rockafellar and Wets (Ref. 25) for a detail. We call a function F : R" -> BT a LC1 function, if it is differentiable and its derivative function is locally Lipschitzian. We call a nonlinear programming problem a LC 1 optimization problem if its objective and constrained functions are LC1 functions. For the detail of LC 1 functions and LC 1 optimization problems, see Qi (Ref. 17). In Qi (Ref. 19), the Q-superlinear con­ vergence of the approximate Newton or SQP methods for solving LC 1 optimization problems was established under the assumption that the derivatives of the objective and constrained functions are semismooth and the three key assumptions that the second-order sufficiency condition, the strict complementarity slackness and linear in­ dependence of the gradients to the active constraints are satisfied under the context of LC 1 optimization problems. Basing on generalized equations' theory established by Robinson (Ref. 23), Josephy (Refs. 7-8) provided a proof to the local superlinear (quadratic) convergence of quasi-Newton (Newton) methods without assuming the strict complementarity slackness condition when the second-order differentiability is available. Also basing on Robinson's generalized equations' theory (Ref. 23), without assuming the strict complementarity condition Lescrenier (Ref. 29) provided a proof to the convergence of a class of trust region methods proposed by Conn, Gould, and Toint (Ref. 30) for optimization problem with simple bounds constraints when the objective function is twice continuously differentiable. In this paper, we will discuss the superlinear convergence of approximate Newton or SQP methods for solving LC1 optimization problems without assuming the existence of the second-order differen­ tiability and the strict complementarity slackness condition. In a certain sense, our results in this paper are the LC 1 version of the results in Josephy (Refs. 7-8) or a generalization of the results in Qi (Ref. 19) without the strict complementarity slackness. To achieve this, our technique is different from that of Josephy (Refs. 7-8) or Qi (Ref. 19). First we consider the superlinear

Approximate Newton

Methods

143

convergence of a generalized approximate Newton type method for solving nonsmooth equations, recently developed in Pang (Ref. 14) and Qi (Refs. 16-17). Then, we prove that the approximate Newton or SQP methods are special cases of such generalized approximate Newton method. In section 2, we discuss the strong second-order sufficiency condition and linear independence under the context of LC 1 optimization. The Q-superlinear convergence of approximate Newton or SQP methods for LC1 optimization is established in section 3. In section 4, we give some discussions.

2

The Strong Second-Order Sufficiency Condition Throughout this paper, we assume that / , g and h in (1.1) are LC 1 functions.

The Lagrangian of (1.1) is L(x,u,v) = f(x) + uTg(x) + vTh(x). gradient of L with respect to x by FUfV. Then Fu,v(x) = v / ( * ) + V f f (i)u +

Denote the

Vh(x)v

is a locally Lipschitzian function. In Josephy (Refs. 7-8) or Robinson (Ref. 23), the two key assumptions other than second-order differentiability are the strong second-order sufficiency condition and linear independence of the gradients to the active constraints. We still need these two assumptions. However the strong second-order sufficiency condition needs to be modified because we will not assume the second-order differentiability of / , g and h. In general, assume that F : Rn —> Rm is locally Lipschitzian. By Rademacher's Theorem, F is differentiable almost everywhere. Let Dp be the set where F is dif­ ferentiate. Let dF be the generalized Jacobian of F in the sense of Clarke (Ref. 2). Then dF{x) = co{ lim F'(xk)\, (2.1) where co{A} is a convex hull of a set A. In Qi (Ref. 16) and Pang and Qi (Ref. 15), the concept dsF(x) dBF(x)

= { lim

F'(xk)\.

Then dF(x) =

codBF(x).

was introduced

J. Han and D. Sun

144

For m = 1, 8BF(X) was introduced by Shor (Ref. 26). Let F, denote the ith compo­ nent of F. Sun and Han (Ref. 27) introduced dbF(x) = dgF^x)

x dBF2(x) x ■ ■ ■ x

dBFm(x).

Then 8BF(X) C di,F(x) and the converse relation does not hold in general. For example if F : R1 —> R2 has the form v

'

/ min(*,*') y min(-x, -x')

\ I

then

w>-{(i).(. , 1 ) }•»«•)-{(;). (-.)•(-.)■(:)}■ and dBF(0) C dt,F(0). But when m = 1, 3 t F(a:) =

dBF{x).

From the results of Clarke (Ref. 2), Qi (Ref. 16), and Sun and Han (Ref. 27) we know that dF(x), dBF(x) and di,F(x) are nonempty compact subsets of Rmxn, and the maps dp, dBF and d^F are upper semi-continuous (Ref. 1). In fact if we note that dF{x) and diF(x) are compact subsets, and that the maps dF and d{F are upper semi-continuous (Ref. 2), we can draw the same conclusions for the maps dsF and d\,F through the standard analysis. In this paper we use M{x,F) to represent one of dF(x), dBF(x) and dt,F(x) and use the multifunction M(-, F) to represent one of dF, dBF and dtF. Therefore, M(x,F) is a nonempty compact subset of Rmxn, and the map M{-,F) is upper semi-continuous. Suppose that f\, / 2 : Rn —+ i?1 are continuously differentiable functions. Let fo(x) = m i n ( / i ( x ) , / 2 ( i ) ) , then 9*/o(i) =

{V/,(*) T } {V/r(x)r,V/2(zn {V/ 2 (x) T }

if fi(x) < / 2 ( x if / i t 1 ) = /2(x i f / i ( z ) > f2(x

This formulae will be used later in this paper. The first-order Kuhn-Tucker conditions for (1.1) are F»,v{x) = Vf{x) + Vg{x)u + Vh(x)v = 0, « > 0, g(i) < 0, u;5,(z) = 0, for i = l,...,p, ft(x) = 0.

(2.2)

Let H(z)=

/ V / ( i ) + Vg(x)u + Vh(x)v min{u,-g{x))

V

~h(x)

\ ,

)

(2.3)

Approximate

Newton

Methods

145

where the 'min' operator denotes the componentwise minimum. Then the first-order Kuhn-Tucker conditions are equivalent to H(z) = 0. Denote Ht{z) = V / ( x ) + Vg(x)u + Vh(x)v, H2(z) = min(u, -g(x)) and H3{z) = -h(x). Then

H(z) =

/ Hx(z) \ H2{z) .

\ H3(z) J For every z = (x, u, v) G R" x R? x R?, denote dQH(z) = M{z,Hx)

x dbH2(z) x

{VH3(zf}.

It is easy to see that 3QH(Z) is a nonempty compact subset of Rmxm, and the map 3QH is upper semi-continuous, where m = n + p + q. For any A G M(z, Hx), there exists V 6 R"xn such that A = {V V(?(i) Vh(x)). Denote

vx(z) = {ve Rnxn\ (v vg(x) Vh(x)) e

M^,^)}.

From the definition of the map M(-,-), it is easy to see that for any z = (x,u,v) G R" x R? x Rq, we have M(x,Fu,v)CVx(z). Suppose that z = (x,u,v)

£ R" x Rp x Rq is a Kuhn-Tucker point of (1.1). Let

I(z) = {»| 1 < t < p, 0}, I°(z) = {," 6 J(*)| ut- = 0}, G(z) = {<* G / T | /'(x; d) = 0, gKx; d) = 0 for i £ /+(«), 0 for all d £ G(z)\0 (d G G+(z)\0), V 6 Vx(z). Suppose that z = (x,u,v) G R" x Rv x Rq is a Kuhn-Tucker point of (1.1). We say that z satisfies the linear independence condition if {Vj;(x), i G I(z)} and {Vhi(x), i = 1,...,<J} are linearly independent. We say that z satisfies the strict complementarity slackness condition if I°(z) = 0. When the strict complementar­ ity condition is satisfied (i.e., I°(z) = 0), then G(z) = G+(z). Therefore, secondorder sufficiency conditions and the strict complementarity slackness condition mean

J. Han and D. Sun

146

strong second-order sufficiency conditions. In general, strong second-order sufficiency conditions mean the second-order sufficiency conditions, but don't mean the strict complementarity slackness condition. The strict complementarity slackness condi­ tion may not hold in nonlinear optimization problems. Therefore, we will consider the superlinear convergence properties of approximate Newton or SQP methods for LC1 optimization problems without assuming the strict complementarity condition. First, we shall consider the nonsingularity of matrices W € 8QH(Z) at a solution of H(z) = 0. If the components of such a solution are denoted by xo, uo, «o, we can partition the vector g(xo) into smaller vectors g+(x0), g°(xo) and g~(xo), of dimensions r, s and t, respectively, and partition u0 conformably into itg , u° and u^ so that

ut >0,

g+(x0) = 0, g°(x0) = 0, g-{x0) < 0,

(2.4)

u° = 0, un = 0,

where the ordering is componentwise. After suitable arrangement, (2.3) can be writ­ ten as / x \ I V / ( i ) + Vg{x)u + Vh(x)v u+ min(u + , — g+(x)) H u° = min(u°, -g°{x)) u~ min(u~, — g~(x)) K

v j

-h(x)

\

\ .

(2.5)

j

Theorem 2.1. Suppose that z0 = (x0,u0,v0) 6 Rn x Rv x Rq satisfies the strong second-order sufficiency conditions and the linear independence condition of (1.1). Then all W G 8QH(Z0) are nonsingular. Proof. According to the definition of dQH(z0), we only need to prove for i = 0,1,..., s, the nonsingularity of the following matrices

( WW =

v

Gf

G°' T

G°jT

Gf

-Gt

0 0 0 0 0

0 0 0 0 0

0 0

0 0 0

-GV 0 0

I -Ho

'jxj

0 0

'txt

0

#oT\ 0 0 0 0 0 /

where V € VXo(z0), H0 denotes Vh(x0)T1 G£ denotes Vg+(x0)T, etc, / = {1,...,«'} (when i = 0, J = 0), J = {\,...,s}\I, j = | J | , G° 7 is a matrix of the / rows of G°, J G°0J is a matrix of the J rows of Gj, and LXj and Itxt are the unit matrices of if*

Approximate and Rtxt

Newton

Methods

147

respectively. Suppose that a, b, c, d, e and / are such that Va + G+Tb + G°0'Tc + G°0jTd + Gft -Gja -Gl'a Iixid

+ H0Tl = = = =

-ffxte

0, 0, 0, 0,

(2.6)

= 0,

-//0a

= 0.

Therefore, we get Va + G+Tb + G°'Tc + H0Tl -G+a -Gl'a -H0a

= = = =

0, 0, 0, 0.

(2.7)

Premultiplying the equations in (2.7) by aT, bT, cT and lT, respectively, and adding the result we find that aTVa = 0. This, together with the second and fourth equations of (2.7) and the strong second-order sufficiency conditions, implies that a = 0; the first equation of (2.7) and the linear independence assumption now imply that 6, c and / are also zero. The fourth and fifth equations of (2.6) means that d and e are zero. Thus the matrix Wt^ is nonsingular. This completes the proof. □ Corollary 2 . 1 . Under the conditions of Theorem 2.1, there exist 8 > 0 and C > 0 such that for any z = (x, u, v) G R" x W x Rq, satisfying p — z0\\ < 6, and any W € dQH(z), W is invertible and WW^W < C. Proof. Applying Theorem 2.1 of this paper, and that 3QH{Z) is a nonempty compact subset and the map 8QH is upper semi-continuous, we can easily obtain the conclusion. □ We say that a locally Lipschitzian function F : R" —* Rm is semismooth at x if lim

{Vh'}

(2.8)

V£0F(i+th')

exists for any h 6 Rn. If F is semismooth at x, then F is directionally differentiable at x and F'(x; h) is equal to the limit in (2.8). Semismoothness was first introduced by Mifflin (Ref. 10) for functional. Convex functions, continuously piecewise linear functions, smooth functions and subsmooth functions are examples of semismooth functions. Scalar products and sums of semismooth functions are also semismooth functions. In Qi (Ref. 16) and Qi and Sun (Ref. 18), the definition of semismoothness was extended to F : R" —» R™■ It was proved in Qi (Ref. 17) that F is semismooth at x if and only if each of its components is semismooth at x.

J. Han and D. Sun

148

3

Superlinear Convergence P r o p e r t y

To establish the superlinear convergence of approximate Newton or SQP methods, we need the following two properties of semismoothness: Suppose that F : Rn —+ i f is locally Lipschitzian and semismooth at x. Then (1) F is B-differentiable at x, i.e., F'(x; h) exists for all h G if1 , and F(x + h) = F(x) + F'(x; h) + o(||A||), (2) For any V G dF(x +

(3.1)

h),h-^0 Vh-F'(x;h)

= o(\\h\\).

(3.2)

See Theorem 2.3 of Qi and Sun (Ref. 18). The approximate Newton method (ANM) for solving (1.1) is as follows: Start at a point z° = (x°,u°,v°) G Rn x Rp x R". Having zk = (xk,uk,vk), k+1 k+1 k+l k+1 find a Kuhn-Tucker point z = (x ,u ,v ) of the quadratic subproblem Qk described by (1.2). If zk+l is not unique, choose any Kuhn-Tucker point zk+l which is closest to zk in terms of distance \\zk+1 — zk\\. Suppose that z' = (x",u",v') G Rn x R" x Rq is a solution of H(z) = 0 (i.e., z' is a Kuhn-Tucker point of (1.1)). For every z = (x,u,v) G i?" x Rv x Rq, denote a(z) = {i |u, > -gi(x)}, For ielfl

f3(z) = {i\ u, = -gi(x)}

and f(z) - {i\ «,• < - p ; ( x ) } .

= {1,...,2W*'>I}, define

ffW(*) =

/ V / ( x ) + V^(x)u + V/i(i)u \ , P <"( 2 )

-Hx)

V where p^\z)

(3.3)

j

G P(z) and P(z) consists of all the following functions p(z),

Pj(z)

< -
if j G a(z'), if j G P(z'), if j G j(z*),

j = 1, ...,p and define 9Qi7('»(Z) = M{z,Hx)

x {Vp(')( 2 ) T } x { V i / 3 ( ^ T } .

Lemma 3.1. Suppose that z" = (x*,u*,v") G Rn x R? x il« is a Kuhn-Tucker point of (1.1) and satisfies the conditions of Theorem 2.1. Then there exist positive

Approximate Newton

Methods

149

constants 6 and C such that for any z = (x,u,v) G 7?" x 7?" x 7?' with z G {z\ \\z—z*\\ < 6}, and any i G 7", all W{i) G dg77(z) are invertible and HW^H < C . Proof. From the definition of H^(z) and dQH^(z) we know that H®(z*) = 0

Vie/"

and dQH(i){z*)CdQH(z')

Vie/".

From Theorem 2.1 we know that all matrices W G dqH(z') are nonsingular. This means that all matrices Wj,-) 6 <9Q77('>(Z*), i G 7" are nonsingular. It is easy to see that all 3 Q / 7 ' ' ' ( Z ) , i G 7^ are nonempty compact subsets and all the maps 8QH^'\ i G I13 are upper semi-continuous. Therefore for each i G I13 there exist a neighborhood N^(z') of z' and a positive number C, such that for any z G -/V(''(z*), all W(,) G dqH^(z) are nonsingular and satisfy |[WT^11] < C,. Since I13 is of finite elements, the conclusion of this lemma holds. D In order to establish the superlinear convergence of approximate Newton method, we first consider the following generalized approximate Newton method (GANM) for solving H(z) = 0 : Given z° = (x°,u°,t>0) G Rn x R" x R«. For k = 0,1,..., choose i G 7" and let

^+i = 2<= _ B j ^ ' V ) , where B (i)fc = S/H^k(zkf k

H^ (z)

(3-4)

and TfW* is defined as

/ V/(x*) + V ^ a ^ u + V/i(xfc)u + G t (z - xk) \ = q"k(z) , k \ -h(x )-Vh(xk)T(x-xk) )

(3.5)

i G 7^, where q<-''lk(z) is defined as

?f *M =

( -9j(xk)

- V9l(xk)T(x

k

T

- xk)

if j G a(**),

pf{z ) + Vpj'V) (* ~ «*)

if J e £(**),

[ Uj

(3-6)

i f ; G l{z*),

j = l,...,?,andGfc€7?nxn Remark 3.1. In practice, we can't use the above method since we don't know z" However, the above method provides an approach to prove the Q-superlinear convergence of the approximate Newton method. T h e o r e m 3 . 1 . Suppose that z* = (x*,u*,v*) G 7?" x Rp x Rq is a Kuhn-Tucker point of (1.1) and satisfies the conditions of Theorem 2.1. Suppose that V / , Vg and

J. Han and D. Sun

150

V/i are semismooth at i*. Let C and 6 be the positive constants in Lemma 3.1. If there exists Vk 6 Vxk{zk) such that \\Gk-Vk\\<±

Vfc,

(3.7)

then the above method GANM is well defined and Q-linearly converges to z* in a neighborhood of z* If furthermore,

£2,

\](Gk-Vk)(xk"-xk)\\

\\zk»-z«\\

(3 8)

- °'

"

then the convergence is Q-superlinear. If in the later case H(zk) ^ 0, we have

lim"^f;;j"=0.

(3.9)

*-• ll#(**)ll Proof. Since V / , Vg and V/t are semismooth at x', H and H^'K i 6 I13 are semismooth at z". From the definitions of Vx*(zk) and dQH^(zk), i € /", for each £(,-)*, i e J" there exists W(,-)t £ dQH{i1(zk) such that for any z = ( i , t i , « ) e i f x i ? x /?« | | ( 5 ( 1 > - W{i)k)z\\ = \\(Vk - Gk)x\\.

(3.10)

\\B{i)k-W{i)k\\<\\Vk-Gk\\<±.

(3.11)

In particular, we have

If \\zk - z*|| < 6, then by Lemma 3.1, W{'\ exists and || W ^ J < C. By the Pertur­ bation Lemma of Ortega and Rheinboldt (Ref. 12, p. 45), B^)k is invertible and l|B(7)\ll < \C

(3.12)

Recall that a map is semismmooth at z* if and only if each of its components is semismooth at z* and there are finite elements in the set / , so by (3.1) and (3.2), for every e > 0 there exists a neighborhood N(z*) of z" such that when z G N(z') and W(i) 6 dQH^{z) (note Wfa e dHf\z)) we have n+P+9

\\H®{x) - H^(z')

- W{l)(z - OH <

£

l^ ( , , (*) -

tfjV)

- Wj)(» - z')\

J=l

<e||z-z*||

Vie/* 3 . (3.13)

Approximate

Newton Methods

151

So we may choose S\ > 0 sufficiently small such that when \\zk — z*\\ < Si, for any i 6 / " we have \\HM(zk) - H^(z')

- W{t)k(zk - z')\\ < ± | | * * - z*\\.

(3.14)

Let S = min(<5j, (5). Then when \\zk — z*|| < 6, we have H ^ i _ 2 .|| = ^k _ B^H^(z")

- z'\\

< H^IIII^°(«*) - # V ) - %*(** - **)ii < \\B^\\l\\HU(zk)

- H<<\z') - W(i)k(zk - z')\\

+\\{Bmk-W{i)k){zk-z')\\}.

(3.15)

Substituting (3.11)-(3.12) and (3.14) into (3.15) gives

^_z»n

< _ Cc( ( — ++ — jMI-* l12 3

iC

8C

:

= i||^-z*||.

(3.16)

This proves that GANM is well defined and Q-linearly converges to z* in a neighbor­ hood of z'. Furthermore if (3.8) holds, by (3.10)-(3.11), (3.13) and (3.15), we have \\zk+1 ~ 2*|| < \c[\\HV{zk)

-

tf
- W{i)k(zk - z')\\

+ 11(^(0* - W(.l*)(**+1 - **)ll + ll(B(,-,t - Wm){zk^ - z')\\] < \c[o{\\zk
- z'\\) + \\{Vk - Gk)(xk" +

- xk)\\ + ± | | z * + 1 - *'||]

o{\\zk»-zk\\)+l-\\zk»-z'\\. (3.17)

This, and the Q-linear convergence of {zk}, turns out to be \\zk+1 - z'\\ = o(\\zk - z*\\),

(3.18)

i.e., the convergence of GANM is Q-superlinear. The proof of (3.9) is similar to the proof of Theorem 3.1 of Qi (Ref. 16).

D

J. Han and D. Sun

152

Remark 3.2. For unconstrained optimization problem ( / G C 2 ), condition (3.8) is known as the Dennis-More type condition (see, e.g., Dennis and Schnabel (Ref. 3)) and that for nonlinear programming (C2 optimization problem) with equality constraints a generalization of this condition due to Boggs, Tolle, and Wang (Ref. 31) is widely used. Corollary 3.1. Assume that the conditions of Theorem 3.1 hold. Then there exists a positive number e > 0 such that when there exists Vk € Vxt{zk) such that ||Vl-Gfc||
V *,

(3.19)

the approximate Newton method described above is well defined and Q-linearly con­ verges to 2* in a neighborhood of z* - If furthermore (3.8) holds, then the convergence is Q-superlinear. If in the later case, H(zk) ^ 0, then (3.9) holds. Proof. To complete the proof, we prove that the approximate Newton method is a special case of GANM in a neighborhood of z* Choose a positive number 82 > 0 {82 < 6/3, 8 is defined in the proof of Theorem 3.1) such that when z, zheB(z'-382)

= {z\

\\z-z'\\<382},

we have -g;(xk) - Vgt(xk) (x — xk) < uk -9i(xk) - X7g,(xkf(x - xh) >uk

if i € a(z*), if i € f(z').

(3.20)

So when zk £ B(z~\ Z82) we have a(*') C «(**), j(z") C 7 (**) and /3(zk) C

fi(z').

(3.21)

The first-order Kuhn-Tucker conditions of the quadratic subproblem Qk can be written as Hk(z) = 0, (3.22) where Hk{z) is defined as Vf{xk) + Vg(xk)u + Vh(xk)v + Gk(x - xk) H (z) = j min(u, -g(xk) - Vg(xkf(x - xk)) k k k -h{x )-Vh{x f{x-x )

\

k

(3.23)

/

We now show that (3.22) has a solution if 82 sufficiently small. Similarly to the proof of Theorem 4.1 of Robinson (Ref. 23), we can easily conclude that the following matrix / V. V 5o(2 .,(x*) Vh(x') \ A. = -V5a(z.)(x-)r 0 0 j

\

-Vh(x'f

0

0

/

Approximate

Newton

Methods

153

is nonsingular, and the Schur complement B(z') =

C{z'f'A^C{z')

is a P-matrix (i.e., a matrix with positive principle minors), where V, 6 Vx>(z") and C{z') From the definitions of M(z,Hi) exists 83 > 0 such that when

0 0

and V x (z), for every e > 0 we can prove that there

zheB(z'-63)

=

{z\\\z-z'\\<63},

we have V,*(**)CV,.(z*) + e £ ( 0 ; l } ,

(3.24)

where 5(0; 1) = {2 g Rn\ \\z\\ < 1}. So we may restrict S2 and e such that for any zk € B(z'; S2) = {z\ \\z - z*|| < 62}, the matrix .. V ffa(z . ) (x fc )

G* *(**) = ) - v 5 a ( , - ) ( ^ ) -Vh(xkf

VA(**) \ 0 0

0 0

J

is nonsingular, and the Schur complement B(zk) = C{zk)TA(zk)

*C(zk)

is a P-matrix, where Vgp(z.)(xk) 0

( k

C(z ) = Note that in the matrix

A(zk) k

-C{z f

C(zk)

0

(3.25)

the index sets a and 0 are defined at z" but the various gradients are evaluated at In order to consider the solvability of the system (3.22), we consider the solvability of the following system F„* ,„*(!*) + Gk

+ Vh(xk)d» = 0, -gi(xk) - Vgi(xkfdx = 0 for i G a(z'), mm(uk + d"-,-g,(xk) - Vgt(xkfdx) = 0 for i € /?(z*), for z 6 7(2*), w* +
(3.26)

J. Han and D. Sun

154

The component dUt is explicit for i £ j(z'). Simplifying these equations, we deduce that the remaining components of the vector d = (dx,du,dv) £ Rn x R" x Ri can be obtained by solving the mixed linear complementarity problem q(zk) + A(zk)w + C{zk)d^ -gp(xk)-C(zk)Tw>0, u* + d»" > 0, I [-gp(x«)-C{zk)Tw]T{4

= 0, ^M>

+ d^) = 0,

where w = ( d - . d - . O . f(**) = (&(**)»-»•(**),-A(**)), &(**) =

F „*{xk)~Vg^xk)uk uK

and a, /? and 7 denotes respectively the index sets a(z*), P(z*) and 7(2*). From linear complementarity theory (see, e.g., Murty (Ref. 11)), we know that a sufficient condition for the system (3.27) to have a unique solution is (i) the matrix A(zk) is nonsingular and (ii) the Schur complement B(zk) = C(zk) A(zk) C(zk) is a Pmatrix. Since we have proved that these two conditions are satisfied, system (3.27) has a unique solution. Then system (3.26) has a unique solution when zk £ B(z*; <52). We denote this solution by dk = (rf*\
xR" x K>.

It is easy to prove that for each k there exists i 6 I13 such that H^(zk)

+ B{i)kdk = 0.

(3.28)

From the proof of Theorem 3.1, we know that ||*h + d * - z * | | < i ] | * f c - * * | | .

(3.29)

Let zk+1 =zk + dk. Then zk+l € B{z"; 62) if zk 6 B{z~; S2). We now prove that Hk(zk+1) zk, zk+1 £ B{z*;62), we have mm(uk+\-9i(xk)

= 0, which means that (3.22) has a solution, when

- V g ^ f ^ -g,(xk) Sf+1

1

- xk))

- Vgi(xkf(xk+l

- xk)

if i 6 a ( * ' ) , if i £ -y(z').

Approximate

Newton Methods

Thus if zkeB(z';62),

k+t 1) Hkk(zk+

H (Z )

155

then k k kk k (Fu.ut vt„*(**) (xk) + Vg(x )d»" + Vh(* )d» + G d** \ (F Vg(xk)d" Vh(*k)d" Gtk<*** k = min(u* + « f \ -g(x ) V (x*) V ) nan(u* ^ , - j ( * * ) - V 5f f ( * * ) V

V \

-*(**) - Vfc(sf>* VMx*) V

//

k fc .*(**)++VV5(x V k ++Vfc(*V Vh(xk)d"k++ G Gt„*(x*) 5(x )
= 0, which means that system ffl(z) = 0 has a solution zfc+1 in B(z*;62), i.e., z*c+1 is a Kuhn-Tucker point of (1.2). Suppose that i*+1 6 £(z-;Z62) is an arbitrary solution of Hk(z) = 0. Since zk+l € B{z'; 3S2), then T min(u* ++11 \- 5 ,(x*) - V«7,-(x*) V«7,-(x*)T(x*+> (x*+>- -xkx))k))

f -g,(xk) 1 ik+l

- Vgi{xk)T($k^

- xk)

if a(z*), if t € a(z*), if f(z'). if i G 7(*»).

Therefore d* = zt+1 - zk is also a solutton of syssem (3.26)) From the uniqueness of the solution of system (3.26-), we know that z*+1 = zk+1, which shows that zt+1 is the closest Kuhn-Tucker point to zk in terms of distance \\zk+1 - zk\\. So there exists i 6 P such that ZM

=

sk+l = zk_

B-l^(.)(/))

which means that approximate "Newton method is a special case of GANM in a neighborhood of z* So we complete the proof of Corollary 3.1 by considering Theorem 3.1. □ Remark 3.3. If we choose Gk 6 V^(zk),

4

(3.7) and (3.8) are satisfied.

Some Discussions

In this paper we considered the local convergence of approximate Newton or SQP methods for LC 1 optimization problems without assuming the strict complementarity condition. The global convergent technique used in Qi (Ref. 19) can be applied to this paper similarly.

J. Han and D. Sun

156

GANM is useful in proving the Q-superlinear convergence of approximate Newton or SQP methods, but it can't be used in practice since we don't know oc(z'), fi(z') and 7(2*). The approximate Newton or SQP methods are well used and in each step a quadratic programming is needed to be solved. In the following we give such a method that in each step only a linear equations is needed to be solved. Given z° = {x°,u°,v0) For k = 0,1,...,

g R" x R" x R". zk+1 = zk - B;lH(zh),

where Bk G dQHk(zk)

= {VLk(zk)T}

Lk(z) = Vf(xk)

(4.1)

x dbgk(zk) x {Vhk(zk)T},

+ Vg(xk)u + Vh(xk)v

gk(z) = min(u, -g(xk)

+ Gk{x -

- Vg(xkf(x

-

and xk),

xk))

and hk(z) = -h(xk)

- Vh(xkf(x

-

xk).

It is easy to see that in a neighborhood of the solution z" of H(z) = 0, the above method is a special case of GANM. So similar convergent properties for (4.1) can be found in Theorem 3.1. Acknowledgements. The authors thank the two referees for their valuable com­ ments and suggestions on this paper and are grateful to Professor L. Qi for his helpful suggestions on nonsmooth equations and related problems.

References [1] J. D. Aubin, and F. Frankowska, Set-Valued Analysis, Birkhauser, Boston, 1990. [2] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983. [3] J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Opti­ mization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jercy, 1983. [4] U. C. Garcia Palomares and O. L. Mangasarian, Superlinearly convergent quasiNewton algorithms for nonlinearly constrained optimization problems, Mathe­ matical Programming 11 (1976) 1-13. [5] S. P. Han, Superlinearly convergent variable metric algorithms for general non­ linear nrogramming problems, Mathematical Programming 11 (1976) 263-282.

Approximate Newton Methods

157

[6] J. B. Hiriart-Urruty, J. J. Strodoit and V. H. Nguyen, Generalized Hessian ma­ trix and secord-order optimality conditions for problems with C 1,1 data, Applied Mathematics and Optimization 11 (1984) 43-56. [7] N. H. Josephy, Newton's method for generalized equations, Technical Summary Report 1965, Mathematical Research Center, University of Wisconsin-Madison, 1979. [8] N. H. Josephy, Quasi-JVewton methods for generalized equations, Techni­ cal Summary Report 1966, Mathematical Research Center, University of Wisconsin-Madison, 1979. [9] G. P. McCormick, Penalty function versus non-penalty function methods for constrained nonlinear programming problems, Mathematical Programming 1 (1971) 217-238. 101 R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization 15 (1972) 957-972. 11] K. G. Murty, Linear Complementarity, Helderman-Verlag, Berlin, 1988.

Linear and Nonlinear

Programming,

121 J- M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. 131 J.-S. Pang, S. P. Han and R. Rangaraj, Minimization of locally Lipschitzian functions, SIAM Journal on Optimization 1 (1991) 57-82. 141 J.-S. Pang, A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems, Mathematical Programming 51 (1991) 101-131. 15l J.-S. Pang and L. Qi, Nonsmooth equations: motivation and algorithms, SIAM Journal on Optimization 3 (1993) 443-465. 16] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equa­ tions, Mathematics of Operations Research 18 (1993) 227-244. 171 L. Qi, LC 1 functions and LC 1 optimization problems, Applied Mathematics Preprint 91/21, School of Mathematics, The University of New South Wales, Sydney, Australia, 1991. 18] L. Qi and J. Sun, A nonsmooth version of Newton's method, Programming 58 (1993) 353-368.

Mathematical

191 L. Qi, Superlinearly convergent approximate Newton methods for LC 1 opti­ mization problems, Mathematical Programming 64 (1994) 277-294.

158

J. Han and D. Sun

[20] L. Qi and R. Womersley, An SQP algorithm for solving extended linearqua.dra.tic problems in stochastic programming, Applied Mathematics Preprint 92/23, School of Mathematics, The University of New South Wales, Sydney, Australia, 1992. [21] S. M. Robinson, A quadratically convergent algorithm for general nonlinear programming problems, Mathematical Programming 3 (1972) 145-156. [22] S. M. Robinson, Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming algorithms, Mathematical Programming 7 (1974) 1-16. [23] S. M. Robinson, Strongly regular generalized equations, Mathematics of Oper­ ations Research 5 (1980) 43-62. [24] R. T. Rockafellar, Computational schemes for solving large-scale problems in extended linear-quadratic programming, Mathematical Programming 48 (1990) 447-474. [25] R. T. Rockafellar and R. J.-B. Wets, Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time, SIAM Journal on Control and Optimization 28 (1990) 810-822. [26] N. Z. Shor, A class of almost-differentiable functions and a minimization method for functions of this class, Kibemetiica 4 (1972) 65-70. [27] D. Sun and J. Han, Newton and quasi-Newton methods for a class ofnonsmooth equations and related problems, Technical Report No. 026, Institute of Applied Mathematics, Academia Sinica, Beijing, China, 1994. [28] C. Zhu and R. T. Rockafellar, Primal-dual projected gradient algorithm for extended linear-quadratic programming, to Appear in SIAM Journal on Opti­ mization. [29] M. Lescrenier, Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold, SIAM Journal on Numerical Analysis 28 (1991) 476-495. [30] A. R. Conn, N. I. M. Gould and Ph. L. Toint, Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM Journal on Numerical Analysis 25 (1988) 433-460. Erratum in the same Journal 26 (1989) 764. [31] P. T. Boggs, J. W. Tolle and P. Wang, On the local convergence of quasinewton methods for constrained optimization, SIAM Journal on Control and Optimization 20 (1982) 161-171.

Second-Order Directional Derivatives

159

Recent Advances in Nonsmooth Optimization, pp. 159-171 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

On Second-Order Directional Derivatives in Nonsmooth Optimization L. R. Huang Department of Mathematics, South China Normal University, Guangzhou, China K. F. Ng Department of Mathematics, The Chinese University of Hong Kong, Hong Kong

Abstract Some relationships between the second-order derivative of Ben-Tal, Zowe and that of Chaney are established. These derivatives are used in providing optimality conditions for nonsmooth optimization problems with and without constraints.

1

Introduction

As a major role in second-order nonsmooth optimization problems, different kinds of generalized second-order directional derivatives have been introduced among which one has D2f(x;u,v) of Dem'yanov-Pevnyi [13], Ben-Tal, Zowe [3], and f"(x;x',u) of Chaney [6] where / is a locally Lipschitz real-valued function on a normed space X. In this paper, we shall survey some of the results obtained in [4, 14, 15, 16] as well as give further new results. In particular we provide, in section 4, a new set of sufficient conditions for a minimum point in nonsmooth optimization problems with and without constraints.

2

Definitions

Though most results can be generalized, we assume for simplicity that X = 1in; let W be an open set in X and / a real-valued locally Lipschitz function. The lower Dinidirectional derivative of / at x £ X in the direction u G X is denoted by D-f(x; u)

L. R. Huang and K. F. Ng

160 and is defined by D-f(x;u)

:= liminf j{f(x

+ tu) - / ( x ) } .

The upper Dini-directional derivative D+f(x;u) is similarly defined (with the lower limit replaced by the upper one). If D-f(x;u) = D+f(x;u) then the common value is denoted by f'(x;u). As in [2], Clarke's generalized (upper) directional derivative and subdifferential are denoted by f°(x;u) and df(x) respectively. In the case when f'(x;u) exists, the following definition was introduced by Ben-Tal and Zowe [3]. Definition 2.1 Let x € W and u,v G X. The Ben-Tal/Zowe lower and upper generalized second-order directional derivatives of f at x in the directions u and v are defined respectively by Dif(x;

u, v) := liminf i { / ( x + tu + t2v) - f(x) - tD+f(x;

u)}

(2.1)

Dlf(x;

u, v) := limsup - { / ( x + tu + t2v) - f(x) - tD.f{x\ no *

u)}.

(2.2)

and

It is easy to see that - oo < D2_f(x; u, v) < D\f(x;

u, v) < +oo

(2.3)

2

-D _f(x;u,v) = Dl(-f)(x;u,v). (2.4) Similar but different notions have appeared in the literatures, e.g. in Penot [20] and Studniarski [24]; these authors use D+f and D-f in the above definitions to replace £>_/ and D+f respectively. In our approach it is true [15] that if D2f(x;u,v) exists and is finite then the first-order derivative f'(x;u) also exists. This property is not shared by the approach of [20], [24] (see Example 3.6 in [24]). A sequence (i^) is said to converge to x in the direction u, denoted by ( i t ) —> u x, if (x/,) converges to x, x/c ^ x for every k, and the sequence (|| u \\ ,,**"*,.) converges to u. Chaney's subdifferential [5] of / at x in the direction u is denoted by duf(x) and defined to be the set consisting of all x* for each of which there exist sequences (a^) and x*k € df(xk) such that (x&) —> u x and (x*k) —» x' Because we have assumed that X = 7£", duf(x) is nonempty and duf(x) C df(x) since the multifunction df is upper semicontinuous [2]. The following generalized lower and upper second-order directional derivatives are also due to Chaney [5]. Definition 2.2 Let x e W and u 6 X. Suppose that x~ G <9„/(x). Then /i'(x;x*,u) is defined to be the infimum of all numbers lim inf -~{f(xk)

- f(x) - x*(xk - x)}

k^oot'k

taken over all triple of sequences (xk), (x£) and (tk) for which

Second-Order Directional Derivatives

161

(a) tk > 0 for each k and (xk) converges to x, (b) (tk) converges to 0 and f5^-12) converges to u, (c) (xj) converges to x* with x*k in df(xk)

for each k.

Similarly, /"(x;x*,u) is defined by the supremum of all numbers lim sup "5{/(x fc ) - f(x) - x"(xk - x)} fc—oo tk

taken over all triples of sequences (xjt), (x'k) and (tk) for which (a), (b) and (c) above all hold. Clearly, — oo < f"(x;x',u) < f+(x\x*,u) < +oo. Further, if f"(x;x',u) = f+(x;x",u), then we denote this common value by f"(x;x*,u) and call it Chaney's generalized second-order directional derivative of f at x and x* in the direction u.

Remark.

By (b), we see that if u ^ 0, then Xk — X \\xk-x\\

(xk — x)/tk \\xk-x\\ltk

u \\u\y

that is, (xk) converges to x in the direction u. Thus, lim inf ~^{f(xk)

- f(x) - x"(xk - x)}

k~ootk

= lim inf j ^ {f{xk) - f(x) - x'(xk - x)} *-°° || xk - x ||2 = || u f lim inf j fc-»oo || Xk

^ — {f(xk) — X

k

—r t{

- / ( * ) - x'(xk - x)} .

\\'

Hence, f"{x; x', u) equals to the infimum of all numbers || u ||2 lim inf -

jrr {f(xk)

- f{x) - x*(xk - x)}

fc^oo || xk — X | | '

taken over the set of all sequences (xk) such that (a') (xk) converges to x in the direction u and (b') there exists a sequence x"k € df(xk)

converging to x".

112

L. R. Huang and K. F. Ng

162

3

Relationships Between the two Second-Order Derivatives and Application for Convexity

In the case where / is C2 it is well known and easy to verify that the second-order derivatives of Chaney and Ben-Tal/Zowe are given by f"{x;x*,u)

= -

D2f(x; u,w) = -
, V2f{x)u

>

+x'(w),

where x' = S/f(x); this implies the following relationship between the two derivatives: f"(x;x\u)

= D2f(x;u,w)-x"{w),

Vw.

(3.1)

This relationship persists in some nonsmooth cases, e.g., if duf(x) = {x*} and /"(x;x*,u) exists (see [15, Corollary 4.2]. Another instance is provided by Theo­ rem 3.2 below. But (3.1) may fail to hold in general: the right-hand side of (3.1) may not be a constant function (of w); indeed it may be a convex and non-affine function of w. Based on the works of Ben-Tal and Zowe [3] the following weaken relation was established by Chaney [6] f"(x;x',u)=mi{D2f(x;u,v)-x*{v):veV>}

(e K)

(3.2)

for a very special class of nonsmooth functions. The following theorem 3.1 implies that (3.2) in fact holds in general provided that both sides of (3.2) exist in It. Theorem 3.1 Letx,u,x* G 1Z-n and suppose that x" £ duf{x) andx*(u) = Then f"{x;x',u) <mi{D2_f{x;u,v) - x*(v) :v£lln} < f'l{x;x\u)

D+f(x;u).

provided that the infimum is finite. Consequently, if f satisfies an additional condition that f"(x;x*,u) exists then f"(x;x',u)

= \nt{D2_f(x;u,v)

- x'(v) : v G

ft"}

(3.3)

Remark. In the terminology of convex analysis, the conclusion (3.3) simply says that f"(x;x*,u) equals to the value at x* of the conjugate function of D2_f(x;u,-). This result is proved in [15]. In a special case, it was established by Chaney [6] who considered / of the form f(x) = JlZi 9<(hi(x)) where each hi is a sup-type function and each #; is C2 with <7,'(/i,(x)) > 0. Theorem 3.2 Let x, u, x" G Un such that x" G duf(x), suppose that f"(x\x',u) exists. If inf{D2_f(x;u,w)

- x'(w) : w G ft"}

x'(u)

= f'(x;u),

and

Second-Order Directional Derivatives

163

and sup{D*/(x; u, w) - x'(w) : w € Tln) are both finite then D2f(x; u, to) exists and for all w € TZn f"(x; u, to) = D2f{x; u, to) - x*(to). The following result from [16] show that though Dlf(-,u,0) and D2_f(;u,0) do not equal in general but under reasonable conditions they have the same lower bounds on any open subset of "R.n Theorem 3.3 Suppose that f is regular on 7?" Let W be an open subset of TV1 and u€Kn. Then ini{D2+f(x;u,0)

:x€

w) = inf {Dif(x;u,0)

:x 6

w)

if the left-hand side is finite. Under the same conditions, we also have, for each x, that lim inf D\f(y; u, 0) = lim inf D2_f(y; u, 0) and lim

inf

Dlf(y;v,0)

y—*x,v—*x

T

= lim

D2_f(y;v,0)

inf y—*x,v—*u

Remark. As an application of Theorem 3.3, we note the following corollary which provides a sufficient condition for the existency of D2f(x;u,0). Corollary 3.4 If there exists xo € W such that inf{D*/(x;u,0) : x £ W] =

D2+f(xo;u,0)

then Dlf(xo;u,0)

=

D2_f(xo;u,0).

Indeed, by Theorem 3.3, the given assumption implies that D\f(x0; for all x and hence the equality at x = x0.

u, 0) < D2_f(x; u, 0)

Theorem 3.5 Let f be as in Theorem 3.3. Then f is convex on W if and only if D\f(x\u,Q) > 0 for each x € W and each unit vector u. For detailed proofs as well as the corresponding results in terms of Chaney's derivative, we refer the reader to [16].

L. R. Huang and K. F. Ng

164

4

Second Order Optimality Conditions

Let / , glt ■ ■ -, gm+p be real-valued locally Lipschitz functions on an open set W in 72". We consider the following optimization problems V, Vc without and with constraints respectively: (V)

minimize f(x),x

£ W

and (Vc)

minimize f(x),x

£ W

subject to

9i(x) < 0 for i £ {1,2,■■■,m} gj(x) = 0 for j € {m + 1 , ■•• ,m + p}. For any subset S C. W and x0 £ S, we use K$(x0) to denote the contingent cone [l] of S at x 0 . It is well-known and easily verfied that if x0 £ 5 is a local minimum point of / on S then D-f(x; •) > 0 on Ks(x0). The following result which roughly deals with a converse situation was established by Ioffe [17] for the special case when S = W and by the authors for the general case [14]. Lemma 4.1 Let S be a subset of TZ", x0 £ S and f be a locally Lipschitz function of S into TZ. Suppose that D-f(x0; u) > 0 for any u £ K$(x0)- Then for any e > 0, there exists 6 > 0 such that f(x0) < f(x) + t \\ x — x0 \\ for any x £ S with x / x0 and || x — x0 ||< 8; thus x0 is a strict local minimum point of Fc on S where Ft is defined by Fi(x):=f(x) + e\\x-x0\\. By virtue of this lemma and Ekeland's variational principle [l], one can show (cf. [14]): Theorem 4.2 Let f : W —> 7Z be a locally Lipschitz function such that D_f(x0; •) > 0 on Tln. Ifu £ Tln is such that D-f(x0\u) = 0, then 0 £ duf(x0). More generally, we have Theorem 4.3 / : W —> 72. be locally Lipschitz near x with x £ W. Then 7J_/(i; ■) is continuous, and, for any unit vector u in 7Zn with D-f(x; u) = mini|„||=1 D-f(x; v), one has 0 e 8J(x) + D-f(x;u)Bi, where B\ denotes the unit ball in 72.™. Proof. That D-f(x;-) is a continuous (finite) real-valued function follows from the Lipschitz property of / . By compactness it follows that there exists u £ B^ such that D-f(x;u) = min||„|)=1 D-f(x;v). Fix any such u, let F : 72" —► 72 be defined by F(y):=f(y)-D^f(x-u)\\y-x\\.

Second-Order Directional Derivatives

165

Then it is easy to verify that D-F(x;v)

= D..f(x;v)

- D-f(x;u)

>0

for all v with || v || = 1 and, in particular, D.F(x;

u) = D-f{x; u) - D-f(x;

u) = 0.

It follows from Theorem 4.2 that 0 6 duF(x) : there exist sequences tk, zk and z'k with tk 1 0, ^ 2 —► u and z'k G dF(zk) convergent to 0. Since by [2, Proposition 2.3.3], 9F(zk) C df(zk) + D.f(x;u)d(\\--x 11)00 and since d(- || • - x \\)(zk) Q Bu we write z\ = x"k + D_f(x; u)y'k with xj G 0 / 0 * ) and yl E Bi. Since the subdifferential function takes values locally in a compact set [2, Proposition 2.1.2], and by considering subsequences if necessary, we can assume that x\ —► x* and y"k —> y* for some x* and y* in TV1 These imply that x" G duf(x) and y" G Bi and so 0 = x- + £ > _ / 0 ; u)y* G 9 u /(u) + f»_/(x; w)5i-

□

Remark. Let / : w —> 7?. be a locally Lipschitz function and attain its local minimum at some point x0 G W (thus, in particular D-f(xo; •) > 0 on 1Z\). Suppose u G 72A is such that Z)_/(xo; u) = 0 then, by Theorem 4.2, 0 G duf(x0). Consequently f'l(xo; 0,u) is meaningfully defined by Definition 2.2 and, in fact, it is now easily seen from the definition and the minimality that f'l(xo; 0, u) > 0. This result on necessary conditions for / to attain its minimum extends the corresponding result of Chaney [8] in two aspects: firstly we have removed his additional semismooth assumption of / , secondly the positive definite property of f'l(xo', 0, ■) is now established on the whole set {u : D-f(xo',u) = 0} of ''critical directions" while his result is only on a subset. See [8] and [14] for details. The following result plays a key role for our subsequent discussions. Theorem 4.4 Let f : W —► 1Z be a locally Lipschitz function and x0 G Tin Suppose that D-f(x0; •) > 0 on TZn Let u G TV be a unit vector and let (xk) be a sequence convergent to x in the direction u such that f(xk) < f(x0) for each k. Then 0 G dj(x0) and fZ(xo;0,u) < 0.

Proof. From the assumption of (xk), one has D-f(x0;u) < 0 and in fact the equality holds in view of the given condition D-f(x0; •) > 0 on TZn. By Lemma 4.1 (with S = W), this condition also implies that for any («;) J. 0 with e; G (0,1), there exists (Si) I 0 such that Fit(x) '■= / O ) + «; || x — x0 || attains a minimum on B[x0,6i]

L. R. Huang and K. F. Ng

166

at x 0 . Now for each i, take a large enough fc; such that xki € B[x0, j6;]. Note that if x g B[x0,2 || xki - x 0 ||] then f{xk.) < / ( * . ) < f(x) + £,■ || * - i . ||< / ( * ) + 2e, || xki - io || • By Ekeland's variational principle [l] with A = e]/2 || «*, - x„ || / 2 , we can find zki 6 B[x„, 2 || xki — x 0 ||] such that

(i) I I * * - * * , ||<£! / 2 ||x f c j -x 0 ||/2, (ii) / ( * * ) < / < * * ) , and (iii) /(**,) < / ( * ) + 4«J/2 || x _ ^

|| for

a ll a

g 5 [ x 0 ) 2 || x*. - x 0 |||.

From (i) we have x<, ^ zjt, and zki lies in the open ball B(x 0 ,2 || x^, — x 0 ||). Thus, from (iii) we obtained 0 € df(zki) + 4eJ B\ by results of Clarke [2], and so there exists

*;ea/(xOwith 114 ll<4ej/2; therefore (zJJJ —> 0 6 3/(x„). Note that by (i)

( ( * * . - * * i ) / I I * * . - * . ID — o Then for f, = || x t l - x„ ||, Zfc, - X 0

_ [(zt, - X t , ) / < , ] + [(Xfc, -

x0)/U]

II **.- - *<« II ~ II (2*. - x*. )/U + (xk, - x„)/U || Hence the properties (a'), (b') in the Remark after Definition 2.2 are satisfied by the sequences (zkt), {z*k%). It follows from the definition of / " , (ii) and the inequality / ( * * ) < / ( * . ) that' /"(x„; 0, u) < lim inf j

— — {f(zk%) - /(*„)} < 0.

—°° II «*. - xo II 2

□

This result provides a short proof of the following sufficient condition theorem [14, Theorem 2.9], for the problem V. T h e o r e m 4.5 (Second-order sufficient conditions without constraint). and suppose that (i) D-f(xo;)>0

onTln,

Let x 0 € W

Second-Order Directional Derivatives (ii) / " ( x o , 0 , u) > 0 whenever D-f(x0;u)

167 = 0, and u / 0.

Then there exists 6 > 0 such that f(x) > f(x0) for all 0 ^ | | x — x0 ||< <S. Indeed, if not: there exists a sequence (i^) in W such that x* —» i 0 , Xk ^ x„ and /(**) < / ( i o ) - By compactness of the unit ball in 1ln we assume without loss of generality that xk —» u x„ for some unit vector u. Then D_/(x„;ii) = 0 by (i), and hence / " ( x o ; 0 , u ) < 0 by Theorem 4.4. This contradicts the given assumption (ii). Remark Theorem 1 of Chaney in [9] is a weak form of the following result where he assumed the following stronger condition in the place of (ii): (ii)* / " ( x 0 ; 0,u) > 0 for all unit vectors u in Hn for which 0 £ <9u/(x0). Corollary 4.6 Let x 0 € W, and suppose that (i) v ■ u > 0 for all unit vectors u in 1Zn and v in <9 u /(x 0 ). (ii) f"(xo;0,u)

> 0 for all unit vectors u in 1Zn for which Z)_/(x 0 ;u) = 0.

Then there exists 6 > 0 such that f(x) > /(x 0 ) for all 0 <|| x — x 0 ||< 8. To see this corollary we need only to show that there exists V- £ duf(x0) such that D-f(xo,u) = V- ■ u. In turn, for each t > 0, we apply the Mean Value Theorem of Lebourg [10, Theorem 2.3.7] to obtain at € (0,t) and vt € df(xo + atu) such that - { / ( X 0 + tu) - f{x0)}

= VfU

Passing to the lower limits, we have D-f(xo\u) = liminf ( j 0 f( • "• Since the multi­ function x —► df(x) is closed and locally takes values in a compact set [10], we can choose a sequence (/„) J. 0 such that lim„_ 00 vtn = u_ for some i;_ € <9/(x0). Clearly V- has the desired properties, as (x 0 + at„u) converges to x0 in the direction u. In connection with the constrained problem (Vc), let x 0 £ W be feasible (i.e. x 0 satisfies the given constraints). Let us say that a locally Lipschitz function F : W —► 11 is an allied function to / at x 0 if F(x) < F(x0) whenever x £ W is feasible and f(x) < f(x„). For example, if 0 = (/?,•)So* € ^ 1 + m +P is a "Lagrange multiplier compatible with x 0 ", that is, if m+p

A , A , ■ ■ ■, A* > 0 and (5m+u ■ ■ -,pm+p such that Pi9i(x.) = 0

€ 11 with £ .=o

# = 1

L. R. Huang and K. F. Ng

168

for all i = 1, • • • , m + p, then the corresponding Lagrange function L defined by m+p

L(x) := &/(*) + J2 pi9t(x) i=l

is an allied function to / at x0. Theorem 4.7 Let L : W —► 11 be an allied function of f at x0 such that D-L(x0; •) > 0 on 1Zn. Let (xk) be a sequence of feasible points in W convergent to x0 in the direction u, and suppose that f(xk) < / ( x 0 ) for all k. Then 0 6 3 u i(x 0 ) and

i'I(x„;0,u) < 0 . Proof. By assumptions, L(xk) < L(x0) for each k. Now the result follows from Theorem 4.4 (applied to function L in place of / ) . Part (ii) of the following theorem is a restatement of Theorem 4.7 while (i) is easy to verify. Theorem 4.8 Let (xjt) be a sequence of feasible point such that xk —►„ x 0 and f{xk) < /(xo) for each k. Then the following statements hold: (i) u € Ks{x0) and D-f(x0;u)

<0

(ii) If L is an allied function of f at x0 such that D-L(x0\-) 0 € duL(x0) and L'L(xo;0,w) < 0.

> 0 on 1in then

Let U denote the set of all unit vectors u in TV1 with the following property: there exists a sequence (x^) of feasible points such that x* —►„ x0, and / ( x t ) < / ( x 0 ) for all it. Theorem 4.9 (Second-order sufficient condition with constraints) Suppose for each u 6 U, there exists an allied function L of f at x0 such that D_L(x0\ •) > 0 on 1Zn and L"(x o ;0,u) > 0. Then there exists S > 0 such that f(x) > f(x0) for every feasible x ^ x 0 satisfying || x — x0 ||< <5. Remark. This result clearly improves an earlier result of ours [14, Theorem 5.7], which in turn extends a result of Chaney [9] where the function L is required to assume the regularity condition. Proof. Suppose not: there exists a sequence xk —► x„ and f(xk) < /(x 0 ) for each k. Without Xk —* u x0 for some unit vector u. Then u G U. allied function L of / at x» such that £>_Z,(x0;-)

(xk) of feasible points such that loss of generality we assume that By assumptions, there exists an > 0 and L"(x o ;0,u) > 0. This

Second-Order Directional Derivatives contradicts (ii) to Theorem 4.8.

169

□

For discussion of the accompany necessary condition theorems for (V) and (Pc) we refer the reader to [14]. Results in terms of the second-order derivatives of Cominetti and Correa [11] are also studied in [4]. A c k n o w l e d g e m e n t s . The author gratefully acknowledge the financial supports from the Research Grant Council of Hong Kong, the United College and the Institute of Mathematical Science, Chinese University of Hong Kong.

References [1] J-P Aubin and I. Ekeland, Applied Nonlinear Analysis (John Wiley & Sons. 1984). [2] A. Ben-Tal, Second-order and related extremality conditions in nonlinear pro­ gramming, Journal of Optimization Theory and Applications 31(1980) 143-165. [3] A. Ben-Tal and J. Zowe, Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems, Mathematical Programming 24 (1982) 7091. [4] W. L. Chan, L. R. Huang ang K. F. Ng, On generalized second-order derivatives and Taylor expansions in nonsmooth optimization, SIAM Journal on Control and Optimization 32 (1994) 591-611. [5] R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Anal­ ysis Theory, Methods and Applications 9 (1985) 1189-1209. [6] R. W. Chaney, Second-order directional derivatives for nonsmooth functions, Journal of Mathematical Analysis and Application 128 (1987) 495-511. [7] R. W. Chaney, Second-order necessary conditions in constrained semismooth optimization, SIAM Journal on Control and Optimizations 25 (1987) 1072-1081. [8] R. W. Chaney, Second-order necessary conditions in semismooth optimization, Mathematical Programming 40 (1988) 95-109. [9] R. W. Chaney, Second-order sufficient conditions in nonsmooth optimization, Mathematics of Operations Research 13 (1988) 660-673. [10] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley-interscience, New York, 1983.

170

L. R. Huang and K. F. Ng

[11] R. Cominetti and R. Correa, A generalized second-order derivative in nonsmooth optimization, SIAM Journal on Control and Optimization 28 (1990) 789-809. [12] C. N. Do, Generalized second-order derivatives of convex functions in reflexive Banach Spaces, Trnasactions of the American Mathematical Society 334 (1992) 281-301. [13] V. F. Dem'yanov and A. B. Pevnyi, Expansion with respect to a parameter of the extremal values of game problems, USSR Computational Mathematics and Mathematical Physics 14 (1974) 33-45. [14] L. R. Hunag and K. F. Ng, Second-order necessary and sufficient conditions in nonsmooth optimization, Mathematical Programming (1994) 379-402. [15] L.R. Huang and K.F. Ng, On some relations between Chaney's generalized second-order directional derivative and that of Ben-Tal and Zowe, SIAM Journal on Control and Optimization (to appear). [16] L. R. Hunag and K. F. Ng, On lower bounds of the second-order directional derivatives of Ben-Tal - Zowe and Chaney, submitted. [17] A. D. Ioffe, Calculus of Dini subdifferentials of functions and contingent coderivatives of set-valued maps, Journal of Nonlinear Analysis Theory, Methods and Applications 8 (1984) 517-539. [18] H. Kawasaki, Second-order necessary and sufficient optimality conditions for minimizing a sup-type function, Applied Mathematics and Optimization 26 (1992) 195-220. [19] R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization 15 (1977) 959-972. [20] J.-P. Penot, Generalized higher order derivatives and higher order optimality conditions, preprint, Universite de Pau, 1985. [21] J.-P. Penot, Second-order generalized derivatives: comparisons of two types of epi-derivatives, Lecture Notes in Economics and Mathematical Systems 382 (1992) 52-76. [22] R. T. Rockafellar, First-and second-order epi-differentiability in nonlinear pro­ gramming, Trnasactions of the American Mathematical Society 307 (1988) 75108. [23] R. T. Rockafellar, Second-order optimality conditions in nonlinear program­ ming obtained by way of epi-derivatives, Mathematics of Operations Research 14 (1989) 462-484.

Second-Order Directional Derivatives

171

[24] M. Studniarski, Second-order necessary condition for optimality in nonsmooth nonlinear programming, Journal of Mathematical Analysis and Applications 154 (1991) 303-317.

M. Kocvara a n d J. V.

172

Outrata

Recent Advances in Nonsmooth Optimization, pp. 172-192 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

On the Solution of Optimum Design Problems with Variational Inequalities Michal Kocvara and Jiff V. O u t r a t a Institute of Information Theory and Automation, Czech Academy Voddrenskou vezi 4, 182 08 Praha 8, Czech Republic

of Sciences,

Pod

Abstract

The paper deals with the numerical solution of a class of optimum design prob­ lems in which the controlled systems are described by elliptic variational in­ equalities. The approach is based on the characterization of (discretized) sys­ tem operators by means of generalized Jacobians and the subsequent usage of nondifferentiable optimization methods. As an application, two important shape design problems are solved.

1

Introduction

O p t i m a l control problems, in which the controlled systems are governed by monotone variational inequalities, arise frequently in economic modelling and o p t i m u m design. Inspite of t h e fact t h a t the basic theoretical questions, connected with t h e existence of solutions, optimality conditions and suitable approximations, have been already successfully answered, the numerical solution of such problems remains t o be a difficult task. A classical regularization technique ([8]) consists in converting t h e variational inequality into an equation by means of a smooth penalty. In this way, one obtains a s t a n d a r d optimal control problem, to the solution of which various effective m e t h o d s are available. However, the smooth penalization leads either to a low accuracy or to ill-conditioned problems. Moreover, the incidental presence of state-space constraints which are mostly also treated by a smooth penalization, makes a suitable choice of t h e single penalty p a r a m e t e r s extremely cumbersome. Similar difficulties can be expected when using the penalty approach of [6], where the resulting optimization problem has to be solved on t h e product of the state and the control space.

O p t i m u m Design Problems

with Variation*/

173

Inequalities

In this p a p e r we develop another approach, started with [18], in which we, under suitable a s s u m p t i o n s , handle t h e variational inequality as a nondifferentiable con­ trolled s y s t e m by using t h e tools of nondifferentiable analysis [2]. As already shown in [19] a n d [17], in this way one can achieve a substantially higher accuracy compared with t h e regularization technique. Moreover, t h e incidental state-space constraints m a y be t r e a t e d by exact penalties, which further contributes to t h e quality of the results. In t h e spirit, our approach is close to the heuristic algorithms suggested in [5], b u t we do not use any heuristic reasoning in its development 1 . Assume t h a t U and Y are Banach spaces, B[U —> Y*\ is a linear continuous operator, t h e m a p A assigns to controls u linear selfadjoint elliptic ([8]) operators m a p p i n g Y into Ym and K C Y is a n o n e m p t y closed convex set. We confine ourselves to the controlled systems governed by the following variational inequality: For a given control u 6 U, find the state variable y 6 K such t h a t {A(u)y - Bu, v - y) > 0 for all v £ K.

. . ^ '

Since A is a selfadjoint operator, solving (1) for a given control u a m o u n t s to solving the convex p r o g r a m

±(y,A(u)y)-(Bu,y)

-> inf

subject to

(2) y e K,

which clearly possesses a unique solution due to the ellipticity of A(u) [8]. Also, if we discretize (1) e.g. by a finite element ( F E ) m e t h o d , a finite dimensional approximation y of y, corresponding to a finite dimensional approximation u of u, can b e found as t h e u n i q u e solution of a finite dimensional convex q u a d r a t i c p r o g r a m m i n g problem of t h e form (2). Therefore it is reasonable to investigate the optimization of systems governed by (1) (after an appropriate discretization) in a more general framework of two-level optimization problems #(u,y) -»inf subject to y 6 argmin
W

u £ w, m

where u £ R , y , v G R",.=, is a closed convex subset of lR n , u> is a compact subset of IR m , a n d for any fixed u 0 £ u the lower-level problems (y?(u0, v ) -* inf subject to

(4)

'After the paper had been finished, the autors learned about another approach proposed by J.S. Pang. This approach relies on a combination of interior and exterior penalties. It requires, however, the strict complementarity to be satisfied at the solution point. This is frequently violated in the applications discussed in Section 3.

174

M. Kocvara and J. V. Outrata

satisfy a number of assumptions. Problems (3) belong to so-called Stackelberg prob­ lems and have been already intensively studied from various points of view ([20,1,15]). Under the assumptions of [3], guaranteeing that the map S : U H arg min <^(u, v) is a locally Lipschitz operator, (3) may be rewritten into the form 0{u)=0(u,S(u))-Mnf subject to

(5) u 6 u).

Hence, to its numerical solution, existing nondifferentiable optimization (NDO) meth­ ods can be applied, provided 0 is at least directionally differentiable and we are able to compute vectors from the generalized gradient of 0 for arbitrary u 6 u>. This so-called direct method has been proposed and investigated in [18], where for the computation of the mentioned "subgradients" a passable way is derived provided the operators Vy U y>(u,S(u)) []Rm —> R n ] are surjective for all u 6 w. The aim of this paper is (i) to analyze the nonsurjective situation (appearing often in practical problems) from the point of view of the computation of "subgradients"; (ii) to apply the mentioned approach to two important design problems. Concerning item (i), in the next section we derive conditions, under which a matrix from the generalized Jacobian ([2]) of S at an u 0 6 lRm can be expressed as a linear operator denned by a special quadratic programming problem. The verification of these conditions is not easy in the general case, but assuming a special structure df E, they may be substantially simplified. It allows in particular to test the correctness of the vectors supplied as subgradients in the "packaging" and in the "incidence set identification" problems, used in Section 3 as test examples. However, even without this testing we have not observed any difficulties related to wrong subgradients. For the reader's convenience we recall still the definition of the generalized gradient and generalized Jacobian used throughout the whole paper. Definition 1.1 Let the operator F[Rm —» Ht"] be Lipschitz near x0 € H m and let up denote the set of points at which F fails to be differentiable. The generalized Jacobian of F at x0, denoted 8F(x0), is the set of[n x m] matrices, given by dF(xo) = conv I lim V_F(x,) | Xj —► x 0 , xi £ °~F{ For n = 1, dF(xo) is termed the generalized gradient of F at x0. Its elements are called subgradients. R e m a r k . The term subgradient is borrowed from convex analysis, where it is used for the vectors belonging to the subdifferential. Recently, however, it is frequently used also in a nonconvex setting for the elements of various generalized gradients.

Optimum Design Problems with VariationaJ Inequalities

175

The following notation is employed: A/"(C) is the null space of a linear operator C, S'(x0; d) is the directional derivative of an operator 5 at a point x0 in the direction d, Pi denotes the subspace of the polynomials of the first-order and x' is the i t h coordinate of a vector x G IRm and for x, y G R n the inequalities x > y (x > y) mean x' > y" (x* > y') for all i. H1, H£ are the usual Sobolev spaces W1-2, W01,2 and A denotes the closure of a set A.

2

Computation of the Subgradients

Let S = {yeB."|**'(y)<0, 1 = 1,2,...,?},

(6)

where functions $*[R" —* R] are convex and twice continuously differentiable. As­ sume that there exists an open subset V of R m containing u> such that

0, 0,

i = l,2,...,P,

. . >

(

v . . where £(u,y,A) = <^>(u,y) + *£. A'$'(y) is the standard Lagrangian. To be able to utilize the strong results of [3, 10], we impose still the Strong Second-Order Sufficient Condition, i.e., (A2) for all u 0 G V, y 0 G 5(u 0 ) and h G R m , h + 0, one has (h,V 2 , y £(u 0 ,yo,A 0 )h) > 0 , whenever (V*'(y 0 ), h> = 0

for

i G J(y 0 ) := {} € 7(y 0 ) | AJ0 > o}

Under (Al) and (A2), S is single-valued on V; moreover, it is locally Lipschitz ([3]) and directionally differentiable ([10, 13] ). The same is true about the operator A[R m —t R p ] , assigning to vectors u 0 G V the corresponding Kuhn-Tucker vectors An. It is well-known that if the strict complementarity condition 7(y 0 ) = J{yo) holds

176

M. Kocvara, and J. V. Outrata

at some y„ = S(u 0 ), u 0 G V, then 5 is even difFerentiable at u 0 ([4]). The gradient VS(uo) is in this case given as the operator which assigns to an arbitrary vector z G R m the (unique) solution of the quadratic program i(v,Q(u 0 )v> + ¥ ,(u ( u 00,,y y 00 ))z,v) z,v) — —► inf subject to

(8) i/(y„)(uo), v G £/(y„)(uo),

where Q(u0) = V ^ y £ ( u 0 , y 0 ) A0) and for an arbitrary index set G C { 1 , 2 , . . . ,p] LG(u)) = {{vv G £ RR"" | | (V*'(S(uo)),v) (V$ i (5(u 0 )),v) = 0, it 6G G) G}

(9)

If the differentiability of S at some u 0 G V is not ensured by the strict comple­ mentarity condition, we need for the evaluation of a subgradient from d 0 ( u o ) one arbitrary matrix from the generalized Jacobian dS(u0). Such matrices will now be constructed exactly according to Definition 1.1. Let y„ = S(u 0 ) and let the index set J(y 0 ) satisfy the inclusions (10)

J(yo) C J(y 0 ) C 7(y 0 ).

We denote A = 7(y 0 ) \ J{y0), & = J(y0) \ J(yo), o,ouo2,33 the cardinalities of I(yo),J(yo), A and B, respectively, and C(y 0 ) the [o x m] matrix, composed from V$'(y 0 ), i G 7(y 0 ), as rows. Evidently, C(y 0 ) may be divided into three matrices Cj{y0),CA{y0) and Cg(y0), composed from V$'(y 0 ) for i G J(y0),i G A and i G B, respectively. P r o p o s i t i o n 2.1 Let assumptions (Al), (A2) hold, u 0 G V,y 0 = S(u„) and let the index set J(y 0 ) satisfy inch (10). Assume that the linear system --C CTjA({yo)y\ yo)yI

+ Q(u 00)y^ )y; + y2* + Ce(y0)y5 )y*3

does not possess a solution (y-uy'2,y'3,y'4,yl) the conditions

(yi.y»)>o,

+

Cj(y 0 )yJ + C j ( y 0 ) y ; 2

g R° x R

03

xR

m

=0 =0

l[ii llj

>

3

x R°> x R° , satisfying

(yr,y;)^o

yie^((VXu 0t y 0 )f)n^(C J (y 8 )).

(12)

TTien tne operator Pj (u„) wfcicft assijw to an arbitrary vector z G R " «Ae fwj'^e) solution of the quadratic program i(v,Q(u0)v) + ( V V ^^(U u 0c, y oo)Kz ,vv )) -> inf subject to

(13) v G 6 7j(yo)(uo) ij(yo)(uo)

belongs to

dS(u0).

Optimum Design Problems with Variational Inequalities

177

Proof. In the first step we show the existence of a direction h e R " for which J ( S ( u 0 + Mi)) = 7(5(u 0 + Mi)) 0h)) = J(y J(y00))

(14)

for all sufficiently small positive t). By using of the directional derivatives of S and A, this condition may be rewritten into the form C^(y )5'(u 0 ;h) C4(y 0 )S'(u (A')'(u 0 ;h)

< 0 >0

iovzeB. fortGB.

(15)

Denote by A/(u 0 ) the subvector of A(u 0 ) composed from the multipliers, correspond­ ing to active constraints. Again, A/(u 0 ) may be decomposed into Aj(u 0 ),A^(u 0 ), A B (u 0 ) in the same way as C(y 0 ). The vectors S'(u 0 ;h), A' 7 (u 0 ;h) form the unique Kuhn-Tucker point of a special quadratic program with the constraints Cj(y0)S'(u0; h) = 0, CA(y0)S'{\i0;h) < 0 and C e (y 0 )S'(u 0 ; h) < 0, (cf. [10]), for which the KuhnTucker conditions attain the form Q(u 0 )S'(u )5'(u 0 ; h) + V ^ ( U o , y 0 )h + C r (y 0 )A',(uo; )A' / (u 0 ; h) = 0 (A')'(u 0 ; h ) ( V $ ' ( y 0 ) , 5'(u 0 ; h)) = 0, (A')'(u 0 ; h) > 0

for i g I(y0) \ J(y„).

(16)

By combining of relations (15),(16) and using the complementarity argument, one immediately concludes that the desired direction h exists whenever the linear system of equalities and inequalities Q(u 0 )S'(u 0 ;h) + V ^ ( u 0 , y 0 ) h + C Cj(yo)A^(u j ( y 0 ) A ^ u 00;;y y 00 ) + CjA' e (u 0 ;y 0 ) = 0 Cj(y0)S'(u0;

h) = 0,

C^(yo)5'(u0;h)<0,

C e (y 0 )S'(uo; h) = 0

(17)

A'B(uo;yo)>0

is consistent. Its consistency is according to the well-known Motzkin theorem of the alternative ([16]) equivalent to the inconsistency of (11), (12) and thus, under the assumptions imposed, the strict complementarity condition holds at the points u 0 + tfh for all tf > 0 sufficiently small. Consequently, S is differentiable at these points and VS(u 0 + tf h) is the operator, assigning to an arbitrary vector z € R m the unique solution v of the quadratic program rfh)v) - (V£u¥>(u0 + Ml, t?h, (5u (Su 0 + Mi))z, tfh))z, v) —► inf | ( v , Q(u 0 + Mi)v) —> inf subject to

(18) vv e G iLj. -

.(u 0 + Mi). (uo-Mh).

With respect to the definition of the generalized Jacobian, it remains to prove that VS(u 0 + tfh) converges for d | 0 to ^J (yo )(uo). To this purpose we denote u,, = u 0 + i?h and observe that V vs(u,) 5W = = r(u,)o(-v>K,s(u,))), rK)o(-V>(u,,5(u,))),

178

M. Kocvara and J. V. Outiata.

where T(u^) is the projection operator which projects (Q(u^)) 1 d, d € E. m , onto Ly, Ju#) in the Q(u#)— metric. Due to the continuity assumptions being imposed, T as well as V yu <^(-, 5(-)) depend continuously on xij over V so that limV5(u,) = P7(yo)(u0)e55(uo) by definition.

□

R e m a r k . In the particular case J{yo) = ^(yo), the variable y j disappears and in (12) we have to require y j > 0, yj ^ 0. Analogously, in the case J(yo) = ^(yo), the whole second equation of (11) disappears and in (12) we have to require y* > 0,

rt± o. Of course, the satisfaction of the above conditions can hardly be tested in the presented general form. Fortunately, these conditions may be drastically simplified in the case, when $'(y) = — y \ i = 1,2,... ,p, arising frequently in applications. Let us delete from Q(uo) and (Vy U c^(u 0 ,yo)) r all columns, corresponding to in­ dices i 6 J(yo) a n d denote these new [m x (m — ox)] and [n x (m — oi)] matrices by Q(uo) and F(\io), respectively. Corollary 2.2 Let p < m, $'(y) = —y',i = 1,2, . . . , p , let assumption (A2) hold, Uo £ V and yo = 5(uo). Suppose that n + p > m + o2 + o 3 ,

(19)

and the \(n -f p — o) x (m — Oi)] matrix, composed from F(UQ) and the rows of Q(u 0 ) corresponding to nonactive constraints, has maximal rank, i.e. m — 0\. Then the assertion of Proposition 2.1 holds true. Proof. We observe first that if (19) holds as equality, we have to test a square matrix of order m — o%; otherwise, the number of rows is greater than the number of columns so that the maximal rank of this matrix is indeed m — o\. The rows of the matrix C(y 0 ) possess nonzero elements only on positions specified by the index of the corresponding inequality. Since y j 6 A/"(C,/(yo)), one has (yj)' = 0 for t G -/(yo) and thus it suffices to consider only the remaining components. We denote by y\ the subvector of y*z composed from (y^)'',» £ ./(yo), and observe that the condition y% G M ((Vy U (^(u 0 ,yo)) T ) reduces to y\ 6 Af(F(u0)) and the first equation of (11) reduces to the form -C.S(yo)y! + Q(»°)r3 + Cj(y0)yl

+ Cj(y 0 )y 5 * = 0.

As clearly ( - C j ( y o ) y ! + Cj(y0)y;

+ Cj(y0)y5*)* = 0 for all i ? 7(y 0 ),

Optimum Design Problems with Varia.tiona..1nequalities

179

we conclude that necessarily ( Q ( u o ) y - ; )== 00 for all i <£(y„). (Q(uo)y-;) <£(y0).

(20) (20)

Equations (20) together with condition y£ 6 A/"(F(u0)) form a homogeneous linear system, the solution of which must be zero due to the imposed rank condition. Thus the whole vector y j = 0 and we immediately infer that the linear system (11) and conditions (12) are inconsistent due to the linear independence assumption (Al), being evidently satisfied. D Condition (19) restricts the admissible number of active constraints, whose multipliers are zero. It is not too restrictive, because usually p = m and thus it reduces to n > 03 + o3. In the examples solved, n was always larger than 02 + o3 and thus the criterion of the above corollary could be applied. For the evaluation of subgradients from 30(uo) it is not necessary to compute a matrix from 5S(uo) according to Proposition 2.1. Instead of it, we can apply the idea of the adjoint program ([18]) which leads to the following assertion. Proposition 2.3 Assume that g is continuously differentiable on V x HT, assumptions (Al), (A2) hold, uo 6 V, y 0 E 5(u 0 ) and J(y0) is an arbitrary index set satisfying inclusion (10). Let the linear system (11) do not possess a solution satisfying the conditions (12) and p 0 be the (unique) solution of the adjoint quadratic program ll(p,Q(u0,)p) ( p , Q ( u 0 ) p ) - (V (Vy^u0,y0),p) y f f (u 0 ,y 0 ),p) —> inf subject to (21) (21)

pP €€ ^W 11*)Then VuS(u0,y 0 ) - ( v X u 0 , y 00 ) ) T p o 6 * » ( « . ) .

(22) (22)

Proof. According to the Jacobian Chain Rule ([2]) TT (^J(yo) (uo)) £ := V u p(u 0 ,y0) + {Pj( (uo)) Vyyff
As already mentioned in the proof of Proposition 2.1, f

r

u ^(yo)( °) = ( u °o() -°V ( -> V(Xuuoo, ,yyoo)))) .. JWH = rW

where T(u 0 ) projects (
,(uo) in the <5(u 0 )-metric.

T £ = Vu5l (u00,y0) - (VyuV (u0,y ,y0)) r(u00)V )Vy5y5(u0,y0). (u0,y0). u5 (u yu ^(u 0 )) r(u

However, r ( u 0 ) V y ^ ( u 0 , y o ) is nothing else but the solution p 0 of our adjoint program (21) and thus inclusion (22) holds true. D This way of computing subgradients has been applied in the design problems investigated in the next section.

180

3

M. Kocvara and J. V. Outrata

Two Selected Optimum Design Problems

In this section we present two examples of shape design problems. In both examples, the controlled system describes the behaviour of a membrane supported by a rigid obstacle. In the first problem we want to find such a shape of the membrane, that its surface is minimized, while it is still in contact with a given part of the obstacle. In the second problem we do not care about the surface, but we want to manage the contact between the membrane and the obstacle exclusively on that given part. However, this part can move now, together with the boundary of the membrane. The first optimum design problem known as packaging problem has been analyzed and numerically solved in [7, 8] via the above mentioned regularization technique. In the following we show that results obtained by the technique proposed in this pa­ per are substantialy different both in terms of the design variables and the objective function. The second, more complicated problem, known as incidence set identifica­ tion problem has been analyzed in [9]; however, as far as we know, it has not been numerically solved yet. We start with the description of the controlled system which is the same for both problems.

3.1

Membrane with a rigid obstacle

Let us introduce the set of admissible design variables Vu = i u € C^QO, 1]) | 0 <

Cl

< u(x2) < c2, l ^ r « ( * 2 ) | < c 3 a.e. in (0,1) 1 ,

where C\,C2,cs are given positive constants such that Uad =f= 0. Consider a family of admissible domains Q(u) with variable right "vertical" part of the boundary: Q(u) = {(*!, x2) e IR21 0 < xx < u(x2) for all x2 € (0,1)} . Denote by O = (0,c 2 ) x (0,1) the largest domain from this family. Let ip € C(Q) be the obstacle function such that ip < 0 on <9fi U ((ci,C2) x (0,1)), and K(u) = {v 6 Hg(il(u))\v > i\> a.e. in fi(«)} be the set of admissible states. For u £ t/ 0 j, the corresponding state of the controlled system is computed by solving the variational inequality: Find v = v(u) € K(u) such that (VD, V(w - u)) 0 i n ( u ) > ( / . w ~ ")o,n(u) for all w €

K(u),

V{u)

where (., .)o,n(u) stands for the scalar product in L2(il(u)) and / € L2(il(u)). In the notation of (1), A(u)v = —Av on fi(u),B(u) = £f, where £ is the canonical embedding of L2(£2) into .//"'(H); however, the convex set K is in V(u) replaced by a set-valued map K(u).

181

Optimum Design Problems with VariationaJ Inequalities

Figure 1: Discretization of fi and u. The state problem V(u) describes the deflection of a membrane fixed on the bound­ ary given by dil(u), loaded by the pressure / and supported from below by a rigid obstacle described by xp. We discretize V(u) by the finite element method in the following way. Let 0 = a0 < di < • • • < (/,) = 1 be a partition of [0,1]. The discretization of Uad is defined as follows: E^ = {«AeC([o,i])|«t|[a,_J(%]ePi, 0 < ci < uh < c 2 ,

|ufc(a,-) - « A (o,_i) CLi —


l,...,D(h)\,

di-

i.e., U^d contains piecewise linear functions from Uaj. Further, we introduce a subset Uad C TRD(h), isometrically isomorphic with U^d: Uad = {ue

R D ( / , ) | u*' = uh{ai) for some uheU^d,

i = 1 , . . . , D(h)} ,

i.e., it is the set of vectors of ii-coordinates of the nodes u ' = (u A (a,),a,),

i=

l,...,D{h).

For Uh 6 U^d we define a polygonal computational domain il(uh) = { ( n , i j ) € R 2 | 0 < X i
0<x2<

l}

and construct its triangulation T(h, uh) depending on the mesh parameter h as well as on Uh. and consisting of two parts: the fixed triangulation of a rectangle (0, co] x [0,1] with Co < cx and the moving triangulation constructed by means of principal moving nodes (design nodes) u' and associated moving nodes, ^-coordinates of which are given by an equidistant partition of the segments [co,u/,(a,)], see Fig. 1. Thus, for a fixed h > 0, the triangulation T{h,uh) depends continuously on uh. The domain fi(uh) with a given triangulation T(h,uh) will be denoted by ilh-

M. Kocvara and J. V. Outrata

182

For discretization of P(u) we use the triangulation T{h,Uh) and the set of piecewise linear basis functions (Courant basis functions). In the standard way we obtain the stiffness matrix A(u) € IR NxA ' and the right-hand side vector f(u) € R N , con­ tinuously depending on a given u € Ua(j (N = N(h) is the number of nodes of the triangulation T(h, u^)). Denote by x', i = 1 , . . . , N, the nodes of T(h,Uh) and by * ' = il>(x'), i = 1 , . . . , N. The discretized problem can be written as the quadratic programming problem l{v,A-(f(u),v)—faif subject to

v 6 Kh(u),

) >

('P(u))^

J

where u 6 \Jad and K (u) = { v e R " | v- > *«', i = 1 , . . . ,N) h

Since the triangulation T(h,Uh) depends on u/, £ Ujjd, the same holds for ^ ( u ) . In order to be able to use the direct method described in Section 2, we perform a simple transformation y = v-*(u) and replace ('P(u))/ l by the problem subject to

| ( y , A(u)y) +
y>o.

CP(u))h

J

In such a way, the values of Kk are replaced by R + and u enters only the objective oi(V{u))h.

3.2

Packaging problem

In the packaging problem we try to find such a control u* for which the contact of the membrane with the obstacle occurs in a given subset of $7, while the surface of the membrane (i.e., the measure of fi(u*)) is minimized. Let fi0 be a given closed simply connected subset of [0,co] x [0,1]. For u 6 Uai, denote by Z(u) the contact region which is the set {x S 0(u) | v(x) = ip(x)}, where v is the solution of V(u). The packaging problem is defined as follows: G(u) = meas fi(u) —► inf subject to Z{u) D n 0 , u G Uad, v solves V(u).

(P)

183

Optimum Design Problems with Variations/ Inequalities

If the set {u 6 Uai I Z{u) D H0} is nonempty, then (P) has at least one solution

([8, Thm. 6]). For the treatment of the state constraint Z(u) D fto, an exterior quadratic penalty technique has been proposed and analyzed in [7, 8]. However, as v > i\>, the direct method being applied allows us to augment this state constraint by a differentiable exact penalty. (This is impossible in the regularization technique used in [7], where the relationship v > i\> does not hold.) One obtains then an augmented objective functional GT(u,v)= meas Q(u) + r / (v-ifi)dx, Jn0 where r > 0 is the penalty parameter. Hence, instead of (P), we will solve the problem GT(u, v) —► inf

subject to (Pr)

u £ Uad,

v solves V(u). In [8, Thms. 9.3, 9.4] it is shown that for exterior quadratic penalty the penalized problem has at least one solution for any r > 0, and if r —► oo, then u r , the solutions of ( P r ) , converge uniformly to u", the solution of (P). Analogously, the same can be proved for Gr with the exact linear penalty. The discretization of ( P r ) is straightforward. Let T>0 be the set of indices of nodes lying in fi0. The discretized problem reads as follows: £ r ( u , y ) = meas Uh + — ^y' h

—► inf

i£V0

subject to

(P.) u e Uad y solves {P(u))h,

with r > 0. It is known ([8, Thm. 9.5]) that if h —> 0+ then uTh, the solutions of (Pr);,, converge uniformly to u r , the solution of (P r ). Problem (P r )/i is now exactly of the form (3). It satisfies all requirements needed by the direct approach; in particular, the appropriate function 0 is locally Lipschitz and directionally differentiable. For the evaluation of its subgradients, relations (21) and (22) can be applied which provides us with the formula V u £ r ( u , y ) - [V u (A(u)y + A ( u ) * ( u ) ) - V f ( u ) ] T p € 5 0 ( u ) , where y solves {V(u))h

(23)

and the variable p solves the adjoint quadratic program i ( p , A ( u ) p ) - ( V y £ r ( u , y ) , p ) —► inf

subject to

(24) p{ = 0

for i 6 J{y),

M. Kocvara and J. V. Outrata

184

where J ( y ) C J ( y ) C J(y). In the computations performed, we have set J(y) = I(y) during the whole it­ eration process. To be correct, one should apply the test of Corollary 2.1 at each point, where the strict complementary condition is violated. Fortunately, we have not met any computational difficulties, which shows the robustness of our approach when applied to this kind of controlled systems. Example 3.1 (see [7]): Consider the packaging problem in which fl0 = [0.25, 0.5] x [0.25, 0.75], f(xi,x2) = —1.0 and ^ ( x ^ x j ) = —0.05xi. The set Uad is specified by the parameters c\ = 0.6, c-i = 1.0, C3 = 3.0, the triangulation parameter CQ = 0.5. First we have used (as in [7]) the quadratic penalty term — - 2 ^ (y') 2 w ' t n penalty 2h .ePo 4 parameter r = 10 The problem has been computed by the NDO code BT [19]. The discretized problems (V(u))i, have been solved by a two-step algorithm introduced in [13]. The results obtained for h = ~g (D(h) = 17) are close to those of [7] at least concerning the optimal value of the objective (E°pt = 0.784213). However, the used quadratic penalty has led to considerable inaccuracies in the satisfaction of the state constraint (up to 4 % of the deflection at the front corners of f?o)- Therefore, we have solved the problem with the exact penalty. The penalty term — 52 (y1) has been used for three discretizations given by i€Z>o

^ = 8' 16' 1*2' 64' Th e P e n a lty parameters r have been chosen large enough to satisfy the state constraint exactly. Their values together with the corresponding optimal objective values E°pt are given in Table 1.

TABLE 1 D{h) 9 17 33 65

r E?* 8 • 103 0.787932 8 • 104 0.826013 8 ■ 105 0.850895 8 • 106 0.866364

The final design for D(h) — 65 is depicted in Figure 2. We see that in the set Ho the isolines of the solution follow the isolines of the obstacle (which are parallel to 12—coordinate). Comparing the values of E°vt for the quadratic and linear penalty, respectively, we see a significant difference (5% for h = -h). Also the resulting optimal design is quite sensitive to the exact satisfaction of the state constraint. This is even more evident in the next example.

Optimum Design Problems with Variationai Inequalities

185

Figure 2: Optimal design for Ex. 3.1, D(h) = 65. Example 3.2 (see [6]): Let rf>{xux7) = -0.05(iJ + (z 2 - 0.25)2) and all other data be the same as in Example 3.1. Again, the linear penalty has been used for three discretizations given by h = | , ^ , J J i . The values of the penalty parameters r and the corresponding optimal objective values E°pt are given in Table 2. TABLE 2 £>(fc) 9 17 33 65

r E°?" 1,6 ■ 104 0.780361 3 • 105 0.900842 5 • 105 0.934860 1 106 0.980475

The final design for the finest mesh {D{h) = 65) is depicted in Figure 3. Again, in do, the isolines of the solution coincide with isolines of the obstacle, which are depicted in Figure 4. The comparison of the obtained optimal design with that computed via regular ization technique and with the quadratic penalty is quite interesting in this example. When comparing the maximum components of the design vectors for the same dis­ cretization parameter h = jr, we obtain the difference of 11%, i.e., the resulting designs differ substantially.

186

M. Kocvara and J. V. Outrata

Figure 3: Optimal design for Ex. 3.2, D(h) = 65.

Figure 4: Isolines of obstacle for Ex. 3.2.

Optimum Design Problems with Variations] Inequalities

187

Note that it is necessary to use a nonsmooth code in this approach. Numerical test performed with a smooth (SQP) code failed in most cases due to line-search difficulties at a point which was far from the true solution.

3.3

I n c i d e n c e set identification

In the second design problem of incidence set identification ([8]) we do not take care about the surface of Q(u) as in the packaging problem, but we want to manage the contact between the membrane and the obstacle exclusively on n 0 . However, in contrary to the first problem, this set can move together with the moving boundary of fi(u), because now fio = {(xi,x2)

e E. x [f,S\ |wi(x 2 ) < zi
,

where 0 < 7 < 6 < 1, wj, a>2 £ C0,1([7,<$]) and have uniformly bounded derivatives a. e., and for given positive scalars e, A, C4 e < wi(x 2 ) + A < LJ2(X2) < c4,

for all x2 G [7,5].

In [8], two different objective functionals, expressing the "identification" require­ ment have been proposed. In our approach we utilize the complementarity conditions to create another suitable objective, but we introduce it only after the problem has been discretized. The discretization we start with the domain S70. Let 7 = 60 < &i < • • ■ < bo'{h) — & be a partition of [7,1$] corresponding to the partition a0 < ■ ■ ■ < ar}(h.) of [0>1]> i-e-> such that the x2—coordinates of 6, coincide with x2—coordinates of some a,-; see Figure 5. Define for a given positive c5 (specifying the upper bound for the derivatives) a new set of admissible (discretized) design variables corresponding to il0:

Kd = {"h = («!*,«») G (C([i,6]))2 \ujh\lb,_lM

G Pu

0 < e < Uik + A < u2h < c4, i = l,...,D'(h),j

< c5, h - k-l = l,2}

and for ilk = (wi/i, "2/1) € U'J^ the associated discretized set fi0fc(w/i) as fto/i(ufc) = {(xi, x2) G R x [7,S] I u u (a; 2 ) < xx < u2h(x2)} . For uh G U£d and fih = («U,W 2 A) 6 tC> the single principal moving nodes are given by couples

(ulh(bi),k),

(u/.(<2;)>a0) (u3h(bi),bi),

i= i=

l,...,D(h), l,...,D'(h),

M. Kocvara and 3. V. Outrata

188

Figure 5: Discretization of n,u,o>i and u>2. and X\—coordinates of the associated moving nodes are given by an equidistant par­ tition of segments for x'2 < 7 or xl2 > 6,

[0,u/,(a<)] [0,uih(bj)],

[uih(6j),«2k(&i)], [u2h(bj),uh(ai)]

for 7 < x*3 < 6,

see Fig. 5. Analogously to U a j , we introduce still a set ~Vad by

V a „ = {u € R°(fc)+«'(M I u .

= Uh{a.):

uD
w

'

w

£ = ! , . . . , D(fc), /y(A),

= «»(*), i = l , . . . , t f ( A )

for some u h 6 C&, («u, u2A) 6 U*dj , i.e., V a j contains vectors of ii—coordinates of all principal moving nodes. For the construction of the objective we utilize the fact that if y' > 0 at some node in (T'(u))/,, then the coordinate A' of the appropriate (unique) Kuhn-Tucker vector must be zero. As A = A(u)y + A ( u ) t f ( u ) - f ( u ) ,

189

Optimum Design Problems with Varia.tiona.1 Inequalities we may employ the objective £ (A(u)(y + * ( u ) ) - f ( u ) ) \ where V\ = {1,2,...,

N}\

2>a. Thus, the discretized problem of identification of the incidence set can be formu­ lated as *v(u,y)= E (A(u)(y+*(u)-f(u))' + - [ subject to u G V„ d , ^ y solves {V(u))h,

?

£yi^mf

' (P'r)*

where r > 0 is the appropriate penalty parameter. Of course, even if E'r = 0, "semiactive" contacts with zero multipliers may occur; however, this undesirable phenomenon has not been observed in computations. Problem (P'r)h may again be solved numerically by using of the direct method and a suitable NDO routine. In this case, however, the computation of subgradients according to (21), (22) is slightly more complicated than in the packaging problem, because the evaluation of V u £ ^ , VyJE^ is nontrivial and the dependence of A, f on the design variable is more complex. Example 3.3. Consider the problem of identification of the incidence set where f(xi,x2) = —1.0 and i>{xi, 12) = —0.03. The sets Uad, U'Jj are specified by parameters c, = 0.7, c2 = 1.2, c3 = 2.5, 7 = 0.25, S = 0.75, e = 0.15, A = 0.05, c4 = 0.65. The proper choice of the (linear) penalty parameter r is more difficult than in the obstacle problem, because both terms in the objective functional E'r are of the same nature and thus r determines a scaling between them. For r = 33, h = yg and h = ^ , the final values of the objective functional are E'ropt = 0 and £^ p< = 0.395618 • 10" 4 , respectively. In Figure 6 we see the initial design of $7 and fi0 and the corresponding isolines of the solution. Figure 7 shows the optimal design for h = ^ ; the boundary of fl0 in fact coincides with the isoline —0.03. Finally, Figure 8 shows a 3D view of the solution and the obstacle with changed scaling in the vertical axis. We see that the problem constraints are satisfactorily satisfied. The obtained results could not be compared with any other ones, because in [9] there is no attempt to solve the problem numerically.

4

Conclusion

The direct method proposed in [18] and further developed in this paper proved to be an effective tool for the numerical solution of the considered shape optimization problems. It may be recommended whenever the number of design variables is small with respect to the number of state variables and a 'high' accuracy of the results is required. Another applications of this technique are reported in [11, 12].

190

M. Kocvara and J. V. Outrata.

Figure 6: Initial design for Ex. 3.3, D(h) = 33.

Figure 7: Optimal design for Ex. 3.3, D{h) = 33.

Optimum Design Problems with Variational Inequalities

191

Figure 8: Optimal state solution for Ex. 3.3, D(h) = 33.

References [1] J. P. Aubin and I. Ekeland, Applied Nonlinear Analysis, J. Wiley & Sons, New York, 1984. [2] F. H. Clarke, Optimization and Nonsmooth Analysis, J. Wiley & Sons, New York, 1983. [3] B. Cornet and G. Laroque, Lipschitz properties of solutions in mathematical programming, Journal of Optimization Theory and Applications 53 (1987) 407427. [4] A. V. Fiacco, Sensitivity analysis for nonlinear programming using penalty meth­ ods, Mathematical Programming 10 (1976) 287-311. [5] T. L. Friesz, R. L. Tobin, H.-J. Cho and N.J. Mehta, Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality con­ straints, Mathematical Programming 48 (1990) 265-284. [6] P. T. Harker and S. C. Choi, A penalty function approach for mathematical programs with variational inequality constraints, WP 87-09-08, Dep. Dec. Sci., Univ. of Pennsylvania, 1987.

192

M. Kocvara and J. V. Outrata

[7] J. Haslinger and P. Neittaanmaki, On the design of the optimal covering of an obstacle, in: Lecture Notes in Control Inf. Sci. 199, Springer-Verlag, Berlin, (1988) 192-209. [8] J. Haslinger and P. Neittaanmaki, Finite Element Approximaiion for Optimal Shape Design: Theory and Applications, J. Wiley & Sons, Chichester, 1988. [9] K.-H. Hoffmann and J. Haslinger, On the identification of incidence set for elliptic free boundary value problems, DFG Research Report No. 174, Augsburg, 1989. [10] K. Jitorntrum, Solution point differentiability without strict complementarity in nonlinear programming, Mathemaiical Programming Study 21 (1984) 127-138. [11] M. Kocvara and J. V. Outrata, Shape optimization of elasto-plastic bodies governed by variational inequalities, in: J.-P Zolesio, editor, Boundary Control and Variation, Lecture Notes in Pure and Applied Mathematics 163, pages 261271. Marcel Dekker, 1994. [12] M. Kocvara and J. V. Outrata, A numerical approach to the design of masonry structures, in: Proceedings 16th IFIP Conf. on System Modelling and Optimization, Compiegne, July 5-9, 1993 (to appear). [13] M. Kocvara and J. Zowe, An iterative two-step algorithm for linear complementarity problems, Numerische Mathematik 68 (1994) 95-106. [14] J. Kyparisis, Sensitivity analysis for nonlinear programs and variational inequalities with nonunique multipliers, Mathemaiics of Operations Research 15 (1990) 286-298. [15] P. Loridan and J. A. Morgan, Theoretical approximation scheme for Stackelberg problems, Journal of Optimization Theory and Applications 61 (1989) 95-110. [16] O. L. Mangasarian, Nonlinear Programming, McGraw Hill, New York, 1969. [17] M. Makelaand P. Neittaanmaki, Nonsmooth Optimization, World Scientific, Singapore, 1992. [18] J. V. Outrata, On the numerical solution of a class of Stackelberg problems, Zeitschrift fur Operations Research 34 (1990) 255-277. [19] H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM Journal on Optimization 2 (1992) 121-152. [20] H. von Stackelberg, The Theory of Market Economy, Oxford University Press, Oxford, 1952.

Monotonicity

and

Quasimonotonicity

193

Recent Advances in Nonsmooth Optimization, pp. 193-214 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

Monotonicity and Quasimonotonicity in Nonsmooth Analysis 12 Sandor Komlosi Faculty of Economics, Janus Pannonius H-7621, Rdkoczi ut 80, Pecs, Hungary

University

Abstract

The role of the monotonicity concept for linear operators, bifunctions and multifunctions in several branches of Mathematics such as Functional Analysis, Nonlinear Analysis, Optimization Theory is rather well known. Quite recently the notion of monotonicity has been generalized by different authors. The aim of the present paper is to give some recent contributions to the theory of gen­ eralized monotonicity in a unified way incorporating results for a wide range of generalized derivatives and subdifferentials.

1

Introduction

T h e role of t h e monotonicity concept for linear operators, bifunctions and multifunctions in several branches of M a t h e m a t i c s such as Functional Analysis, Nonlinear Analysis, O p t i m i z a t i o n Theory and its relationships with convexity are rather well known [1,2,8,30,35,36]. For an instance we mention only two well known theorems from Convex Analysis: (i) a directionally differentiable lower semicontinuous function is convex if and only if its directional derivative is a m o n o t o n e bifunction; (ii) a lower 'This paper is the written version of the invited lecture delivered by the author on "Workshop on Nonsmooth Analysis and its Applications" (Banach Center, Warsawa, May 3-14, 1993) and which was completed in October 1993, during the author's stay at the Department of Mathematics, University of Pisa. I take the opportunity of thanking Professor Franco Giannessi and Professor Massimo Pappalardo for their warm hospitality. 2 Partially supported by the Hungarian National Scientific Research Foundation (Grant No. T013967).

S. Komlosi

194

semicontinuous function is convex if and only if its convex subdifferential is a nonvoid monotone multifunction [30,33]. Since it has been well known that the convexity assumption on the function can be weakened to certain kind of generalized convexity assumption without "destroying" the nice results valid for the convex case, therefore there has recently been similar attempts to weaken the monotonicity assumption to some kinds of generalized monotonicity concept. In 1976 Karamardian introduced a concept of pseudomonotonicity for gradient maps [16]. Some years later, in 1983, Hassouni introduced the notion of quasimonotonicity for multifunctions [14]. The paper of Karamardian and Schaible [17] from 1990, where several kinds of generalized monotonicity were introduced and studied for gradient maps, might be considered as the one opening a new theory, the theory of generalized monotonicity. These concepts were extended to nondifferentiable functions (for generalized derivatives and subdifferential maps) by Komlosi [19-25] and Luc [27,28] and for Equilibrium Problems by Blum and Oettli [2], Further remarkable results on this topic can be found in [3,4,5,9,10,12,15,31,36,37]. The aim of the present paper is to give some recent contributions to the theory of generalized monotonicity in a unified way incorporating results for a wide range of generalized derivatives and subdifferentials. The paper is organized as follows: Chapter 2 gives a short overlook to monotonic­ ity concepts proved to be useful in several branches of optimization theory and related topics. Chapter 3 is devoted to the introduction of different generalized monotonicity concepts for bifunctions (generalized derivatives) and the study of their interrelations with certain kinds of generalized convexity. In Chapter 4 we show how monotonicity can be characterized via quasimonotonicity. These results are applied in Chapter 5, where quasimonotonicity - quasiconvexity results are proved applying suitable mean value theorems, due to Diewert and Zagrodny, respectively. Chapter 6 is devoted to the generalized monotonicity of multifunctions, for which different characteriza­ tions are given. For special subdifferentials generalized monotonicity is linked with generalized monotonicity of the generalized derivatives associated with them.

2

Monotonicity Concepts in Nondifferentiable Optimization

Let X, X* and (■, •) denote, respectively, a real Banach space, its topological dual and the canonical bilinear form on X* x X throughout this paper. The following models present the most favourable classes of optimization theory and related fields. Mathematical Programming Problem (MPP): minimize / ( x ) x £ C, C CX,

Monotonicity and

Quasimonotonicity

195

where the function / is, / : C —► R. Complementarity

Problem (CP): find x £ l such that xGC,

F ( X ) G C * and

(F(x),x)

= Q,

where C C X is a given convex cone, C" C X' is the dual cone to C and F is a given function, F : C —» X' Variational Inequality Problem (VIP): find x a X and y € X* such that x G C, y 6 T(x) and (y,z - x) > 0 for all z 6 C, where C c l and T is a multifunction T : C ^

X*.

Equilibrium problem (EP): find x £ . Y such that / ( x , y ) > 0 for all y € C, where C C X and f : C x C ^ R with / ( z , z) = 0 for all z G C There are interesting interrelations between these classes of problems, namely (MPP) can be formulated as (CP), (CP) can be given in the form of (VIP) and all of them may have the form of (EP). More details on these interrelations can be found in [2,8,37]. It is well known that in existence proofs for (MPP) the convexity of the objective function / ( x ) is a celebrated property, whereas for the other problems (CP), (VIP) and (EP) the monotonicity of the functions F(x), / ( x , y) and the multifunction T(x) guarantees the existence of solutions and supports algorithms computing them. For the sake of convenience let us recall the definitions of monotonicity for the different cases considered. a.) F:C ^X", C CX, (F(y)-F(x),y-x)>0 b)T:C

-> X*, C

for all

x,y€C

(1)

CX,

< r ( y ) - r ( x ) , y - x ) C R+

for all

x,y<EC.

(2)

Here ( r ( z ) , u ) denotes the set {(z*,u) | z* G T(z) } and R+ denotes the set of nonnegative reals. c) / : C x C -> R, with / ( z , z) = 0 for all z G C, /(x,y) + / ( y , x ) < 0

for all

x,yGC.

(3)

S. Komlosi

196

The interrelations between monotonicity and convexity are well known, moreover behind both properties there are well developed theories: Convex Analysis, Minty's Theory [35]. By a classical result, the monotonicity of the directional derivative / ' ( x , d) com­ pletely characterizes the convexity of the given function / ( x ) . Recently similar char­ acterizations were obtained in terms of some other kinds of generalized derivatives such as Clarke-, Rockafellar- and Dini derivatives [6,22,26].

3

Generalized Monotonicity for Bifunctions

Generalized derivatives might be considered in a unified way as a bifunction h(x,d) with finite or infinite real values, where x refers to a given point of a given subset C from X and d refers to a given direction of X. Since the domain for d is always the whole space X, therefore it is sufficient to specify the domain of x only and so, for the sake of brevity, we will say that /i(x, d) is a bifunction defined on C. Let us begin with introducing generalized monotonicity concepts for generalized derivatives proved to be useful for nondifferentiable functions [19]. Definition 3.1 Let /i(x,d) be a bifunction defined on the convex set C. h(x,d) is called monotone, strictly monotone, quasimonotone, pseudomonotone, strictly pseudomonotone on C, if for every y , z 6 C, y / z, condition (M), (SM), (QM), (PM), (SPM) holds, respectively: (M)

h(y,z-y)

+

h(z,y-z)<0,

(SM)

h{y, z - y) + h(x, y - z) < 0 ,

(QM)

h(y,z-y)>0

implies

h(z,y - z) < 0 ,

(PM)

h(y,z-y)>0

implies

/j(z,y-z)<0,

(SPM)

h(y,z-y)>0

implies

h(z,y - z) < 0

Remark. In the definitions of (M) and (SM) we adopt the following rule: (+oo) + (-oo) = 0 . The following interrelations are immediate consequences of the above definitions. (SM) => (M) => (PM) => (QM)

Monotonicity and

197

Quasimonotonicity

and (SM) =► {SPM) => (J°M) => (QM). Remark. If / ( x ) is differentiable with gradient map F(x) = / ' ( x ) , then the monotonicity concept (1) for F(x) coincides with (M) if we apply it for h(x,d) = ( F ( x ) , d ) . It should be mentioned that for this choice of h(x,d) the other kinds of generalized monotonicity concepts gives just the ones introduced by Karamardian and Schaible [17]. If ft(x,d) is a generalized gradient, then (M) is equivalent to (3) with / ( x , y) = h(x, y - x). One of the most useful applications of the generalized monotonicity concepts is that these properties can be related to appropriate kinds of generalized convexity [15,17,20,23,27, 28]. To proceed this way let us recall first some definitions. Definition 3.2 Let the function / ( x ) and the bifunction h(x, d) be defined on the convex set C C X. / ( x ) is called convex, strictly convex, quasiconvex, h-quasiconvex, h-pseudoconvex or h-strictly pseudoconvex on C, if conditions (CX), (SCX), (QCX), (h-QCX), (h-PCX) or (h-SPCX) hold, respectively: (CX): for all x , y 6 C and t g [0,1] one has

/(tx+(l-i)y)<*/(x) + (l-i)/(y), (SCX): for all x , y € C, x / y and t 6 (0,1) one has

(*x+(l-t)y)
/(ix+(l-*)y)<max{/(x),/(y)}, (h-QCX): for all x,ye

C,

/(x) < /(y) (h-PCX): for all x,y

implies

ft(y,x-y)<0,

implies

h{y, x - y) < 0 ,

implies

h(y,x-

(EC, /(x) < /(y)

(h-SPCX): for all x , y € C, x ^ y, /(x) < /(y)

y) < 0 .

Remark. The above definitions can be applied for function / ( x ) and bifunction /i(x, d) with 'extended' real values, as well. The following interrelations are immediate consequences of the definitions: (SCX) => (CX) => (QCX),

198

S. Komlosi ( h - S P C X ) => ( h - P C X ) =*• ( h - Q C X )

In the sequel we shall focus our attention to some special kinds of generalized derivatives of a given function / ( x ) at a, whose definitions are given below using the following notations [13]: ^ . (z, a) -> (a, /(a)) and ( z ) ,, and a > ((z,z ,Qa)) || a < (z,a)->(a,/(a)) > //(z) ( z , a ) ||aa< ! -*=*= ) - (z,a) -» ((a, a , //(a)) ( a ) ) and and a < //(z) (z) . (z,a) (z,a)-> Dini derivatives (upper and lower):

/(a ,Di A\ r / ( a + id)f d ) -/(a) - / (; a ) D / (a,d) (a, d) ::= hmsup —, = limsup (—0+ (—0+ ti /o(a,d) := liminf

/(a + id) - /(a) t

1

Dini-Hadamard derivatives (upper and lower): /

— -/(a) ,

(a, d) = hm sup

"-To*? & a /00 H(a,d) liminf^ H ( a , d ) = ]imini^ u-»d

+ tU U +

^ ' ~^ ^ ; t

Clarke derivatives (upper and lower): rC/ tCi J \ if(z + td) - a f (a,d) = hmsup , (z, 0 )|a

/ C ( a , d ) = liminf / ' ( Z 1-.0+

+ M )

~

a

;

t

Rockafellar derivatives: z+ / H" ( a , d ) = = l limsup i m s u p inf -^^Z + **U")) -—-- ,,

(z,o)la / n ( a , d ) = liminf sup / ( z + * " ) - < * . weaA; Rockafellar derivatives: a u f *(a,d) = + **U) ) ~~ / ( aa ) _, = limsup u infd / ((& +

i_o+

—

'

Monotonicity and

Quasimonotonicity

199

t i A\ v • t /(a + *u)-/(a) fwR(a,d) = liminf sup — -^-^ . Remark. The "limsup inf" and "liminf sup" operations were introduced by Rockafellar [34,35]. The meaninig of limsup inf (_0+ (z.o)la

u

—d

operation, for istance, is the following sup lim sup e>0

inf

(^o+ l l u - d l l < £ (z,o)ia

The meaning of the other operations used above are similar. The following theorem provides the relationships between these derivatives ac­ cording to the partial order "<", the proof of which can be found in [13]. Lemma 3.3 For all x G C and d 6 X one has /5(x,d) I V /c(x,d) |V /*(x,d)

> > >

/D"(x,d) I v /D(x,d) |V rfi(x,d)

> > >

fwR(x,d) |v /D(x,d) |V /0ff(x,d)

> > >

/„(x,d) | V /c(x,d) |V //(X,d)

where the "unnamed" derivatives / s ( x , d ) and / / ( x , d ) are defined as follows: fSi J\ r / ( z + ru) - a / (a,d) = limsup , u-d (z,a)la //(a, d) = liminf—1 (-.0+ u^d (z,a)Ta

t

Remark. It should be mentioned that for lower semicontinuous functions the convergence (z, a) J. a is equivalent to the simpler convergence z —*j a, whose meaning is: z - > , a <=$■ ( z , / ( z ) ) - > ( a , / ( a ) ) , and in this case a can be replaced with /(z) in the different quotient. Taking into account the above relationships the following "majoring criterion'' might be very useful.

S.

200

L e m m a 3 . 4 [23] Let the bifunctions h(x, d) andg(x, Assume that for all x € C and d £ X g(x,d)

< h(x,d)

Komldsi

d) be defined on the set C C

X.

.

Ifh(x,d) is (strictly) monotone, quasimonotone or (strictly) pseudomonotone on C, then g{x,d) is (strictly) monotone, quasimonotone or (strictly) pseudomonotone on C, respectively, as well. T h e proof is quite simple and thus o m i t t e d . T h e following two theorems provide a base in studying the links between general­ ized convexity and generalized monotonicity of different kinds of generalized deriva­ tives. T h e o r e m 3 . 5 Let f(x) be radially lower semicontinuous on the convex set C and let either h(x,d) = / D ( X , d ) or h(x,d) = / D ( x , d ) . Then each of the following statements are true: (i) f(x) is convex on C iff h(x,d) is m o n o t o n e on C, (?*) / ( x ) is strictly convex on C iff h(x, d) is strictly m o n o t o n e on C, (ii) / ( x ) is quasiconvex on C iff h(x,d) is quasimonotone on C, (Hi) / ( x ) is (strictly) h-pseudoconvex on C iff h(x,d) is (strictly) pseudomono­ tone on C. T h e proof of (i) and (i") can be found in the papers [22, 26]. S t a t e m e n t (ii) was proved in [19,20,27], whereas the proof of (Hi) was given in [23]. T h e o r e m 3.6 Let f(x) be lower semicontinuous on the open convex set C C Then each of the following statements are true. (i) f(x) is convex on C iff fR(x,d) is monotone on C, (ii) f(x) is quasiconvex on C iff fR(x,d) is quasimonotone on C,

X.

T h e proof of (i) of the above theorem was given in [26], whereas s t a t e m e n t (ii) was proved in [27]. T h e following result is an i m m e d i a t e consequence of Theorem 3.5 and L e m m a 3.3. T h e o r e m 3 . 7 Let f(x) be radially lower semicontinuous have for all x G C and d G X

on the convex set C and

fD(x,d)
Monotonicity and

Quasimonotonicity

201

Remark. The above theorem can be applied for any members of the following collection: /S(x,d)

>

|v

/C(x,d)

fDH(x,d)

>

/„ H (x,d)

>

/D(x,d)

|v

>

|v

fD(x,d)

From Theorem 3.6 and Lemma 3.3 one can infer the following statement. Theorem 3.8 Let f(x) be lower semicontinuous on the open convex set C and let us have for all x £ C and d 6 X fR(x,d)/c(x,d)>/*(x,d). This result can be sharpened by applying the following general assertion. Lemma 3.9 Let the bifunction h(x, d) be defined on the open set C. Set g(x, d) = limsup inf h(z,u) z—.x

(4)

a—>d

Then (i) the monotonicity of h(x, d) on C implies the monotonicity of g(x, d) on C, (ii) the quasimonotonicity ofh(x,d) on C implies the quasimonotonicity ofg(x,d) on C. Proof. First we prove assertion (ii). Suppose that h(x,d) is quasimonotone on C and assume for contradiction that 0

and

ff(y,x-y)>0.

Due to (4) it follows that there exist x ' , y ' 6 C such that h{x', y' - x') > 0

and

h(y', x - y') > 0 ,

which contradicts to the quasimonotonicity of h(x,d). applied for proving (i). ■

The same reasoning can be

Since for lower semicontinuous functions we have fDH(x,d)

< fR(x,d)

< limsup inf / D W ( z , u ) , z->x

u-»d

(see [39]) therefore, by Lemmas 3.3 and 3.9, we arrived to the following result:

S. Komlosi

202

Theorem 3.10 Let f(x) be lower semicontionuous on the open set C. Then the following statements are true: (i) /£>tf(x,d) is monotone on C iff J " ( x , d ) is monotone on C, (") /Dw(x,d) is quasimonotone on C iff fR(x,d) is quasimonotone on C. Taking into account the above result, Theorem 3.8 can be sharpened as follows. Theorem 3.11 Let / ( x ) be lower semicontinuous on the open convex set C and let us have for all x G C and d 6 X

/zur(x,d)
> >

/D"(x,d) |V fD(x,d) R |V

> >

/„«(x,d) |V /D(x,d) | V

/*(x,d) > r (x,d) > fDff(x,d) 4

Characterizing Monotonicity in Terms of Quasimonotonicity

It is worth mentioning that the proofs for convexity-monotonicity and quasiconvexity-quasimonotonicity interrelations have been elaborated so far independently from each other in both of the cases of Theorems 3.5 and 3.6 (see [22,26,27]). What is rather surprising, due to the following two lemmas, convexity-mono­ tonicity statements can, however, be proved by applying quasiconvexity-quasimonotonicity results directly. Lemma 4.1 The function f(x) is convex on the convex set C C X iff the function F(x) = / ( x ) + (g,x> is quasiconvex on C, for all g 6 X'. Proof. Necessity: Obvious, since the sum of a convex and linear function is always convex.

Monotonicity and

Quasimonotonicity

203

Sufficiency: Assume that F(x) = / ( x ) + (g, x) is quasiconvex on C for all g £ l ' . Suppose for contradiction that / ( x ) fails to be convex on C. It means that there exist two distinct points x, y from C and a third point z = tx + (1 — i)y from the open line segment (x, y) such that i / ( x ) + (1 - t)f(y)

< /(z) .

By virtue of the Hahn-Banach Extension Theorem you can always find an appropriate g* € X' such that F'(x) = F'(y) < F*(z) , where F*(x) = / ( x ) + (g*,x). The above conditions, however, contradict to the quasiconvexity of F'(x). This contradiction proves the thesis. ■ Lemma 4.2 The bifunction h(x,d) tf(x,d)

is monotone on C iff the bifunction = /*(x,d) +
is quasimonotone on C for all g 6 X' Proof. Necessity: Assume that h(x,d) is monotone on C. arbitrary and set H(x,d) = h(x,d) + (g,d). Since

Let g G X" be

H(x, y - x) + H(y, x - y) = h(x, y - x) + h(y, x - y ) , therefore H(x, d) is also monotone and thus quasimonotone on C, as well. Sufficiency: Let H(x, d) be quasimonotone on C for all g € X* Since 0 6 X* therefore it follows that h(x, d) is quasimonotone on C, as well. Assume for contradiction that /i(x, d) fails to be monotone. It means that there exist two distinct points x and y in C such that /t(x,y-x) + / i ( y , x - y ) > 0 .

(5)

Without loss of the generality we may assume that ft(x,y-x)

> 0.

From the quasimonotonicity of h(x, d) it follows, that h(y, x — y) < 0. Taking into account inequality (5) we get 0 < -fe(y,x-y) <

h(x,y-x).

In virtue of the Hahn-Banach Extension Theorem you can always find a g* £ X' such that -h(y,x-y) < ( g * , x - y ) < h{x,y-x) . If you consider H*(x, d) = h(x,d) + (g",d) then the above inequalities yield H"(x,y-x)>0

and

H'{y,x

which contradicts to the assumption that H'(x,d) contradiction proves the thesis. ■

- y) > 0 ,

is quasimonotone on C.

Applications of the above lemmas will be given in the next chapter.

This

S. Komlosi

204

5

Two Mean Value Theorems

First we present a proof for statement (ii) of Theorem 3.5. Then, by applying Lemmas 4.1 and 4.2, we get statement (i) of the same theorem. To proceed this way we need the following mean value theorem due to Diewert. [11, Theorem 1, Corollary 1]. Theorem 5.1 Diewert's Mean Value Theorem. Let the function / ( x ) be defined on the line segment [y,z] and assume the values f(y), / ( z ) to be finite. Let s(t) = /(y + *(z — y)) be lower semicontinuous on [0,1]. Then there exists to £ [0,1) such that

/D(xo,z-y)>/(z)-/(y), where x 0 = y + t0(z — y). Proposition 5.2 Let / ( x ) be radially lower semicontinuous on the convex set C. Then / ( x ) is quasiconvex on C, iff any of the following conditions holds: (0 / D ( x i d ) is quasimonotone on C, (ii) fD(x,d) is quasimonotone on C. Proof, (i): Necessity. Assume that / ( x ) is quasiconvex on the convex set C and /D(x,y-x)>0,

(6)

where x, y are arbitrary elements from C. Our task now is to prove that /o(yi x—y) < 0. It is easy to verify that the following implication is true for / ( x ) on C [11]: u , v € C , / ( u ) < / ( v ) =► / D ( v , u - v ) < 0

(7)

From (6) / ( x ) < / ( y ) follows, which, together with (7) gives / o ( y , x — y) < 0. Sufficiency. The proof given here is a slightly modified version of the one given by Luc in [27], Let /£>(x,d) be quasimonotone on C. For contradiction suppose that / ( x ) fails to be quasiconvex. Then it means that there exist a line segment [a, b ] c C and a point z on it, z 6 (a, b), such that /(z)>max{/(a),/(b)} Due to the quasimonotonicity of / D ( X , d) we may assume that / ( z ) is finite. Assume for contradiction that /(z) = -foo for all z S (a, b). Then we have / n ( a , b — a) = /£>(b, a — b) = +oo, which contradicts to the quasimonotonicity of / D ( X , d) on C. Since / ( a ) , / ( b ) and / ( z ) are all finite, therefore there exist, by Diewert's Mean Value Theorem, u G [a, z) and w G [b, z) satisfying conditions /D(u,z-a)>/(z)-/(a)>0 and /o(w,z-b)>/(z)-/(b)>0.

Monotonicity and

Quasimonotonicity

205

Taking into account the positive homogenity of the Dini derivative with respect to its direction argument, the last two inequalities provide the following ones: /D(U,W-U)>0

and

/ D ( W , U - w) > 0 ,

contradicting the quasimonotonicity assumption. This contradiction proves statement (i) of the present theorem. Since / D ( x , d ) > /£>(x,d), therefore statement (ii) follows immediately from (i) above and Lemma 3.4. ■ Now we present a proof for statement (ii) of Theorem 3.6 capturing the essence but simplifying the details of the original one [27]. Then, by applying Lemmas 4.1 and 4.2, we get statement (i) of the same theorem. The same approach can be found in [41]. Let us consider now the generalized derivative fR(a, d), with 'extended' real val­ ues, and the subdifferential 6Rf(a), possibly empty, associated with it (in the sense of Definition 6.1) as follows: **/"(*) = { g € X' | (g, d) < / " ( a ; d) for all d g X } The basic tool in proving the above claim is the following approximate mean value theorem due to Zagrodny [38,Theorem 4.3]. Theorem 5.3 Zagrodny's Mean Value Theorem. Let / ( x ) be a proper lower semicontinuous function defined on an arbitrary Banach space X. Let f(x) assume finite values at a, b € X. Then there exist a point z £ [a, b) and two sequences {z^}, Zjt G X and {gk}, g* € SRf(zk) such that l i m Zjt = z , k—*+oo

liminf(gfc,b-z,)>^^||b-z||,

(8)

liminf(gt,b-a)>/(b)-/(a).

(9)

k—*+oo

The following corollary to this theorem, which allows us to replace b in (8) with any element from the half ray y = a 4- t(h — a) 6 C, t > 1, will be of direct use in the sequel. This lemma was proved in [27] in a rather complicated way. Here we present a quite simple proof for it. Lemma 5.4 Let C be an open convex subset of a Banach space X and / ( x ) be a proper lower semicontinuous function defined on C. Let / ( x ) assume finite values at a, b € C. Then there exist a point z G [a, b) and two sequences {z*}, z* € C and {gfc}, gfc € SRf{zk) such that lim Zk = z , k—*+oo

S. Komlosi

206 and for any y = a + <(b — a) € C, t > 1 we have liminf(g,,y-z,>>Z^5M||y-z||.

Proof. We shall prove that the series {z*} and {g^} from Theorem 5.3 meet the requirements of the present lemma. Since the set C is open, therefore we may assume without loss of the generality that zk € C for all k. Let us denote ( / ( b ) — / ( a ) J / | | b — a|| by the simpler symbol K. Observe that y - z* = (y - b) + (b - zk) = a ( b - a) + (b - zk) . with a = |(y - b||/||b - a||. It follows that (g*,y-z*> = a ( g i , b - a ) + (gA,b-zfc) . Taking into account the superadditivity of the liminf operation, the definitions of scalars K and a and applying (8) and (9) one can deduce that l i m i n f ( g t , y - z / t ) > liminfa(g k ,b - a) + liminf(g t ,b - zk) > k—*+oo

k—*+oo

k—»+oo

> ^ ( | | y - b | | + ||b-z||) = A'||y-z|| and it was to be proved. ■ Now we are ready to prove the following theorem. Proposition 5.5 Let C be an open convex subset of a Banach space X and / ( x ) be a proper lower semicontinuous function defined on C. Then / ( x ) is quasiconvex on C, iff the Rockafellar derivative fR(x,d) is quasimonotone on C. Proof. Necessity: For the proof we refer to [27]. Sufficiency: Let fR(x,d) be quasimonotone on C. Assume for contradiction that / ( x ) fails to be quasiconvex on C. It follows that there exist two points a, b 6 C with finite values / ( a ) and / ( b ) and a third point c on the open line segment (a,b) such that we have /(c)>max{/(a),/(b)}. (10) Without loss of the generality we may assume that /(c) is finite, as well. (If / ( c ) = +oo, then redefine / ( x ) only at x = c in such a way that (10) fulfil and we will arrive to the same conclusion.) Apply first Lemma 5.4, the corollary to Zagrodny's Mean Value Theorem for the line segment [a, c]. It follows the existence of a point z G [a,c) and two sequences {z/t}, zi 6 C and {gt}, gk G 6Rf(zk) satisfying the following conditions: lim Z/t = z ,

207

Monotonicity a n d Quasimonotonicity

and l i m i n f ( g , , b - zk) > M

ip~\\b

- z|| > 0 .

( T h e last inequality is a consequence of (10).) It follows t h a t for sufficiently large k one has (gt,b-zfc)>0.

(11)

Since z / c, therefore t h e sequence {<:*}, where c* denotes t h e projection of c to the closed line segment [zk, b] a d m i t s t h e following properties: ck 6 C

and

{cit} —> c,

cfc G ( z t , b ) , as

k —> + o o .

Since / ( c ) > / ( b ) and / ( x ) is lower semicontinuous, therefore for sufficiently large k /(e») > / ( b ) .

(12)

Let k b e arbitrary. Apply now L e m m a 5.4 to t h e line segment [cfc,b]. It follows t h e existence of a point wj. 6 [ c t , b ) and two sequences {w^,}, w ^ 6 C and {gw}, git, 6 SRf(wki) satisfying t h e following conditions: lim wfc, = Wfe , 1—* + co

and lim i n f ( g h , z t - w t . ) > ^ ~ { j , b ) ||zt - w t | | > 0 (13) ■^+oo ||ct - b|| ( T h e last inequality is a consequence of (12).) Let it b e sufficiently large satisfying (11) and (12). Due to the definition of w^ it is obvious t h a t (11) is equivalent to (gt,w/fc-zt) > 0 .

(14)

According t o (13) a n d (14) you can choose for this k a sufficiently large index i such that (g/ki,Zfc - w f c l ) > 0 and (gfe.Wfci - zk) > 0 hold. Set X! = w t , 6 C and x 2 = z* € C. Since / f l ( X i , X 2 - X i ) > (gjfci, Zfc - Wjti) > 0 and / f l ( X 2 , X ! - x 2 ) > (g*,Wfc -Zfc) > 0 , therefore these inequalities contradict to the quasimonotonicity of fR(x,d). contradiction proves t h e s t a t e m e n t of the above theorem. ■

This

S. Komlosi

208

6

Generalized Monotonicity for Mult if unctions

Subdifferentials, playing a very important role in Nonlinear Analysis and related fields, are useful dual objects of geometric character for generalized derivatives. Let / ( x ) be a function defined on X and let a £ X. The convex subdifferential of / ( x ) at a is defined as follows: */(*) := { 8 G X' | 0

implies

(v,x-y)<0,

(15)

Monotonicity and

Quasimonotonicity

209

(ii) pseudomonotone on C if for every x , y 6 C and u £ T(x), v £ T(y) one has (u,y-x)>0

implies

(v,x-y)<0,

(16)

(Hi) strictly pseudomonotone on C if for every x , y £ C, x / y and u € T(x), € T(y) one has

v

(u,y-x)>0

implies

(v,x-y)<0.

(17)

The following interrelations are immediate consequences of the definitions above. monotonicity =$■ pseudomonotonicity =4- quasimonotonicity and strict pseudomonotonicity =>• pseudomonotonicity . Amongst the subdifferential maps Sh(x) you can find a favourable class which is characterized by the following property: for each a £ C, h(a, ■) is the support function of Sh(a). In other words it means that A(a, ■) is a, positively homogeneous sublinear function and for all d G X we have fc(a,d) = sup{(d,g) |ge<5/i(a)} . Michel-Penot-, Clarke-, Rockafellar subdifferentials belong to the above class. The Michel-Penot directional derivative is defined as follows: fUp,

,i ,/ ( a + tz + i d ) - / ( a + fz) (a, d) = suphmsup , zex f-.o+ t and has some remarkable properties, namely it is a lower semicontinuous convex function of d and for all a, d £ X, we have /

/o(a,d) < /D(a,d) < /MP(a,d) < /c(a,d) The following theorem demonstrates that the generalized monotonicity concepts for bifunctions and multifunctions fit well to each other, moreover shows the way for transforming the results of the previous parts for subdifferentials possessing support function. (For the proof consult [22].) Theorem 6.3 Let 6h(x) be a subdifferential map defined on the convex set C with support function h(x,d). Then 6h(x) is monotone, quasimonotone, (strictly) pseu­ domonotone on C if and only if its support function h(x, d) is a monotone, quasimonotone, (strictly) pseudomonotone bifunction on C, respectively.

S. Komlosi

210

Let us consider now the generalized derivative fR(&, d) and the subdifferential S f(a) associated with it in the sense of Definition 6.1: R

**/(*) = { g € X' | (g,d) < / f i ( a , d ) for all d g X } . It is well known [34] that fR(&, ■) is the support function of 6Rf(a). By combining Theorem 6.3 and Proposition 5.5 we obtain the following theorem. Theorem 6.4 Let C be an open convex subset of a Banach space X and / ( x ) be a proper lower semicontinuous function defined on C. Then / ( x ) is quasiconvex on C iff the Rockafellar subdifferential 6Rf(x) is quasimonotone on C. Thanks to the following result due to Hassouni [14,15], Theorem 6.4 enables us to characterize convexity in terms of the monotonicity of 6Rf(x). Now we give a proof bit simpler than that of Hassouni, applying characterization (15) instead of the Hassouni's definition. Lemma 6.5 Let T(x) be defined on C C X. Then the following statements are equivalent: (i) T(x) is monotone on C, (ii) T(x) + g is quasimonotone for all g 6 X* Proof, (i) =>■ (ii): It is not difficult to prove that the monotonicity of T(x) implies the monotonicity and thus the quasimonotonicity of its "translates" T(x) + g for any g g X * (ii) => (i): Suppose that T(x) + g is quasimonotone for any g g X*. Setting g = 0, we infer that T(x) itself is quasimonotone, too. Assume for contradiction that T(x) fails to be monotone on C. It follows that there exist x , y g C and u g T(x), v g T(y) such that (u,y-x) + (v,x-y) >0 (18) Without loss of the generality we may assume that (u,y-x) >0. Taking into account (15) and (18) it follows that (u,x-y) < (v,x-y) <0.

(19)

Let g = —(u + v)/2 and consider the multifunction M(x) = T(x) + g . Then we have u + g g M(x) and v + g g M(y) and from (19) we obtain that (u + g , y - x ) > 0

and

(v + g , x - y ) > 0 ,

which contradicts to the quasimonotonicity of M(x). As a corollary to Lemma 6.5 and Theorem 6.4 we have the following result (cf. [7,26,32,40]). Proposition 6.6 Let C be an open convex subset of a Banach space X and / ( x ) be a proper lower semicontinuous function defined on C. Then / ( x ) is convex on C iff the Rockafellar subdifferential 6Rf(x) is monotone on C.

Monotonicity and

Quasimonotonicity

211

References [1] J.-P. Aubin, Optima and Equilibria, Springer-Verlag, Berlin Heidelberg, 1993. [2] E. Blum and W. Oettli, From optimization and variational inequalities to equi­ librium problems, The Mathematics Student 63 (1993) 1-23. [3] M. Bianchi, Generalized quasimonotonicity and strong pseudomonotonicity of bifunctions, Contributi di Ricera, Universite Cattolica del Sacro Cuore di Milano, 1994. [4] M. Bianchi, Strong pseudomonotonicity and generalized quasimonotonicity of bifunctions, in P. Mazzoleni (ed.) Optimization of Generalized Convex Problems in Economics, Milano, (1994) 101-112. [5] E. Castagnoli and P. Mazzoleni, Orderings, generalized convexity and mono­ tonicity, in: S. Komlosi, T. Rapcsak, S. Schaible (eds.) Generalized Convexity, Springer Verlag, Heidelberg, (1994) 250-262. [6] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley and Sons, New York, 1983. [7] R. Correa, A. Jofre, A. and L. Thibault, Characterization of lower semicontinuous convex functions, Proceedings of the American Mathematical Society 116 (1992) 67-72. [8] R. W. Cottle, F. Giannessi and J-L. Lions, (Eds.) Variational Inequalities and Complementarity Problems, Wiley and Sons, New York, 1980. [9] J.-P. Crouzeix and A. Hassouni, Quasimonotonicity of separable operators and monotonicity indices, Working Paper, Blaise Pascal University, 1993. [10] J.-P. Crouzeix and A. Hassouni, Generalized monotonicity of a separable product of operators: the multivalued case, Working Paper, Blaise Pascal University, 1993. [11] W. E. Diewert, Alternative characterizations of six kinds of quasiconcavity in the nondifferentiable case with applications to nonsmooth programming in: S. Schaible-W. T. Ziemba (eds.) Generalized Concavity in Optimization and Eco­ nomics, Academic Press, New York, 1981. [12] R. Ellaia and A. Hassouni, Characterization of nonsmooth functions through their generalized gradients, Optimization 22 (1991) 401-416.

212

S. Komlosi

[13] K-H. Elster and J. Thierfelder, On cone approximations and generalized direc­ tional derivatives, in: F. H Clarke, V. F. Dem'yanov a n ( j F. Giannessi, (eds.) Nonsmooth Optimization and Related Topics, Plenum Press, New York, (1989) 133-154. [14] A. Hassouni, Sous-difFerentiels des fonctions quasiconvexes, These de 3eme Cycle de 1'Universite Paul Sabatier, Toulouse, 1983. [15] A. Hassouni, Quasimonotone multifunctions: applications to optimality condi­ tions in quasiconvex programming, Numerical Functional Analysis and Opti­ mization 13 (1992) 267-275. [16] S. Karmardian, Complementarity over cones with monotone and pseudomonotone maps, Journal of Optimization Theory and Applications 18 (1976) 445-454. [17] S. Karmardian and S. Schaible, Seven kinds of monotone maps, Journal of Op­ timization Theory and Application 66 (1990) 37-46. [18] S. Karmardian, S. Schaible and J.-P. Crouzeix, Characterizations of generalized monotone maps, Journal of Optimization Theory and Application 76 (1993) 399413. [19] S. Komlosi, Generalized monotonicity of generalized derivatives, Working Paper, Janus Pannonius University, Pecs, (1991) 8. [20] S. Komlosi, On generalized upper quasidifFerentiability, in: F. Giannessi (ed.) Nonsmooth Optimization: Methods and Applications, Gordon and Breach, Lon­ don, (1992) 189-201. [21] S. Komlosi, Generalized monotonicity of generalized derivatives, in: P. Mazzoleni (ed.) Proceedings of the Workshop on Generalized Concavity for Economic Applications held in Pisa April 2, 1992, (Verona, 1992) 1-7. [22] S. Komlosi, Generalized monotonicity in nonsmooth analysis, in: S. Komlosi, T. Rapcsak, S. Schaible (eds.) Generalized Convexity, Springer Verlag, Heidel­ berg, (1994) 263-275. [23] S. Komlosi, Generalized monotonicity and generalized convexity, Working Paper, WP-92-16, Computer and Automation Institute of the Hungarian Academy of Sciences, Budapest, (1992) 23. (accepted by Journal of Optimization Theory and Application). [24] S. Komlosi, Generalized global monotonicity of generalized derivatives, in: R. Tomlinson (Ed.) International Transactions in Operational Research 1 (1994) 259-264.

Monotonicity and Quasimonotonicity

213

[25] S. Komlosi, Generalized monotonicity in nondifferentiable optimization, in: L. Martic, L. Neralic, H. Pasagic (Eds.) KOI'93 Proceedings, Croatian Operational Research Society, Zagreb, (1993) 17-31. [26] D. T. Luc and S. Swaminathan, A characterization of convex functions, Nonlinear Analysis, Theory, Methods and Applications 20 (1993) 697-701. [27] D. T. Luc, Characterization of quasiconvex functions Bulletin of the Australian Mathemaiical Society 48 (1993) 393-405. [28] D. T. Luc, On generalized convex nonsmooth functions, Bulletin of the Australian Mathemaiical Society 49 (1994) 139-149. [29] O. L. Mangasarian, Pseudoconvex functions, SIAM Journal on Controls (1965) 281-290. [30] J. J. Moreau, Fonctionelles Convexes. Lecture notes, Seminare equations aux derivees partielles, College de France (1966). [31] R. Pini and S. Schaible, Some invariance properties of generalized monotonicity, in: S. Komlosi, T. Rapcsak, S. Schaible (eds.)Generalized Convexity. Springer Verlag, Heidelberg, (1994) 276-277. [32] R. A. Poliquin, Subgradient monotonicity and convex functions, Nonlinear Analysis 14 (1990) 305-317. [33] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ., 1970. [34] R. T. Rockafellar, Generalized directional derivatives and subgradients of nonconvex functions, Canadian Journal on Mathemaiics 32 (1980) 257-280. [35] R. T. Rockafellar, The Theory of Subgradients and its Applications to Problems of Optimizaiion: Convex and Nonconvex Functions, Heldermann Verlag, Berlin, 1981. [36] S. Schaible, Generalized monotone maps, in: F. Giannessi (ed.) Nonsmooth Optimization: Methods and Applications, Gordon and Breach, London, (1992) 392408. [37] S. Schaible, Generalized monotone maps - a survey, in: S. Komlosi, T. Rapcsak, S. Schaible (eds.)Generalized Convexity, Springer Verlag, Heidelberg, (1994) 229249. [38] D. Zagrodny, Approximate mean value theorem for upper subderivatives, Nonlinear Analysis, Theory, Methods and Applications 12 (1988) 1413-1438.

214

S. Komlosi

[39] D. Zagrodny, A Note on the equivalence between the mean value theorem for the Dini derivative and the Clarke-Rockfellar derivative, Optimization 21 (1990) 179-183. [40] M. Tosques, Equivalence between generalized gradients and subdifferentials for a suitable class of lower semicontinuous functions, in: S. Komlosi, T. Rapcsak, S. Schaible (eds.) Generalized Convexity, Springer Verlag, Heidelberg, (1994) 116— 133. [41] D. Aussel, J. N. Corvellec and M. Lassonde, Subdifferential characterization of quasiconvexity and convexity, Journal on Convex Analysis, to appear. [42] S. Komlosi, Monotonicity and quasimonotonicity for multifunctions, in: P. Mazzoleni (ed.) Optimization of Generalized Convex Problems in Economics, Milano, (1994) 27-39.

Sensitivity

of Solutions

in Nonlinear

Programming

215

Recent Advances in Nonsmooth Optimization, pp. 215-223 Eds. D.-Z. Du, L. Qi and R.S. Womersley ©1995 World Scientific Publishing Co Pte Ltd

Sensitivity of Solutions in Nonlinear Programming Problems with Nonunique Multipliers A. B. Levy Department of Mathematics,

Bowdoin

R. T. Rockafellar Department of Mathematics,

University

College, Brunswick,

of Washington,

ME 04011

Seattle,

USA

WA 98195

USA

Abstract

We analyze the perturbations of quasi-solutions to a parameterized nonlin­ ear programming problem, these being feasible solutions accompanied by a Lagrange multiplier vector such that the Karush-Kuhn-Tucker optimality con­ ditions are satisfied. We show under a standard constraint qualification, not requiring uniqueness of the multipliers, that the quasi-solution mapping is differentiable in a generalized sense, and we present a formula for its derivative. The results are distinguished from previous ones in the subject, in that they do not entail having to impose conditions to ensure that dual as well as primal elements behave well with respect to sensitivity.

1

Introduction

A s t a n d a r d p a r a m e t e r i z e d nonlinear p r o g r a m m i n g problem can b e formulated in t e r m s of s m o o t h functions / ; on IR" x IR'' as follows: minimize fQ{x,w) where t h e set C(w) C(w)

— (v,x)

over all x € C(w),

C IR" is denned by

: = {x : h{x,w)

< 0,...., f,(x,w)

< 0J,+l(x,w)

= 0, . . . . , / „ ( * , u>) = o } .

(1)

A. B. Levy and R. T. RockafeU&r

216

Here w £ 1R and v £ fit" both serve as parameter elements. In principle, the "tilt" perturbations represented through v could be subsumed into w, but they have an essential role in theory, and we therefore keep them explicit. We concentrate our attention on points x that are quasi-solutions to the mini­ mization problem (1) in the sense of satisfying, in association with some multiplier vector y, the Karush-Kuhn-Tucker (K-K-T) optimality conditions: 3y = {Uu■■•,Um) € A r *:(/i(z,"'), • • •, fm{x,w)) V = Vr/0(l,U)) + y1VI/1(x,tu)+

with

(2)

\-ym^xfm(x,w),

written here for convenience in terms of NK(U) denoting the set of normal vectors at u to the polyhedral cone K := {ueW

:ui < 0 , . . . , u , < 0 , u s + 1 = 0 , . . . , « m = 0}.

(3)

Thus, for any u £ K the vectors y 6 NK(U) are the ones with j / ; > 0 for indices z £ { l , . . . , m } having u, = 0 but yt = 0 for indices i £ { l , . . . , m } with u; < 0, whereas j/, is unrestricted for indices i £ {s + 1 , . . . , m } . (By convention, NK(U) is the empty set when u ^ K.) The notation y 6 NK(U) saves us from repeatedly having to write down such complicated details, and it has the further advantage of adapting in the framework of variational analysis to a broad range of circumstances beyond those that come into play here. The K-K-T conditions are of course necessary for a feasible solution x to be locally optimal under the Mangasarian-Fromovitz constraint qualification, which in turn takes the form

fly = {yu---,ym) yiVi/i(i,«)) +

e Ni<(fi(x,™),■ ■ ■ Jm{x,w)) with \-ym^xfm(x,w)

(4)

= 0, except y = 0.

Quasi-solutions are sure to be optimal solutions when the minimization problem ex­ hibits convexity with respect to x, but this is not an issue of concern to us here. The quasi-solution mapping S in this framework associates with each parameter element (w, v) G E.d+n the set S(w,v) := [x £ IRn : the K-K-T conditions (2) hold}. Since, in general, S(w, v) is not a singleton, this equation defines a multifunction (set-valued mapping) S : 1R + " ^? R". In the main result of this paper, we calculate a kind of generalized derivative of S with respect to (w,v). Until now, differentiability properties of 5 have been studied by distinctly different means than will be used here. Most researchers (cf. [2], [6], and [1] for a survey) have looked at the sensitivity of solution multifunctions defined by K-K-T pairs {x,y), T(w,v) := {(x,y) : x solves the K-K-T conditions (2) with y as multiplier},

Sensitivity of Solutions in Nonlinear Programming

217

being forced by this strategy to make strong assumptions about the multipliers y (e.g. uniqueness) in order to draw conclusions about the x-components of these pairs. Some exceptions to this approach are described in [6] where, however, single-valuedness of the solution mapping S is essential. Our approach is new and has the advantage of enabling us to study the "primal" solution multifunction S directly, without any restrictions on the multipliers. In such a setting, much broader than previously has been accessible, our approach leads to formulas describing the magnitude and di­ rection of perturbations of quasi-solutions in terms of approximations based on set convergence. It does not in itself, though, provide tests for whether S is single-valued in a localized sense. Our methodology derives from our recent work in [3], where we studied the sensi­ tivity of parameterized "variational conditions'' over a set which itself can depend on the parameters. Associated with any closed set C C 1R" and mapping F : W1 —► IR" is the variational condition F{x) + Nc(x) 9 0,

x € C.

(5)

When C is convex, this expresses the variational inequality for C and F. When C is not convex, Nc(x) is interpreted as the cone of "limiting proximal normals" in nonsmooth analysis, rather than the cone of normal vectors in the sense of convex analysis. The parameterized variational conditions studied in [3] are of the form F{x, w) + NC(w)(x) 3v,

x <= C(w),

(6)

with parameter element (w,v) 6 K. x IB". As long as the Mangasarian-Fromovitz constraint qualification (4) holds, the K-K-T optimality conditions (2) can be re­ formulated in terms of this type of parameterized variational condition by taking F(x,w) = Vxf0(x,w) (details in Section 3). The quasi-solution multifunction S is given then by the solutions to the parameterized variational condition (6), the pertur­ bations of which were analyzed in [4]. Here we show that by applying the results of [3] to this formulation of the K-K-T optimality conditions, it can be established that S is "proto-differentiable," moreover with a specific formula for the proto-derivatives.

2

Proto-derivatives

Proto-differentiability, a concept of generalized differentiability which was introduced in [9], is distinguished from other differentiability concepts through its utilization of set convergence of graphs. Consider any multifunction T : W =t Ht" and any pair (u>, z) in the graph of T, i.e., with z G T{w). For each t > 0 one can form the difference quotient multifunction (A ( I%, f : u> ~ [T(w + tw) -

z]/t.

218

A. B. Levy and R. T. Rockafellar

Instead of asking the difference quotient multifunctions (AtT)w,z to converge in some kind of pointwise sense as tiO, proto-differentiability asks that they converge graph­ ically, i.e., that their graphs converge as subsets of IRm x IR" to the graph of some multifunction A. Then A is the proto-derivative multifunction at w for z and is denoted by T^y, for each u> G IR , T'mi{u) is a certain (possibly empty) subset of IR". The concept of Painleve-Kuratowski set convergence underlies the formation of these graphical limits. It refers to a kind of approximation described from two sides as follows. The inner set limit of a parameterized family of sets {Gt}t>o in IR is the set of points n such that for every sequence <* 10 there is a sequence of points rj^ € Gtk with rjk —> r]. The outer set limit of the family is the set of points t] such that for some sequence tki0 there is a sequence of points nk € Gtk with 77* —► 77. When the inner and outer set limits coincide, the common set G is the limit as tiO. In our framework, this is applied to sets that are the graphs of multifunctions. For a multifunction T : IR™ ■=? W and any pair (w,z) in gphT, i.e., with z 6 r(u>)