×

CONDOR, a new parallel, constrained extension of Powell’s UOBYQA algorithm: Experimental results and comparison with the DFO algorithm. (English) Zbl 1072.65088

Summary: This paper presents an algorithmic extension of M. J. D. Powell’s UOBYQA algorithm (Unconstrained Optimization BY Quadratical Approximation) [Math. Program 92, No. 3, 555–582 (2002; Zbl 1014.65050)]. We start by summarizing the original algorithm of Powell and by presenting it in a more comprehensible form. Thereafter, we report comparative numerical results between UOBYQA, DFO and a parallel, constrained extension of UOBYQA that will be called in the paper CONDOR (COnstrained, Non-linear, Direct, parallel Optimization using trust Region method for high-computing load function). The experimental results are very encouraging and validate the approach. They open wide possibilities in the field of noisy and high-computing-load objective functions optimization (from 2 min to several days) like, for instance, industrial shape optimization based on computation fluid dynamic codes or partial differential equations solvers. Finally, we present a new, easily comprehensible and fully stand-alone implementation in C++ of the parallel algorithm.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
65Y05 Parallel numerical computation

Citations:

Zbl 1014.65050
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aemdesign, URL: http://www.aemdesign.com/FSQPapplref.htm; Aemdesign, URL: http://www.aemdesign.com/FSQPapplref.htm
[2] P.T. Boggs, J.W. Tolle, Sequential quadratic programming, Acta Numer. (1996) 1-000.; P.T. Boggs, J.W. Tolle, Sequential quadratic programming, Acta Numer. (1996) 1-000. · Zbl 0828.65060
[3] A.J. Booker, A.R. Conn, J.E. Dennis Jr., P.D. Frank, M. Trosset, V. Torczon, M.W. Trosset, Global modeling for optimization: Boeing/ibm/rice collaborative project 1995 Final Report, Technical Report ISSTECH-95-032, Boeing Information Support Services, Research and Technology, Box 3707, M/S 7L-68, Seattle, WA 98124, December 1995.; A.J. Booker, A.R. Conn, J.E. Dennis Jr., P.D. Frank, M. Trosset, V. Torczon, M.W. Trosset, Global modeling for optimization: Boeing/ibm/rice collaborative project 1995 Final Report, Technical Report ISSTECH-95-032, Boeing Information Support Services, Research and Technology, Box 3707, M/S 7L-68, Seattle, WA 98124, December 1995.
[4] A.J. Booker, J.E. Dennis Jr., P.D. Frank, D.B. Serafini, V. Torczon, M.W. Trosset, Optimization using surrogate objectives on a helicopter test example, Comput. Methods Optimal Design Control (1998) 49-58.; A.J. Booker, J.E. Dennis Jr., P.D. Frank, D.B. Serafini, V. Torczon, M.W. Trosset, Optimization using surrogate objectives on a helicopter test example, Comput. Methods Optimal Design Control (1998) 49-58. · Zbl 0937.76067
[5] D.M. Bortz, C.T. Kelley, The simplex gradient and noisy optimization problems, Technical Report CRSC-TR97-27, North Carolina State University, Department of Mathematics, Center for Research in Scientific Computation, Box 8205, Raleigh, NC 27695-8205, September 1997.; D.M. Bortz, C.T. Kelley, The simplex gradient and noisy optimization problems, Technical Report CRSC-TR97-27, North Carolina State University, Department of Mathematics, Center for Research in Scientific Computation, Box 8205, Raleigh, NC 27695-8205, September 1997.
[6] Carter, R. G.; Gablonsky, J. M.; Patrick, A.; Kelley, C. T.; Eslinger, O. J., Algorithms for noisy problems in gas transmission pipeline optimization, Optim. Eng., 2, 139-157 (2001) · Zbl 1079.90624
[7] A.R. Conn, N.I.M. Gould, P.L. Toint, LANCELOT: a Fortran Package for Large-scale Non-linear Optimization (Release A), Springer Series in Computational Mathematics ed., Springer, HeidelBerg, Berlin, New York, 1992.; A.R. Conn, N.I.M. Gould, P.L. Toint, LANCELOT: a Fortran Package for Large-scale Non-linear Optimization (Release A), Springer Series in Computational Mathematics ed., Springer, HeidelBerg, Berlin, New York, 1992. · Zbl 0761.90087
[8] A.R. Conn, N.I.M. Gould, P.L. Toint, A derivative free optimization algorithm in practice, Technical Report, Report No. 98/11, Department of Mathematics, University of Namur, Belgium, 1998.; A.R. Conn, N.I.M. Gould, P.L. Toint, A derivative free optimization algorithm in practice, Technical Report, Report No. 98/11, Department of Mathematics, University of Namur, Belgium, 1998.
[9] A..R. Conn, N.I.M. Gould, P.L. Toint, Trust-region Methods, MPS-SIAM Series on Optimization ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 2000, pp. 307-323 (Chapter 9: conditional model).; A..R. Conn, N.I.M. Gould, P.L. Toint, Trust-region Methods, MPS-SIAM Series on Optimization ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 2000, pp. 307-323 (Chapter 9: conditional model). · Zbl 0958.65071
[10] A.R. Conn, N.I.M. Gould, P.L. Toint, The ideal trust region, in: Trust-region Methods, MPS-SIAM Series on Optimization ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 2000, pp. 236-237.; A.R. Conn, N.I.M. Gould, P.L. Toint, The ideal trust region, in: Trust-region Methods, MPS-SIAM Series on Optimization ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 2000, pp. 236-237. · Zbl 0958.65071
[11] A.R. Conn, N.I.M. Gould, P.L. Toint, Note on convex models, in: Trust-region Methods, MPS-SIAM Series on Optimization ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 2000, pp. 324-337.; A.R. Conn, N.I.M. Gould, P.L. Toint, Note on convex models, in: Trust-region Methods, MPS-SIAM Series on Optimization ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 2000, pp. 324-337.
[12] Conn, A. R.; Scheinberg, K.; Toint, P. L., Recent progress in unconstrained nonlinear optimization without derivatives, Math. Programming, 79, 397-414 (1997) · Zbl 0887.90154
[13] Cosentino, R.; Alsalihi, Z.; Van Den Braembussche, R., Expert system for radial impeller optimisation, (Proceedings of the Fourth European Conference on Turbomachinery. Proceedings of the Fourth European Conference on Turbomachinery, ATI-CST-039/01, Florence, Italy (2001))
[14] De Boor, C.; Ron, A. A., On multivariate polynomial interpolation, Constr. Approx., 6, 287-302 (1990) · Zbl 0719.41006
[15] J.E. Dennis Jr., R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Classics in Applied Mathematics, 16 ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 1996.; J.E. Dennis Jr., R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Classics in Applied Mathematics, 16 ed., SIAM Society for Industrial & Applied Mathematics, Englewood Cliffs, NJ, 1996.
[16] Dennis, J. E.; Torczon, V., Direct search methods on parallel machines, SIAM J. Optim., 1, 4, 448-474 (1991) · Zbl 0754.90051
[17] Dennis, J. E.; Welaker, H. F., Inaccurracy in quasi-Newton methodslocal improvement theorems, Math. Programming Stud., 22, 70-85 (1984)
[18] Fletcher, R., Practical Methods of Optimization (1987), Wiley-Interscience: Wiley-Interscience Great Britain · Zbl 0905.65002
[19] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPLA Modeling Language for Mathematical Programming (2002), Duxbury Press/Brooks/Cole Publishing Company
[20] P.E. Gill, W. Murray, M.A. Saunders, M.H. Wright, Users’s guide for npsol (version 4.0): a fortran package for non-linear programming, Technical Report, Report SOL 862, Department of Operations Research, Stanford University, Stanford, CA 94305, USA, 1986.; P.E. Gill, W. Murray, M.A. Saunders, M.H. Wright, Users’s guide for npsol (version 4.0): a fortran package for non-linear programming, Technical Report, Report SOL 862, Department of Operations Research, Stanford University, Stanford, CA 94305, USA, 1986.
[21] Gilmore, P.; Kelley, C. T., An implicit filtering algorithm for optimization of functions with many local minima, SIAM J. Optim., 5, 269-285 (1995) · Zbl 0828.65064
[22] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, USA · Zbl 0865.65009
[23] N.I.M. Gould, D. Orban, P.L. Toint, CUTEr (and SifDec), a constrained and unconstrained testing environment, revisited*, Technical Report, Report No. TR/PA/01/04, Cerfacs, 2001.; N.I.M. Gould, D. Orban, P.L. Toint, CUTEr (and SifDec), a constrained and unconstrained testing environment, revisited*, Technical Report, Report No. TR/PA/01/04, Cerfacs, 2001. · Zbl 1068.90526
[24] W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, 1981.; W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, 1981. · Zbl 0452.90038
[25] C.T. Kelley, Iterative Methods for Optimization, vol. 18, Frontiers in Applied Mathematics, 1999.; C.T. Kelley, Iterative Methods for Optimization, vol. 18, Frontiers in Applied Mathematics, 1999. · Zbl 0934.90082
[26] Lawson, C. L.; Hanson, R. J.; Kincaid, D.; Krogh, F. T., Basic linear algebra subprograms for FORTRAN usage, ACM Trans. Math. Soft., 5, 308-323 (1979) · Zbl 0412.65022
[27] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Statist. Comput., 4, 3, 553-572 (1983) · Zbl 0551.65042
[28] Panier, E. R.; Tits, A. L., On combining feasibility, descent and superlinear convergence in inequality contrained optimization, Math. Programming, 59, 261-276 (1995) · Zbl 0794.90068
[29] Pazzi, S.; Martelli, F.; Michelassi, V.; Berghen, F. V.; Bersini, H., Intelligent performance CFD optimisation of a centrifugal impeller, (Proceedings of the Fifth European Conference on Turbomachinery. Proceedings of the Fifth European Conference on Turbomachinery, Prague, CZ (March 2003))
[30] S. Pierret, R. Van den Braembussche, Turbomachinery blade design using a Navier-Stokes solver and artificial neural network, J. Turbomach. ASME 98-GT-4 (1998) (publication in the transactions of the ASME: J. Turbomach.).; S. Pierret, R. Van den Braembussche, Turbomachinery blade design using a Navier-Stokes solver and artificial neural network, J. Turbomach. ASME 98-GT-4 (1998) (publication in the transactions of the ASME: J. Turbomach.).
[31] V. Pediroda, M. Poian, C. Poloni, Multi objective optimisation examples: design of a laminar airfoil and of a composite rectangular wing, in: Genetic Algorithms for Optimisation in Aeronautics and Turbomachinery, von Karman Institute Lecture Series Monographs 200-07, 2000.; V. Pediroda, M. Poian, C. Poloni, Multi objective optimisation examples: design of a laminar airfoil and of a composite rectangular wing, in: Genetic Algorithms for Optimisation in Aeronautics and Turbomachinery, von Karman Institute Lecture Series Monographs 200-07, 2000.
[32] M.J.D. Powell, A direct search optimization method that models the objective and constraint functions by linar interpolation, in: S. Gomez, J.-P. Hennart (Eds.), Advances in Optimization and Numerical Analysis, Proceedings of the Sixth Workshop on Optimization and Numerical Analysis, Oaxaca, Mexico, vol. 275, Kluwer Academic Publishers, Dordrecht, NL, 1994, pp. 51-67.; M.J.D. Powell, A direct search optimization method that models the objective and constraint functions by linar interpolation, in: S. Gomez, J.-P. Hennart (Eds.), Advances in Optimization and Numerical Analysis, Proceedings of the Sixth Workshop on Optimization and Numerical Analysis, Oaxaca, Mexico, vol. 275, Kluwer Academic Publishers, Dordrecht, NL, 1994, pp. 51-67. · Zbl 0826.90108
[33] M.J.D. Powell. The use of band matrices for second derivative approximations in trust region algorithms, Technical Report No. DAMTP1997/NA12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 1997.; M.J.D. Powell. The use of band matrices for second derivative approximations in trust region algorithms, Technical Report No. DAMTP1997/NA12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 1997.
[34] M.J.D. Powell, On the Lagrange function of quadratic models that are defined by interpolation, Technical Report No. DAMTP2000/10, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 2000.; M.J.D. Powell, On the Lagrange function of quadratic models that are defined by interpolation, Technical Report No. DAMTP2000/10, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 2000.
[35] M.J.D. Powell, UOBYQA: Unconstrained optimization by quadratic approximation, Technical Report No. DAMTP2000/14, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 2000.; M.J.D. Powell, UOBYQA: Unconstrained optimization by quadratic approximation, Technical Report No. DAMTP2000/14, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 2000. · Zbl 1014.65050
[36] Powell, M. J.D., UOBYQAUnconstrained optimization by quadratic approximation, Math. Programming B, 92, 555-582 (2002) · Zbl 1014.65050
[37] M.J.D. Powell, On updating the inverse of a KKT matrix, Technical Report No. DAMTP2004/01, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 2004.; M.J.D. Powell, On updating the inverse of a KKT matrix, Technical Report No. DAMTP2004/01, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England, 2004.
[38] Sauer, T.; Xu, Y., On multivariate lagrange interpolation, Math. Comp., 64, 1147-1170 (1995) · Zbl 0823.41002
[39] Stoneking, D. E.; Bilbro, G. L.; Trew, R. J.; Gilmore, P.; Kelley, C. T., Yield optimization using a GaAs process simulator coupled to a physical device model, IEEE Trans. Microwave Theory Tech., 40, 1353-1363 (1992)
[40] F. Vanden Berghen, Intermediate report on the development of an optimization code for smooth, continuous objective functions when derivatives are not available, Technical Report, IRIDIA, Université Libre de Bruxelles, Belgium.; F. Vanden Berghen, Intermediate report on the development of an optimization code for smooth, continuous objective functions when derivatives are not available, Technical Report, IRIDIA, Université Libre de Bruxelles, Belgium.
[41] F. Vanden Berghen, Optimization algorithm for non-linear, constrained, derivative-free optimization of continuous, high-computing-load functions, Technical Report, IRIDIA, Université Libre de Bruxelles, Belgium, available at http://iridia.ulb.ac.be/\( \sim;\); F. Vanden Berghen, Optimization algorithm for non-linear, constrained, derivative-free optimization of continuous, high-computing-load functions, Technical Report, IRIDIA, Université Libre de Bruxelles, Belgium, available at http://iridia.ulb.ac.be/\( \sim;\)
[42] Wanga, J. F.; Periaux, J.; Sefriouib, M., Parallel evolutionary algorithms for optimization problems in aerospace engineering, J. Comput. Appl. Math., 149, 1, 155-169 (2002) · Zbl 1058.76053
[43] D. Winfield, Function and functional optimization by interpolation in data tables, Ph.D. Thesis, Harvard University, Cambridge, USA, 1969.; D. Winfield, Function and functional optimization by interpolation in data tables, Ph.D. Thesis, Harvard University, Cambridge, USA, 1969.
[44] Winfield, D., Function minimization by interpolation in a data table, J. Inst. Math. Appl., 12, 339-347 (1973) · Zbl 0274.90060
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.