The Low Order-Value Optimization (LOVO) problem involves minimizing the minimum among a finite number of function values within a feasible set. LOVO has several practical applications such as robust parameter estimation, protein alignment, portfolio optimization, among others. In this work, we are interested in the constrained nonlinear optimization LOVO problem of minimizing the minimum between a finite number of function values subject to a nonempty closed convex set where each function is a black-box and continuously differentiable, but the derivatives are not available. We develop the first derivative-free trust-region algorithm for constrained LOVO problems with convergence to weakly critical points. Under suitable conditions, we establish the global convergence of the algorithm and also its worst-case iteration complexity analysis. An initial open-source implementation using only linear interpolation models is developed. Extensive numerical experiments and comparison with existing alternatives show the properties and the efficiency of the proposed approach when solving LOVO problems.

翻译：低阶值优化问题涉及在可行集内最小化有限个函数值中的最小值。LOVO问题具有多种实际应用，如鲁棒参数估计、蛋白质对齐、投资组合优化等。本文关注约束非线性LOVO优化问题，即在非空闭凸集上最小化有限个函数值中的最小值，其中每个函数均为黑箱且连续可微，但其导数不可用。我们针对约束LOVO问题开发了首个无导数信赖域算法，该算法可收敛至弱临界点。在适当条件下，我们证明了算法的全局收敛性，并进行了最坏情况迭代复杂度分析。开发了一个仅使用线性插值模型的开源初始实现。大量数值实验及与现有替代方法的比较表明，所提方法在求解LOVO问题时具有良好的特性与效率。