An optimal interpolation set for model-based derivative-free optimization methods

Abstract

This paper demonstrates the optimality of an interpolation set employed in derivative-free trust-region methods. This set is optimal in the sense that it minimizes the constant of well-poisedness in a ball centred at the starting point. It is chosen as the default initial interpolation set by many derivative-free trust-region methods based on underdetermined quadratic interpolation, including NEWUOA, BOBYQA, LINCOA, and COBYQA. Our analysis provides a theoretical justification for this choice.

KEYWORDS:

• Derivative-free optimization
• model-based methods
• underdetermined quadratic interpolation
• derivative-free symmetric Broyden update
• well-poisedness

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 90C56
• 41A10
• 65K05
• 90C30

Acknowledgements

This paper corresponds to Section 2.5 of the PhD thesis of Tom M. Ragonneau [24], co-supervised by Zaikun Zhang and Professor Xiaojun Chen from The Hong Kong Polytechnic University. Both authors are very grateful to Professor Chen for her support, encouragement, and guidance during the thesis. Zaikun Zhang would like to thank the late Professor Oleg Burdakov for his friendship.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Powell's BOBYQA code contains a comment that ‘choices that exceed 2n + 1 are not recommended’.

Additional information

Funding

This work was funded by the University Grants Committee of Hong Kong under projects PF18-24698 (Hong Kong PhD Fellowship Scheme), PolyU 253012/17P, PolyU 153054/20P, PolyU 153066/21P, and PolyU 153086/23P. It was also supported by The Hong Kong Polytechnic University under projects P0009767, P0038928, P0045598, and the CAS-Croucher Funding Scheme for ‘CAS AMSS-PolyU Joint Laboratory of Applied Mathematics: Nonlinear Optimization Theory, Algorithms and Applications’.

Notes on contributors

Tom M. Ragonneau

Tom M. Ragonneau obtained his PhD degree from The Hong Kong Polytechnic University in 2023. He is now a postdoctoral fellow of the CAS AMSS-PolyU Joint Laboratory of Applied Mathematics at The Hong Kong Polytechnic University.

Zaikun Zhang

Zaikun Zhang obtained his PhD degree from the Chinese Academy of Sciences in 2012. He worked at the University of Coimbra (Portugal) in 2012–2014 and then at Toulouse INP-ENSEEIHT (France) in 2014–2016 as a postdoctoral fellow. In 2016, he joined The Hong Kong Polytechnic University, and he is now an Assistant Professor at the Department of Applied Mathematics.