MATRO: Metric-Aware Fully Quadratic Trust Regions for Derivative-Free Optimization

Model-based derivative-free trust-region methods build local models from function values and accept trial steps only where these models are expected to be reliable. This paper studies the shape of that trusted region. When a black-box objective is badly scaled or locally anisotropic, a Euclidean ball can be forced by the steepest local direction and can therefore restrict progress along directions of slow variation. We propose MATRO (Metric-Aware Trust-Region Optimization), a fully quadratic interpolation framework in which the trust region is the ellipsoid s^T M_k s <= Delta_k^2. The method is built in two layers. First, for any positive definite metric M_k, the induced variable y = M_k^{1/2} s converts the ellipsoidal subproblem into a standard Euclidean trust-region subproblem. Model decrease, ratio tests, radius updates, and fully quadratic interpolation theory can then be stated in induced coordinates under a uniform metric contract. Second, the metric is selected from the Hessian of the interpolation model. For positive definite quadratics, the volume-normalized curvature metric is the unique shape that makes the induced Hessian isotropic, and the corresponding metric trust-region step is a truncated Newton step. For indefinite fitted Hessians, an absolute-curvature metric balances curvature magnitudes while preserving the signs of the model curvature. Under the standard fully quadratic assumptions and the metric contract, MATRO retains the first-order evaluation-complexity order O(n^2 epsilon^{-2}) for full quadratic interpolation. Experiments on More-Wild benchmarks, controlled anisotropy tests, and two-dimensional trajectories show that curvature-shaped trust regions are most useful when the interpolation Hessian captures a stable local anisotropy, while their dense linear-algebra cost is most visible at loose accuracies or on inexpensive analytic tests.