%A Chunhui Chen
%T Smoothing Methods in Mathematical Programming
%D August 2, 1995
%R 95-12
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X A class of parametric smooth functions that approximate the fundamental
plus function,
$(x)_+ =$ max$\{0,x\}$, is obtained by twice integrating a
probability density function.
By means of this approximation,
linear and convex inequalities are converted into smooth, convex unconstrained
minimization problems, the solution of which approximates the solution of
the original problem to a high degree of accuracy for sufficiently
small positive value of the smoothing parameter $\beta$.
In the special case when a Slater constraint qualification is
satisfied, an exact solution can be obtained for finite $\beta$. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size
$ 2000 \times 1000$, and 580 times for convex inequalities with 400
variables.
Linear complementarity problems were treated by converting them
into a system of smooth nonlinear
equations and are solved by a quadratically convergent Newton method. For
monotone LCP's with as many as 10,000 variables, the proposed approach was
as much as 63 times faster than Lemke's method.
Our smooth approach can also be used to solve
nonlinear and mixed complementarity problems
(NCPs and MCPs) by converting them to
classes of smooth parametric nonlinear equations. For any solvable NCP or MCP, existence of an arbitrarily
accurate solution to
the smooth nonlinear equation as well as the NCP or MCP, is established
for sufficiently large value
of a smoothing parameter $\alpha=\frac{1}{\beta}$.
An efficient smooth algorithm, based on the Newton-Armijo approach with
an adjusted smoothing parameter, is also given and its global and local
quadratic convergence is established.
For NCP's, exact solutions of our smooth nonlinear equation for
various values of the parameter $\alpha$, generate an interior path, which
is different from the central path for interior point method.
Computational results for 52 test problems compare
favorably with those for another Newton-based method. The smooth technique is
capable of solving efficiently the test problems solved by
Dirkse \& Ferris \cite{fd:1993}, Harker \& Xiao \cite{hx:89} and Pang \&
Gabriel \cite{pangab:93}.