论文标题
用于结构化优化问题的无衍生化方法
A derivative-free method for structured optimization problems
论文作者
论文摘要
在数据科学和工程等领域，结构化优化问题无处不在。结构化优化的目标是使用一个规定的点集，称为原子，以最大程度地减少或最大化给定功能。在本文中，我们要在给定的一组原子的凸壳上最大程度地减少一个黑框函数，该问题可用于建模许多现实世界应用程序。我们专注于解决方案稀疏的问题，即可以作为组合中仅几个原子的适当凸组组合获得的解决方案，并提出了一种合适的无衍生性内部近似方法，可以很好地利用给定问题的结构。这使我们能够正确处理通常与无衍生算法相关的维数问题，从而获得了一种方法，可以很好地缩放问题的尺寸和原子的数量。我们分析了全球融合到固定点。此外，我们表明，在适当的假设下，所提出的算法在有限的许多迭代后识别最终溶液中零重量的特定原子集。最后，我们报告数值结果，显示了所提出的方法的有效性。
Structured optimization problems are ubiquitous in fields like data science and engineering. The goal in structured optimization is using a prescribed set of points, called atoms, to build up a solution that minimizes or maximizes a given function. In the present paper, we want to minimize a black-box function over the convex hull of a given set of atoms, a problem that can be used to model a number of real-world applications. We focus on problems whose solutions are sparse, i.e., solutions that can be obtained as a proper convex combination of just a few atoms in the set, and propose a suitable derivative-free inner approximation approach that nicely exploits the structure of the given problem. This enables us to properly handle the dimensionality issues usually connected with derivative-free algorithms, thus getting a method that scales well in terms of both the dimension of the problem and the number of atoms. We analyze global convergence to stationary points. Moreover, we show that, under suitable assumptions, the proposed algorithm identifies a specific subset of atoms with zero weight in the final solution after finitely many iterations. Finally, we report numerical results showing the effectiveness of the proposed method.
