On NCP-Functions
Tóm tắt
In this paper we reformulate several NCP-functions for the nonlinear complementarity problem (NCP) from their merit function forms and study some important properties of these NCP-functions. We point out that some of these NCP-functions have all the nice properties investigated by Chen, Chen and Kanzow [2] for a modified Fischer-Burmeister function, while some other NCP-functions may lose one or several of these properties. We also provide a modified normal map and a smoothing technique to overcome the limitation of these NCP-functions. A numerical comparison for the behaviour of various NCP-functions is provided.
Tài liệu tham khảo
S. C. Billups, S. P. Dirkse and M. C. Ferris, “A comparison of algorithms for large scale mixed complementarity problems,” Computational Optimization and Applications, vol. 7, pp. 3-25, 1997.
B. Chen, X. Chen and C. Kanzow, “A penalized Fischer-Burmeister NCP-function: theoretical investigation and numerical results,” Applied Mathematics Report 97/28, School of Mathematics, the University of New South Wales, Sydney 2052, Australia, 997.
B. Chen and P.T. Harker, “A non-interior-point continuation method for linear complementarity problems”, SIAM Journal on Matrix Analysis and Applications, vol. 14, pp. 1168-1190, 1993.
C. Chen and O.L. Mangasarian, “A class of smoothing functions for nonlinear and mixed complementarity problems”, Computational Optimization and Applications, vol. 5, pp. 97-138, 1996.
F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley: New York, 1983.
T. De Luca, F. Facchinei and C. Kanzow, “A semismooth equation approach to the solution of nonlinear complementarity problems,” Mathematical Programming, vol. 75, pp. 407-439, 1996
T. De Luca, F. Facchinei and C. Kanzow, “A theoretical and numerical comparison of some semismooth algorithms for complementarity problems,” Mathematical Programming Technical Report 97-15, Computer Sciences Department, University of Wisconsin-Madison, Madison, WI, December 1997.
S. P. Dirkse and M. C. Ferris, “MCPLIB: A collection of nonlinear mixed complementarity problems,” Optimization Methods and Software, vol. 5, pp. 319-345, 1995.
F. Facchinei, A. Fischer and C. Kanzow, “A semismooth Newton method for variational inequalities: The case of box constraints,” in Complementarity and Variational Problems: State of the Art, SIAM: Philadelphia, Pennsylvania, pp. 76-90, 1997.
F. Facchinei and J. Soares, “A new merit function for nonlinear complementarity problems and a related algorithm,” SIAM Journal on Optimizationm vol. 7, pp. 225-247, 1997.
M.C. Ferris and J.-S. Pang, “Engineering and economic applications of complementarity problems,” SIAM Review, vol. 39, pp. 669-713, 1997.
M. C. Ferris and T. F. Rutherford, “Accessing realistic mixed complementarity problems within MATLAB,” in Nonlinear Optimization and Applications, Plenum Press: New York, 141-153, 1996.
A. Fischer, “A special Newton-type optimization method,” Optimization, vol. 24, pp. 269-284, 1992.
A. Fischer, “Solution of monotone complementarity problems with locally Lipschitzian functions,” Mathematical Programming, vol. 76, pp. 513-532, 1997.
M. Fukushima, “Merit functions for variational inequality and complementarity problems,” in Nonlinear Optimization and Applications, Plenum Publishing Corporation: New York, pp. 155-170, 1996.
L. Grippo, F. L. Lampariello and S. Lucidi, “A nonmonotone linesearch technique for Newton's method,” SIAM Journal on Numerical Analysis, vol. 23, pp. 707-716, 1986.
P.T. Harker and J.-S. Pang, “Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications,” Mathematical Programming, vol. 48, pp.161-220, 1990.
H. Jiang, M. Fukushima, L. Qi and D. Sun, “A trust region method for solving generalized complementarity problems,” SIAM Journal on Optimization, vol. 8, pp. 140-157, 1998.
C. Kanzow, “An unconstrained optimization technique for large-scale linearly constrained convex minimization problems,” Computing, vol. 53, pp. 101-117, 1994.
C. Kanzow, “Some noninterior continuation methods for linear complementarity problems”, SIAM Journal on Matrix Analysis and Applications, vol. 17, pp. 851-868, 1996.
C. Kanzow, N. Yamashita and M. Fukushima, “New NCP-functions and their properties,” Journal of Optimization Theory and Applications, vol. 94, pp. 115-135, 1997.
Z.-Q. Luo and P. Tseng, “A new class of merit functions for the nonlinear complementarity problem,” in Complementarity and Variational Problems: State of the Art, SIAM: Philadelphia, Pennsylvania, pp. 204-225, 1997.
O.L. Mangasarian and M.V. Solodov, “Nonlinear complementarity as unconstrained and constrained minimization,” Mathematical Programming, vol. 62, pp. 277-297, 1993.
R. Mifflin, “Semismooth and semiconvex functions in constrained optimization,” SIAM Journal on Control and Optimization, vol. 15, pp. 957-972, 1977.
J.-S. Pang, “Complementarity problems,” in Handbook of Global Optimization, Kluwer Academic Publishers: Boston, pp. 271-338, 1995.
L. Qi, “Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems,” Mathematics of Operations Research, to appear.
L. Qi and H. Jiang, “Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations,” Mathematics of Operations Research, vol. 22, pp. 301-325, 1997.
L. Qi, D. Sun and G. Zhou, “A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities,” Applied Mathematics Report AMR 97/13, School of Mathematics, the University of New South Wales, Sydney 2052, Australia, 1997.
L. Qi and J. Sun, “A nonsmooth version of Newton's method,” Mathematical Programming, vol. 58, pp. 353-367, 1993.
S.M. Robinson, “Strongly regular generalized equations,” Mathematics of Operations Research, vol. 5, pp. 43-62, 1980.
S.M. Robinson, “Normal maps induced by linear transformation,” Mathematics of Operations Research, vol. 17, pp. 691-714, 1992.
S. Smale, “Algorithms for solving equations,” in Proceedings of the International Congress of Mathematicians, Berkeley, California, pp. 172-195, 1986.
D. Sun and R.S. Womersley, “A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,” SIAM Journal on Optimization, to appear.
P. Tseng, “Global behaviour of a class of merit functions for the nonlinear complementarity problem,” Journal of Optimization Theory and Applications, vol. 89, pp. 17-37, 1986.
N. Yamashita and M. Fukushima, “A new merit function and a descent method for semi-definite programming problem,” in Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers B.V., 381-404, 1998.
G. Zhou, D. Sun and L. Qi, “Numerical experiments for a class of squared smoothing Newton methods for complementarity and variational inequality problems,” in Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers B.V., pp. 421-441, 1998.