Model-Based Derivative-Free Methods for Convex-Constrained Optimization

2021/11/09 by Hough, Matthew, Roberts, Lindon · 4 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2111.05443

Abstract

We present a model-based derivative-free method for optimization subject to general convex constraints, which we assume are unrelaxable and accessed only through a projection operator that is cheap to evaluate. We prove global convergence and a worst-case complexity of O(ε^-2) iterations and objective evaluations for nonconvex functions, matching results for the unconstrained case. We introduce new, weaker requirements on model accuracy compared to existing methods. As a result, sufficiently accurate interpolation models can be constructed only using feasible points. We develop a comprehensive theory of interpolation set management in this regime for linear and composite linear models. We implement our approach for nonlinear least-squares problems and demonstrate strong practical performance compared to general-purpose solvers.

Cited by

• A derivative-free trust-region approach for Low Order-Value Optimization problems
• A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization
• A derivative-free regularization algorithm for equality constrained nonlinear least squares problems
• A Model-Based Derivative-Free Optimization Algorithm for Partially Separable Problems

Related

• Model Construction for Convex-Constrained Derivative-Free Optimization
• A Feasible Method for Constrained Derivative-Free Optimization
• Derivative-Free Bound-Constrained Optimization for Solving Structured Problems with Surrogate Models
• Compositions of Convex Functions and Fully Linear Models
• A constraint-based approach to function interpolation, with application to performance estimation for weakly convex optimisation