×

A derivative-free algorithm for linearly constrained optimization problems. (English) Zbl 1304.90193

Summary: Based on the NEWUOA algorithm, a new derivative-free algorithm is developed, named LCOBYQA. The main aim of the algorithm is to find a minimizer \(x^{*} \in\mathbb{R}^{n}\) of a non-linear function, whose derivatives are unavailable, subject to linear inequality constraints. The algorithm is based on the model of the given function constructed from a set of interpolation points. LCOBYQA is iterative, at each iteration it constructs a quadratic approximation (model) of the objective function that satisfies interpolation conditions, and leaves some freedom in the model. The remaining freedom is resolved by minimizing the Frobenius norm of the change to the second derivative matrix of the model. The model is then minimized by a trust-region subproblem using the conjugate gradient method for a new iterate. At times the new iterate is found from a model iteration, designed to improve the geometry of the interpolation points. Numerical results are presented which show that LCOBYQA works well and is very competing against available model-based derivative-free algorithms.

MSC:

90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buckley, A.G., Jenning, L.S.: Test functions for unconstrained minimization. Technical report, CS-3, Dalhousie University, Canada (1989)
[2] Conn, A., Gould, N., Toint, Ph.: Trust Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[3] Conn, A.; Sheinberg, K.; Toint, Ph.; Pillo, G. Di. (ed.); Giannessi, F. (ed.), An algorithm using quadratic interpolation for unconstrained derivative-free optimization, 27-47 (1996), New York · Zbl 0976.90102
[4] Conn, A., Sheinberg, K., Toint, Ph.: A derivative free optimization (DFO) algorithm. Report 98(11) (1998)
[5] Dong, S.: Methods for Constrained Optimization. Springer, Berlin (2002). 18: project
[6] Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, New York (1987) · Zbl 0905.65002
[7] Frank, V., Bersini, H.B.: CONDOR, a new parallel constrained extension of Powell’s UOBYQA algorithm: experimental results and comparison with DFO algorithm. J. Comput. Appl. Math. 181, 157-175 (2005) · Zbl 1072.65088
[8] Gay, D.M., David, M.: In: Lecture Note in Mathematics, vol. 1066, pp. 74-105. Springer, Berlin (1984)
[9] Gill, P.E., Murray, W., Wright, M.H.: In: Inertia-Controlling Methods for General Quadratic Programming, vol. 33, pp. 1-36. SIAM, Philadelphia (1991) · Zbl 0734.90062
[10] Gumma, E.: A derivative-free algorithm for linearly constrained optimization problems. Ph.D., University of Khartoum, Sudan (2011) · Zbl 1304.90193
[11] Hock, W., Schittkowski, K.: In: Test Example for Nonlinear Programming Codes. Lecture Notes en Economics and Mathematical Systems, vol. 187 (1981) · Zbl 0452.90038
[12] Igor, G., Nash, G., Sofer, A.: In: Linear and Nonlinear Programming. SIAM, Philadelphia (2009) · Zbl 1159.90002
[13] Ju, Z., Wang, C., Jiguo, J.: Combining trust region and line search algorithm for equality constrained optimization. Appl. Math. Comput. 14(1-2), 123-136 (2004) · Zbl 1053.90122
[14] Powell, M. J.D.; Gomez, S. (ed.); Hennart, J. P. (ed.), A direct search optimization method that model the objective function and constrained functions by linear interpolation, Oaxaca, Mexico
[15] Powell, M.J.D.: UOBYQA: unconstrained optimization by quadratic approximation. Math. Program. 92, 555-582 (2002) · Zbl 1014.65050
[16] Powell, M.J.D.: Least Frobenius norm updating for quadratic models that satisfy interpolation conditions. Math. Program. 100, 183-215 (2004) · Zbl 1146.90526
[17] Powell, M. J.D.; pillo, G. (ed.); Roma, M. (ed.), The NEWUOA software for unconstrained optimization without derivative (2006), New York · Zbl 1108.90005
[18] Powell, M.J.D.: Development of NEWUOA for minimization without derivatives. IMA J. Numer. Anal. 28, 649-664 (2008) · Zbl 1154.65049
[19] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivative. Technical report, 2009/NA06, CMS University of Cambridge (2009) · Zbl 0274.90060
[20] Toint, Ph.: Some numerical results using a sparse matrix updating formula in unconstrained optimization. Math. Comput. 32, 839-859 (1987) · Zbl 0381.65036
[21] Winfield, D.: Function and Functional Optimization by Interpolation in Data Table. Ph.D., Harvard University, Cambridge, USA (1969) · Zbl 0274.90060
[22] Winfield, D.: Function minimization by interpolation in 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.