×

An algorithm for composite nonsmooth optimization problems. (English) Zbl 0562.90077

Nonsmooth optimization problems are divided into two categories. The first is composite nonsmooth problems where the generalized gradient can be approximated by information available at the current point. The second is basic nonsmooth problems where the generalized gradient must be approximated using information calculated at previous iterates.
Methods for minimizing composite nonsmooth problems where the nonsmooth function is made up from a finite number of smooth functions, and in particular max functions, are considered. A descent method which uses an active set strategy, a nonsmooth line search, and a quasi-Newton approximation to the reduced Hessian of a Lagrangian function is presented. The theoretical properties of the method are discussed and favourable numerical experience on a wide range of test problems is reported.

MSC:

90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Clarke, F. H.,Generalized Gradients and Applications, Transactions of the American Mathematical Society, Vol. 205, pp. 247-262, 1975. · Zbl 0307.26012 · doi:10.1090/S0002-9947-1975-0367131-6
[2] Lemarechal, C.,Bundle Methods in Nonsmooth Optimization, Nonsmooth Optimization, Edited by C. Lemarechal and R. Mifflin, Pergamon Press, Oxford, England, pp. 71-78, 1978. · Zbl 0398.90088
[3] Fletcher, R.,Practical Methods of Optimization, Vol. 2, Constrained Optimization, John Wiley and Sons, New York, New York, 1981. · Zbl 0474.65043
[4] Womersley, R. S.,Numerical Methods for Structured Problems in Nonsmooth Optimization, University of Dundee, PhD Thesis, 1981.
[5] Womersley, R. S.,Optimality Conditions for Piecewise Smooth Functions, Mathematical Programming Study No. 17, pp. 13-27, 1982. · Zbl 0478.90059
[6] Powell, M. J. D.,The Convergence of Variable Metric Methods for Nonlinearly Constrained Optimization Calculations, Nonlinear Programming 3, Edited by O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, Academic Press, London, England, 1978. · Zbl 0464.65042
[7] Charalambous, C., andConn, A. R.,An Efficient Method to Solve the Minimax Problem Directly, SIAM Journal on Numerical Analysis, Vol. 15, pp. 162-187, 1978. · Zbl 0384.65032 · doi:10.1137/0715011
[8] Conn, A. R.,An Efficient Second-Order Method to Solve the Constrained Minimax Problem, University of Waterloo, Department of Combinatorics and Optimization, Report CORR-79-5, 1979.
[9] Fletcher, R.,A Model Algorithm for Composite Nondifferentiable Optimization Problems, Mathematical Programming Study No. 10, pp. 67-76, 1982. · Zbl 0478.90063
[10] Hald, J., andMadsen, K.,Combined LP and Quasi-Newton Methods for Minimax Optimization, Mathematical Programming, Vol. 20, pp. 49-62, 1981. · Zbl 0441.90097 · doi:10.1007/BF01589332
[11] Han, S. P.,Variable Metric Methods for Minimizing a Class of Nondifferentiable Functions, Mathematical Programming, Vol. 20, pp. 1-13, 1981. · Zbl 0441.90095 · doi:10.1007/BF01589328
[12] Murray, W., andOverton, M. L.,A Projected Lagrangian Algorithm for Nonlinear Minimax Optimization, SIAM Journal on Scientific and Statistical Computing, Vol. 1, pp. 345-370, 1980. · Zbl 0461.65052 · doi:10.1137/0901025
[13] Fletcher, R.,Practical Methods of Optimization, Vol. 1, Unconstrained Optimization, John Wiley and Sons, New York, New York, 1980. · Zbl 0439.93001
[14] Wolfe, P.,Sufficient Minimization of Piecewise Linear Univariate Functions, Nonsmooth Optimization, Edited by C. Lemarechal and R. Mifflin, Pergamon Press, Oxford, England, 1978. · Zbl 0412.90047
[15] Murray, W., andOverton, M. L.,Steplength Algorithms for Minimizing a Class of Nondifferentiable Functions, Computing, Vol. 23, pp. 309-331, 1979. · Zbl 0445.65060 · doi:10.1007/BF02254861
[16] Fletcher, R.,Numerical Experiments with an Exact L 1-Penalty Function, Nonlinear Programming 4, Edited by O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, Academic Press, New York, New York, pp. 99-129, 1981.
[17] Pshenichnyi, V. N.,Nonsmooth Optimization and Nonlinear Programming, Nonsmooth Optimization, Edited by C. Lemarechal and R. Mifflin, Pergamon Press, Oxford, England, 1978.
[18] Gill, P. E., andMurray, W.,The Computation of Lagrange Multiplier Estimates for Constrained Optimization, Mathematical Programming, Vol. 17, pp. 32-60, 1979. · Zbl 0423.90073 · doi:10.1007/BF01588224
[19] Coleman, T. F., andConn, R. R.,Nonlinear Programming via an Exact Penalty Function: Asymptotic Analysis, Mathematical Programming, Vol. 24, pp. 123-136, 1982. · Zbl 0501.90078 · doi:10.1007/BF01585100
[20] Coleman, T. F., andConn, A. R.,Nonlinear Programming via an Exact Penalty Function: Global Analysis, Mathematical Programming, Vol. 24, pp. 137-161, 1982. · Zbl 0501.90077 · doi:10.1007/BF01585101
[21] Gill, P. E., andMurray, W.,Numerically Stable Methods for Quadratic Programming, Mathematical Programming, Vol. 14, pp. 349-372, 1978. · Zbl 0374.90054 · doi:10.1007/BF01588976
[22] Powell, M. J. D.,A Fast Algorithm for Nonlinearly Constrained Optimization Calculations, Numerical Analysis, Dundee 1977, Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, pp. 144-157, 1977.
[23] Powell, M. J. D.,A Hybrid Method for Nonlinear Equations, Numerical Methods for Nonlinear Equations, Edited by P. Rabinowitz, Gordon and Breach, London, England, 1970. · Zbl 0277.65028
[24] Mayne, D. Q.,On the Use of Exact Penalty Functions to Determine Steplength in Optimization Algorithms, Numerical Analysis, Dundee 1979, Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, 1980.
[25] Chamberlain, R. M., Powell, M. J. D., Lemarechal, C., andPedersen, H. C.,The Watchdog Technique for Forcing Convergence in Algorithms for Constrained Optimization, Mathematical Programming Study No. 16, pp. 1-17, 1982. · Zbl 0477.90072
[26] Charalambous, C., andBandler, J. W.,Nonlinear Minimax Optimization as a Sequence of Least pth Optimization with Finite Values of p, International Journal of Systems Science, Vol. 7, pp. 377-394, 1976. · Zbl 0349.90108 · doi:10.1080/00207727608941924
[27] Powell, M. J. D.,Algorithms for Nonlinear Constraints That Use Lagrangian Functions, Mathematical Programming, Vol. 14, pp. 224-248, 1978. · Zbl 0383.90092 · doi:10.1007/BF01588967
[28] Rosenbrock, H. H.,An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal, Vol. 3, pp. 175-184, 1960. · doi:10.1093/comjnl/3.3.175
[29] Barrodale, I., Powell, M. J. D., andRoberts, E. D. K.,The Differential Correction Algorithm for Rational L ?-Approximation, SIAM Journal on Numerical Analysis, Vol. 7, pp. 493-504, 1972. · Zbl 0251.65008 · doi:10.1137/0709044
[30] Rosen, J. B., andSuzuki, S.,Construction of Nonlinear Programming Test Problems, Communications of the Association of Computing Machinery, Vol. 8, p. 113, 1965.
[31] Colville, A. R.,A Comparative Study on Nonlinear Programming Codes, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, Report No. 320-2949, 1968. · Zbl 0224.90069
[32] Freudenstein, F., andRoth, B.,Numerical Solution of Systems of Nonlinear Equations, Journal of the Association of Computing Machinery, Vol. 10, pp. 550-556, 1963. · Zbl 0131.33703
[33] Fletcher, R.,An Ideal Penalty Function for Constrained Optimization, Journal of the Institute of Mathematics and Its Applications, Vol. 15, pp. 319-342, 1975. · Zbl 0325.90056 · doi:10.1093/imamat/15.3.319
[34] Coleman, T. F., andSorensen, D. C.,A Note on the Computation of an Orthogonal Basis for the Null Space of a Matrix, Mathematical Programming, Vol. 29, pp. 234-242, 1984. · Zbl 0539.65020 · doi:10.1007/BF02592223
[35] Fletcher, R.,Second-Order Corrections for Nondifferentiable Optimization, Numerical Analysis, Dundee 1981, Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, pp. 85-114, 1982.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.