Smoothing Methods in Mathematical Programming

Abstract

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 high degree of accuracy for sufficiently small positive value of the smoothing parameter B. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite B. Speedup over the linear/nonlinear programming package MINOS 5.4 was as high as 1142 time for linear inequalities of size 2000x1000, and 580 time for convex inequalities with 400 variables. Linear complementarity problems (LCPs) were treated by converting them into a system of smoothing nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10,000 variables, the proposed approach was as much as 63 time 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 a=B-1. An efficient smoothing 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 NCPs exact solutions of our smooth nonlinear equation for various values of the parameter a, generate an interior path, which is different from the central path for the interior point method. Computational results for 52 test problems compare favorably with those for another Newton based method. The smooth technique is capable of efficiently solving all the test problems solved by Dirkse & Ferris (1993). Harker & Xiao (1990) and Pang & Gabriel (1993).