CLARSTA: A random subspace trust-region algorithm for convex-constrained derivative-free optimization

2025/06/25 by Yiwen Chen, Chen, Yiwen, Warren Hare +3
Computer Science · Mathematics · #65K05 #90C06 #90C56 #Advanced Optimization Algorithms Research #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2506.20335

openalex publication_date 2025/06/25 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28

Abstract

This paper proposes a random subspace trust-region algorithm for general convex-constrained derivative-free optimization (DFO) problems. Similar to previous random subspace DFO methods, the convergence of our algorithm requires a certain accuracy of models and a certain quality of subspaces. For model accuracy, we define a new class of models that is only required to provide reasonable accuracy on the projection of the constraint set onto the subspace. We provide a new geometry measure to make these models easy to analyze, construct, and manage. For subspace quality, we use the concentration of measure on the Grassmann manifold to provide a method to sample subspaces that preserve the first-order criticality measure by a certain fraction with a certain probability lower bound. Based on all these new theoretical results, we present an almost-sure global convergence and a worst-case complexity analysis of our algorithm. Numerical experiments on problems with dimensions up to 10000 demonstrate the reliable performance of our algorithm in high dimensions.

Citations

• Randomized Subspace Derivative-Free Optimization with Quadratic Models and Second-Order Convergence
• Model Construction for Convex-Constrained Derivative-Free Optimization
• Q-fully Quadratic Modeling and its Application in a Random Subspace Derivative-free Method
• PDFO: A Cross-Platform Package for Powell's Derivative-Free Optimization Solvers
• Randomised subspace methods for non-convex optimization, with applications to nonlinear least-squares
• Higher order concentration on Stiefel and Grassmann manifolds
• On random embeddings and their application to optimisation
• Direct search based on probabilistic descent in reduced spaces
• Model-Based Derivative-Free Methods for Convex-Constrained Optimization
• Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization
• A Survey of Convolutional Neural Networks: Analysis, Applications, and Prospects
• A Survey of Convolutional Neural Networks: Analysis, Applications, and Prospects
• Black-Box Optimization in Machine Learning with Trust Region Based Derivative Free Algorithm

Related

• Q-fully Quadratic Modeling and its Application in a Random Subspace Derivative-free Method
• Randomized Subspace Derivative-Free Optimization with Quadratic Models and Second-Order Convergence
• Two-level trust-region method with random subspaces
• A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization
• An optimally fast objective-function-free minimization algorithm using random subspaces