Derivative-free separable quadratic modeling and cubic regularization for unconstrained optimization

We present a derivative-free separable quadratic modeling and cubic regularization technique for solving smooth unconstrained minimization problems. The derivative-free approach is mainly concerned with building a quadratic model that could be generated by numerical interpolation or using a minimum Frobenius norm approach, when the number of points available does not allow to build a complete quadratic model. This model plays a key role to generate an approximated gradient vector and Hessian matrix of the objective function at every iteration. We add a specialized cubic regularization strategy to minimize the quadratic model at each iteration, that makes use of separability. We discuss convergence results, including worst case complexity, of the proposed schemes to first-order stationary points. Some preliminary numerical results are presented to illustrate the robustness of the specialized separable cubic algorithm.

Automated summary

We propose a derivative-free separable quadratic modeling and cubic regularization technique for solving smooth unconstrained minimization problems. The approach focuses on building a quadratic model, which can be generated by numerical interpolation or using a minimum Frobenius norm approach, when there are not enough points available to build a complete quadratic model. This model plays a crucial role in generating the approximate gradient vector and Hessian matrix of the objective function at each iteration. We also introduce a specialized cubic regularization strategy to minimize the quadratic model at each iteration, leveraging separability. Convergence results, including worst case complexity, are discussed for reaching first-order stationary points. Preliminary numerical results are presented to demonstrate the robustness of the specialized separable cubic algorithm.