We analyze the least norm type underdetermined quadratic interpolation model proposed by Conn and Toint [An algorithm using quadratic interpolation for unconstrained derivative free optimization, 1996] from the perspective of the property of trust-region iteration. We find the Karush--Kuhn--Tucker multiplier's nondeterminacy when constructing a quadratic model considering the trust-region iteration in the case where the current iteration point is on the boundary of the trust region. The lack of the quadratic model's uniqueness caused by the Karush--Kuhn--Tucker multiplier's nondeterminacy leads us to propose a new model to consequently improve the model by selectively treating the previously obtained underdetermined quadratic model as a quadratic model or a linear one. A new derivative-free method is given by introducing the improved underdetermined quadratic interpolation model considering the optimality of the model based on the trust-region iteration. The theoretical motivation, property, computational details, and the quadratic model's formula derived from the Karush--Kuhn--Tucker conditions are discussed. The formula is implementation-friendly for the existing model-based derivative-free methods. The numerical results with released codes support the advantages of our quadratic model in the derivative-free optimization methods. To the best of our knowledge, this is the first work considering the property of trust-region iteration and the model's optimality when constructing the underdetermined quadratic model for derivative-free trust-region methods.

Publication:

SIAM J.OPTIM. Vol.35,No.2,pp.1110-1133

http://dx.doi.org/10.1137/23M1582023

Author:

PENGCHENG XIE

Corresponding author.

Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720 USA

pxie@lbl.gov, pxie98@gmail.com

YA-XIANG YUAN

Institute of Computational Math and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing 100190, People's Republic of China

yyx@lsec.cc.ac.cn