Improved Algorithms Based on Trust Region Framework for Solving Unconstrained Derivative Free Optimization Problems

This paper is devoted to developing new derivative-free optimization (DFO) methods for solving optimization problems where derivative information is not available or cannot be calculated numerically. To overcome the computational difficulties arising from time-consuming estimations of the objective function, we propose two algorithms. One algorithm is a variant of the surrogate model-based DFO algorithm under the trust region method, where the surrogate model is formulated through sparse low-rank interpolation and quadratic polynomial interpolation. This algorithm serves as a comparative baseline. The second algorithm leverages the characteristics of the sparse regression model, which can handle sparsity and noise issues, to construct the surrogate model. The coefficients of the sparse surrogate model are then estimated using the alternating direction method of multipliers and refined through a correction strategy based on the R-square. Finally, numerical results, evaluated in terms of performance and data profiles, demonstrate the effectiveness and competitiveness of the proposed algorithms.