×

zbMATH — the first resource for mathematics

Active-set projected trust-region algorithm for box-constrained nonsmooth equations. (English) Zbl 1140.65331
Summary: By means of an active-set strategy, we present a trust-region method for solving box-constrained nonsmooth equations. Nice properties of the proposed method include: (a) all iterates remain feasible; (b) the search direction, as adequate combination of the projected gradient direction and the trust-region direction, is an asymptotic Newton direction under mild conditions; (c) the subproblem of the proposed method, possessing the form of an unconstrained trust-region subproblem, can be solved by existing methods; (d) the subproblem of the proposed method is of reduced dimension, which is potentially cheaper when applied to solve large-scale problems. Under appropriate conditions, we establish global and local superlinear/quadratic convergence of the method. Preliminary numerical results are given.

MSC:
65H10 Numerical computation of solutions to systems of equations
90C53 Methods of quasi-Newton type
90C56 Derivative-free methods and methods using generalized derivatives
Software:
MCPLIB; STRSCNE
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ferris, M. C., and Pang, J. S., Engineering and Economic Applications of Complementarity Problems, SIAM Review, 39, 669-713, 1997. · Zbl 0891.90158
[2] Harker, P. T., and Pang, J. S., Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems; A Survey of Theory, Algorithms, and Applications, Mathematical Programming, 48, 161-220, 1990. · Zbl 0734.90098
[3] Pang, J. S., and Qi, L., Nonsmooth Equations; Motivation and Algorithms, SIAM Journal on Optimization, 3, 443-465, 1993. · Zbl 0784.90082
[4] Qi, L., Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations, Mathematics of Operations Research, 18, 227-245, 1993. · Zbl 0776.65037
[5] Ulbrich, M., Nonmonotone Trust-Region Method for Bound-Constrained Semismooth Equations with Applications to Nonlinear Mixed Complementarity Problems, SIAM Journal on Optimization, 11, 889-917, 2001. · Zbl 1010.90085
[6] Qi, L., 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, 24, 440-471, 1999. · Zbl 0977.90064
[7] Dirkse, S. P., and Ferris, M. C., MCPLIB; A Collection of Nonlinear Mixed Complementarity Problems, Optimization Method and Software, 5, 319-345, 1995.
[8] Kanzow, C., An Active-Set Type Newton Method for Constrained Nonlinear Equations, Complementarity; Applications, Algorithms, and Extensions, M. C. Ferris, O. L. Mangasarian, and J. S. Pang, Kluwer Academic Publishers, Dondrecht, Holland, 179-200, 2001. · Zbl 0983.90060
[9] Bellavia, S., Macconi, M., and Morini, B., An Affine Scaling Trust-Region Approach to Bound-Constrained Nonlinear Systems, Applied Numerical Mathematics, 44, 257-280, 2003. · Zbl 1018.65067
[10] Gabriel, S. A., and Pang, J. S., A Trust-Region Method for Constrained Nonsmooth Equations, Large Scale Optimization–State of the Art, W. W. Hager, D. W. Hearn, and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Holland, 155-181, 1994. · Zbl 0813.65091
[11] Kanzow, C., Strictly Feasible Equation-Based Method for Mixed Complementarity Problems, Numerische Mathematik, 89, 135-160, 2001. · Zbl 0992.65070
[12] Sun, D., Womersley, R. S., and Qi, H., A Feasible Semismooth Asymptotically Newton Method for Mixed Complementarity Problems, Mathematical Programming, 94, 167-187, 2002. · Zbl 1023.90068
[13] Clarke, F. H., Optimization and Nonsmooth Analysis, John Wiley, New York, NY, 1983. · Zbl 0582.49001
[14] Calamai, P. H., and MorĂ©, J. J., Projected Gradient Methods for Linear Constrained Problems, Mathematical Programming, 39, 93-116, 1987. · Zbl 0634.90064
[15] Kanzow, C., and Qi, H. D., A QP-Free Constrained Newton-Type Method for Variational Inequality Problems, Mathematical Programming, 85, 81-106, 1999. · Zbl 0958.65078
[16] Qi, H., Qi, L., and Sun, D., Solving KKT System via the Trust Region and the Conjugate Gradient Method. Technical Report, School of Mathematics, University of New South Wales, Sydney, New South Wales, Australia, 2000.
[17] Jiang, H., Fukushima, M., Qi, L., and Sun, D., A Trust-Region Method for Solving Generalized Complementarity Problems, SIAM Journal on Optimization, 8, 140-157, 1998. · Zbl 0911.90324
[18] Facchinei, F., and Kanzow, C., On Unconstrained and Constrained Stationary Points of the Implicit Lagrangian, Journal of Optimization Theory and Applications, 92, 99-115, 1997. · Zbl 0914.90249
[19] Fischer, A., New Constrained Optimization Reformulation of Complementarity Problems, Journal of Optimization Theory and Applications, 97, 105-117, 1998. · Zbl 0907.90260
[20] Steihaug, T., The Conjugate Gradient Method and Trust Region in Large-Scale Optimization, SIAM Journal on Numerical Analysis, 20, 626-637, 1983. · Zbl 0518.65042
[21] Yuan, Y., On the Truncated Conjugate Gradient Method, Mathematical Programming, 87, 561-573, 2000. · Zbl 0955.65039
[22] Geiger, C., and Kanzow, C., On the Resolution of Monotone Complementarity Problems, Computational Optimization and Applications, 5, 155-173, 1996. · Zbl 0859.90113
[23] Jiang, H., and Qi, L., A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems, SIAM Journal on Control and Optimization, 35, 178-193, 1997. · Zbl 0872.90097
[24] Hock, W., and Schittkowski, K., Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, Germany, 187, 1981. · Zbl 0452.90038
[25] Ralph, D., and Wright, S. J., Superlinear Convergence of an Interior-Point Method for Monotone Variational Inequalities, Complementarity and Variational Problems, State of the Art, M. C. Ferris and J. S. Pang, SIAM, Philadelphia, Pennsylvania, 345-385, 1997. · Zbl 0886.90162
[26] Chen, C., and Ye, Y., On Smoothing Methods for the P0 Matrix Linear Complementarity Problem, SIAM Journal on Optimization, 11, 341-363, 2000. · Zbl 0994.65077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.