A Globally Convergent Successive Approximation Method for Severely Nonsmooth Equations.
This paper presents a globally convergent successive approximation  method for solving $F(x)=0$ where $F$ is a continuous function. At each step of the method, $F$ is approximated by a smooth function $f_{k},$ with $\pa f_{k}-F\pa \rightarrow 0$ as $k \rightarrow \infty$. The direction $-f'_{k}(x_{k})^{-1}F(x_{k})$ is then used in a line search on a sum of squares objective. The approximate function  $f_k$ can be constructed for nonsmooth equations arising from variational inequalities, maximal monotone operator problems, nonlinear complementarity problems, and nonsmooth partial differential equations. Numerical examples are given to illustrate the method.
Introduction
be a continuous, but not necessarily differentiable,
function. We consider the system of nonlinear equations
The recent literature of such nonsmooth equations includes [1-3, 6-8, 10-
13, 15, 17, 19-21].
This work is supported by the Australian Research Council.
If F is smooth, a popular method for solving (1) is the damped Newton
method [4][9]
Solve F to get d k
(2)
where the step size ff k in (0; 1] is chosen by a line search.
Han, Pang and Rangaraj [6] generalized the damped Newton method to
solve the nonsmooth equation (1) using the idea of an "iteration function".
defined by
Damped Newton Method with Iteration Function (IF)
Let ae; oe 2 (0; 1) be given. Let G : R n\Thetan ! R n be a given iteration function.
Solve F to get d k
is the smallest nonnegative integer m such that
Global convergence was established in [6] under four assumptions on G
and F T G. In general, G(x; \Delta) is nonlinear. This implies that a system of
nonlinear equations (generally easier than (1)) is solved at each step in the
above method.
Recently, Gabriel and Pang [7] proposed a trust region algorithm using
iteration functions. They also required certain assumptions on the iteration
functions to establish convergence of their algorithm. Poliquin and Qi [14]
proved that, in the case of nonsmooth optimization, the assumptions on
the iteration functions actually implied restrictions on the original function.
There are other globally convergent methods for nonsmooth equations [10-13,
20]. These methods either assume conditions much stronger than continuity,
or only work for some special problems.
In this paper, we introduce a successive approximation method. Let jj \Delta jj
denote the Euclidean norm. At the k-th step, we approximate F by a smooth
function f k such that
and ff 2 (0; 1) is a fixed constant. The algorithm uses f 0
derivative of F at x k is needed.
There are two outstanding advantages of the new algorithm over existing
methods. The first advantage is that a linear approximation is made at
each step, so the subproblem is a system of linear equations. Known globally
convergent methods for solving nonsmooth equations do not have this
feature. The second advantage is that the conditions required to establish
convergence and implement the new algorithm are very general. We establish
global convergence of this algorithm under the following assumptions on F :
continuity of F , boundedness of a level set, and nonsingularity of f 0
k at x k
for all k and at x   ; an accumulation point of fx k g. To implement our algorithm
we require F to be locally Lipschitzian. Under these assumptions, we
may construct f k with the desired accuracy. The basic tool is the integration
convolution. In some special cases, we have other ways to construct f k .
Although we discuss the linear convergence of this algorithm in Section
3, we do not intend to pursue higher rate of convergence for this method.
There are already several superlinearly convergent methods [10,11,19-21] and
a superlinear convergence theory [13,15] for solving nonsmooth equations.
One may construct a hybrid algorithm which is globally and superlinearly
convergent using the new algorithm and a known superlinearly convergent
algorithm with the methodology proposed in [15]. We do not go into the
details of such a construction. The merit of our algorithm is that it may solve
some severely nonsmooth equations, such as nonsmooth equations arising
from the variational inequality problem for a general convex set and from
the maximal monotone operator problem (see Section 5).
In Section 2 we describe the successive approximation method and prove
its global convergence.
In Section 3 we consider the rate of convergence.
In Section 4 we discuss how to construct a successive approximation function
for a nonsmooth function F using integration convolution.
In Section 5 we investigate some applications of our algorithm.
In Section 6 we give numerical results with the successive approximation
method.
2. Method and Global Convergence
Definition 1. Let ff 2 (0; 1) be a constant. At the kth step of the iteration
methods described in this section and the next section, we call
a normal decomposition of F , if f k is smooth and k g k k- ff k F
whenever F
We shall give some examples of normal decompositions in Section 5.
Let
and
Our method can be described as follows:
The successive approximation method (SAM).
Given ae; ff 2 (0; 1), an initial vector x 0 2 R n and a normal decomposition
1. Solve F
to get d k .
2. Set x
is the smallest nonnegative integer m such that
3. If F
. Otherwise, we construct a new normal decomposition
with k g k+1 k-minf ffk F
Assumption 1. The level set
is bounded.
Assumption 2. f 0
are nonsingular for all k.
Lemma 1. Suppose that F k is a normal decomposition
of F . Then, there exists a scalar t k 2 (0; 1] such that for all t 2 (0; t k ]
Proof. Notice
We have
such that for all t 2 (0; t k ], (3) holds.Lemma 1 indicates that the SAM is well-defined under Assumption 2.
Theorem 1. Suppose that Assumptions 1 and 2 hold. Then the SAM is
well-defined and for all k,
Let fx k g be a sequence produced by the SAM. If furthermore for an accumulation
point x   of fx k
nonsingular for all large k, then
lim
and
for all accumulation points ~
x of fx k g.
Proof. Without loss of generality, we may assume that F is not smooth.
Hence k g k k? 0 for any k.
By Lemma 1, the SAM is well-defined. We now prove (4). Without loss
of generality, we assume that F
kg. Assume that K consists of k
Let k be an arbitrary nonnegative integer. Let k j be the largest number in
K such that k j - k. Then
and
-ff
In both cases it follows that '(x k This implies that (4)
holds.
We now prove the second part of the theorem. If K is infinite, then for
any k - 0, there exists k j 2 K being the largest number in K such that
holds. The limit in the right-hand side of (6) is zero. This
proves (5).
Hence, to prove (5), it suffices to prove that K is infinite. Suppose K is
finite and assume -
Hence for all k -
and
Suppose that K 0 is a subsequence of f0; 1; :::g such that fx converges
to x   . By (7) and the condition of this theorem, f 0
Since lim k!1
(\Delta) is a continuous function, fk f 0
is uniformly bounded. Therefore, there exists L ? 0 such that
(\Delta) is continu-
ous, we have ffi ? 0 such that for all x satisfying
-ffl:
Since lim k!1
k such that for all k ? - k, k 2 K 0
Let t   2 (0; 1) be such that
By (10) and (11), for all k ? -
Now by (9) and (12), for all k ? - k; k 2 K 0 and t 2 (0; t   ], we have
Therefore, for all k - k; k 2 K 0 and t 2 (0; t   ];
This implies that for all k - k, k 2 K 0 , we have ae
By (8), (14) and the construction of our algorithm, for all k -
However, by (7) and the construction of our algorithm, ' -
nonincreasing
for k - k. This implies ' -
1. This contradicts the
fact that ' - k cannot be finite. This proves (5).
The final conclusion of this theorem simply follows (5) and the continuity of
F .Remark 1. We may inductively apply the proof of Lemma 1 and the first
part of Theorem 1 to prove (3) and (4). In this way, we may reduce Assumption
2 to :" f 0
are nonsingular for all k satisfying x k 2 D 0 ."
Remark 2. In [17] trust region methods using decomposition of F for nonsmooth
equations were presented. In the second one, successive approximation
was used, and F used in classical trust region methods were
replaced by f(x k ) and f 0 respectively. If we use successive approximation
and replace all F in the SAM by f k then we can also prove the
global convergence with the technique of [17].
3. Convergence Rate
In order to give a convergence rate, we consider a modification of the
SAM.
Modified
Given ae; ff 2 (0; 1), and c 2 (0; 1
1+ff
), an initial vector x 0 2 R n and a
normal decomposition
1. Solve F
to get d k .
If
we let x . Otherwise, we do Steps 2
and 3 in the SAM.
Theorem 2. Theorem 1 holds for the MSAM.
Proof. Let K be the set of k such that (15) holds. If K is finite, then the
MSAM is essentially the same as the SAM. Hence Theorem 1 holds in this
case. Suppose now K is infinite. Let k i and k i+1 be two consecutive numbers
in K. If k
)jj:
Otherwise, with an argument similar to the first part of the proof of Theorem
1, for any k satisfying
Hence, for any k satisfying
This shows that (5) holds. Then the conclusion
follows.The proof of Theorem 2 shows that the MSAM is globally convergent and
the norm jjF
reduces linearly in i if (15) holds infinitely many times.
In the following theorem, we show that under some conditions, the linear
convergence rate can be realized, and that need not be a normal
decomposition any more for all large k.
Theorem 3. Suppose that the conditions of Theorem 1 hold and that x
is an accumulation point of fx k g generated by the MSAM. Suppose that
there exist a positive integer -
k and positive numbers and fi such that
and
Then for all k - k; f
Furthermore, for all k -
k, (15) also holds.
Proof. By Theorem 2, F
By the Perturbation Lemma, for all x 2 S(x   ; r);
. Then from x -
This implies -
Furthermore,
Therefore, we have x -
. So that f -
k and g - Repeating
the proof with -
3. If F is smooth, then 0: Then the quadratic rate
of convergence of the Damped Newton method is recovered by (17).
4. Approximation Using Convolution
In this section and the next two sections, we use x i to represent the ith
component of a vector x and use x k to represent a vector.
Without loss of generality, we may assume that F : R n ! R n is bounded
and uniformly continuous. If F is continuous but not bounded and not
uniformly continuous, let the level set D 0 be defined as in Section 2. By
Assumption 1, there is r
by
x
Then (1) is equivalent to
while F 0 is bounded and uniformly continuous. Hence, we assume that F is
bounded and uniformly continuous. Let M be a bound of jjF jj.
R+ be the modulus of continuity of F , defined by
Then ! is a continous nondecreasing function [9], and for any x
and y in R n , we have
We call \Phi : R n ! R+ a kernel function if
Z
If \Phi is a kernel function, then defined by
where - is a positive number, is also a kernel function. If \Phi is smooth, then
\Phi - is also smooth. If OE : R ! R+ is a one-dimensional (smooth) kernel
defined by
is an n-dimensional (smooth) kernel function. Two famous one-dimensional
smooth kernel functions are
(Cauchy
and
(see Shapiro [24]).
Suppose now that \Phi : R n ! R+ is a smooth kernel function. For any
Z
Z
According to [5,23,25], F - is a smooth function and
Z
Furthermore, for any x in R n ,
Z
Z
For any ffl ? 0, let be such that
Z
jjxjj?r
and
For any - ? r
, we have
Z
Z
Z
Z
Z
Z
Z
\Phi(z)dz
Z
jjzjj?r
Therefore, in Section 2, if F we may choose
construct
i.e., we have the normal decomposition required in Section 2.
To construct F - satisfying (21), we need to know r ? 0 and
that (19) and (20) hold. If \Phi is constructed by (18), then it is not very
difficult to choose r. Actually, if (18) holds, then we only need r to satisfy
Z
On the other hand, if F is globally Lipschitzian with constant L 0 , then
. Then (20) will be satisfied. In Section 5,
we will give examples of such applications.
If F is locally Lipschitzian, by the construction of F 0 at the beginning of
this section, F 0 is always globally Lipschitzian. Hence our method can be
implemented as long as F is locally Lipschitzian.
5. Applications of the Successive Approximation Method
In this section, we discuss some applications of the successive approximation
method. The first two examples have appeared in the literature such as
[13].
5.1 The Variational Inequality Problem
Let C be a closed convex subset of R n and be a once continuously
differentiable function defined on the open set D ' R n containing
C. This problem, which we denote VI(C; OE), is to find a vector x   2 C such
that
The system is equivalent to a system of nonsmooth equations in R n
where \Pi C (y) denotes the projection of y on C. The nonsmoothness of the
function F is the consequence of the projection operator \Pi C (\Delta) (see [13]).
When C is a polyhedral set, this operator possesses some B-differentiability
properties that can be put to use algorithmically (see [10]). However, it is
not easy to establish these properties when C is a general convex set.
Since the projection operator is Lipschitzian with modulus 1, we can use
the tool of integration convolution stated in Section 4 to solve the nonsmooth
equations (22) by the successive approximation method.
5.2. The Maximal Monotone Operator Problem
be a set-valued maximal monotone operator. An
important problem is to find x 2 R n such that
According to the theory of the maximal monotone operator, the resolvent
of T , namely I is the identity operator and - is
a positive number, is always single-valued and nonexpansive (hence globally
[13]. Moreover, the solution of (23) is equivalent to that of the
nonsmooth equation (1) where
globally Lipschitzian, we can use the tool of integration
convolution to approximate F and solve the equation by the successive
approximation method.
5.3 LC 1 Optimization
Consider
R is a continuously differentiable function. Let
Then we may solve
to find the stationary points of (24). If F is locally Lipschitzian, then /
is called an LC 1 function and (24) is called an LC 1 optimization problem.
There are many examples of LC 1 optimization problems [16, 18]. For ex-
ample, if are conjugate functions of extend-valued
strongly convex functions ' 1 and ' 2 , then / 0
2 and F are globally Lips-
chitzian, see Theorem 2.5 of [16]. Actually, we have
are extended-valued convex quadratic functions, then we can
rewrite (26) as
z
n\Thetan is symmetric and positive definite, A i 2 R m\Thetan and b i
2: In Section 6, we will give a numerical example where F is defined
by (27) and (28).
5.4 The Nonlinear Complementarity Problem
We consider the nonlinear complementarity problem of finding x such
that
where are continuously differentiable. This problem can be
formulated as a system of nonsmooth equations (1) with
(see [13]). Now, we give a normal decomposition of F defined by (29). This
is simpler than the convolution approximation proposed in the general case.
Let ff 2 (0; 1) be a constant and
Let
(j
Then it is easy to verify that
f k is continuously differentiable, g k is continuous and k g k k-
5.5 A Piecewise Smooth Function
Consider
is a matrix, / is a diagonal continuous function, that is,
Such a system arises from nonsmooth
partial differential equations. In a general case, OE i is defined as a piecewise
where u i and v i are smooth functions with are con-
stants,
If
replace F i by \GammaF i . Hence, we may assume that
for all i, u 0
and
Then p; q are smooth functions and
is equivalent to (30).
Now, we can give a normal decomposition of F as in 5.4.
6. Numerical Experiments
In this section, we give some computation results to illustrate the SAM
and MSAM. The first example is from 5.3.
Example 1. Let
be nonempty convex polyhedra in R n . Let
and
n\Thetan are symmetric and positive definite, A i 2 R m\Thetan and b i 2
R m for 2:
We consider the nonsmooth equations
where P is an n \Theta n nonsingular matrix and c 0 is a fixed vector in R n .
Proposition 1. Let
n\Thetan is symmetric and positive definite, A 2 R m\Thetan and b 2 R m .
Assume that fz : Az - bg is not empty. Then
Proof. By Theorem 26.3 of [22], / is continuously differentiable and / 0
bg. Moreover
is the conjugate function of /, and ' is a strongly convex function, that is
Theorem 23.5 of [22],
Hence, for any t 2 (0; 1);
where the second inequality holds, because of the basic property of subgra-
dients. Let t ! 0, we have
Similarly, we have
Addition of (31) and (32) shows that
Hence,
Therefore,
can be generalized to the case that ' is locally strongly
convex. See [16]. By Proposition 1, F is globally Lipschitzian with modulus
(0)jj. If we take
the transformation mentioned in the beginning of Section 4, then jjF jj -
Hence we can give a normal decomposition of F using
convolution discussed in Section 4. Let
Z
We use the Cauchy kernel function stated in Section 4. At the kth step, let
)). Then we have jjF
We solve a system of linear equations:
where
Z
and 5f k
Z
Obviously, F is nondifferentiable at x if for one (x) is on
the boundary of Z i . We test the algorithm SAM with a four dimensional
problem where
7:0022 0:9018 0:6111 0:5042
0:6111 1:0961 6:9120 0:6618
0:5042 0:9506 0:6618 6:6859C C C A
@
2:0022 0:9018 0:6111 0:5042
0:9018 0:2974 1:0961 0:9506
0:6111 1:0961 1:9120 0:6618
0:5042 0:9506 0:6618 1:6850C C C
A
2:9174 1:4182 0:4576 1:0221
0:4576 0:7656 3:0682 0:8975
are randomly generated. Let
and
We randomly generate x   and choose c 0 such that x   is a solution of F
and F is nondifferentiable at the solution x   , i.e. is on the
boundary of Z 1 or Z 2 , respectively.
The Monte-Carlo method is used to calculate the integral numerically.
Numerical results are shown in Table 1 with random initial points.
Example 2.
We consider the following degenerate nonlinear complementarity problem
[8]:
This problem has two solutions
Formulate this problem as F defined by (29), then F (x)
is differentiable at x   but nondifferentiable at x    .
Using the Newton line search method with iteration function method(IF),
we quote the particular definition of iteration function G(\Delta; \Delta) given in [6].
d) otherwise.
The computational results by the IF, the SAM and the MSAM are shown
in

Table

2. We used single precision. We chose
1+ff
in the MSAM.

Table

1: Example 1.
Test problem 1
Test problem 2
x   (4.7545, 10.5370, 1.3704, 5.0524)
Test problem 3
Stopping criterion : jjF

Table

2: The iteration number k and jjx
Initial (1,0,0,0) (1,1,1,1) (1,0,1,0) (1,0,0,1)
Data
Stopping criterion
We see that these three methods are globally convergent. The final iteration
numbers of the SAM and MSAM are comparable with those of the IF.
The SAM and MSAM are further featured by less work at each iteration (the
SAM and MSAM only needs to solve a linear system of equations at each
step). We can construct approximation functions for any locally Lipschitzian
function but until now generally we do not know how to construct iteration
functions in this case. Therefore, the successive approximation method is
more general.

Acknowledgements

We are thankful to Professor Olvi Mangasarian, Dr. Rob Womersley,
three referees and Mr. Houyuan Jiang for their comments. We are grateful
to Professor Carl de Boor for his suggestion on convolution, which upgraded
this paper.



--R

On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms
Parameterized Newton method and Broyden-like method for solving nonsmooth equations
On the convergence of some quasi
Jr and R.
The minimization of discontinuous functions: mollifier subgradients
Globally convergent Newton methods for nonsmooth equations
A trust region method for constrained nonsmooth equations
Extensions of Newton and quasi-Newton methods to systems of PC 1 equations
Iterative Solution of Nonlinear Equations in Several Variables
Newton's method for B-differentiable equations

NE/SQP: A robust algorithm for the non-linear complementarity problem
motivation and algorithms
Iteration function in some nonsmooth optimization algorithms
Convergence analysis of some algorithms for solving nonsmooth equations
functions and LC 1 optimization problems
Trust region algorithms for solving nonsmooth equations
Superlinear convergent approximate Newton methods for LC 1 optimization problems
A nonsmooth version of Newton's method
Global convergence of damped Newton's method for nonsmooth equations via the path search
Newton's method for a class of nonsmooth functions
Convex Analysis

Smoothing and Approximation of Functions
Some Applications of Functional Analysis in Mathematical Physics
--TR

--CTR
. Ilker Birbil , Shu-Cherng Fang , Jiye Han, An entropic regularization approach for mathematical programs with equilibrium constraints, Computers and Operations Research, v.31 n.13, p.2249-2262, November 2004
L. Qi , D. Sun, Smoothing functions and smoothing Newton method for complementarity and variational inequality problems, Journal of Optimization Theory and Applications, v.113 n.1, p.121-147, April 2002
Smoothing Newton Method for Semi-Infinite Programming, Journal of Global Optimization, v.30 n.2-3, p.169-194, November  2004
Liqun Qi , Defeng Sun , Guanglu Zhou, A primal-dual algorithm for minimizing a sum of Euclidean norms, Journal of Computational and Applied Mathematics, v.138 n.1, p.127-150, 1 January 2002
Smoothing Newton and Quasi-Newton Methods for Mixed Complementarity Problems, Computational Optimization and Applications, v.17 n.2-3, p.203-230, December 2000
Bintong Chen , Xiaojun Chen, A Global Linear and Local Quadratic Continuation Smoothing Method for Variational Inequalities with Box Constraints, Computational Optimization and Applications, v.17 n.2-3, p.131-158, December 2000
Xiaojun Chen, Applications of smoothing methods in numerical analysis and optimization, Focus on computational neurobiology, Nova Science Publishers, Inc., Commack, NY, 2004
successive approximation;global convergence;integration convolution