| الوصف: |
We propose the pivoting meta algorithm (PM), a framework designed to enhance optimization algorithms that generate iterates as convex combinations of vertices of a feasible region $\mathcal{C}\subseteq \mathbb{R}^n$, including several variants of the Frank-Wolfe algorithm (FW). PM guarantees that the active set of the modified algorithm remains as small as guaranteed by Carath\'eodory's theorem. PM achieves this by reformulating the active set expansion task into an equivalent linear programming problem, which can be efficiently solved using a single pivot step akin to the primal simplex algorithm. We establish that PM bounds the cardinality of the active set by the dimension of $\mathcal{C}$ plus one, while preserving the convergence rate guarantees of a class of original algorithms, including various variants of the Frank-Wolfe algorithm. Furthermore, we establish the connection between PM and active set identification. Specifically, when $\mathcal{C}$ is a polytope and under mild assumptions, PM applied to the away-step Frank-Wolfe algorithm (AFW) or the blended pairwise Frank-Wolfe algorithm (BPFW) ensures that the active set size is at most the dimension of the optimal face plus one. To illustrate the practicality of PM, we provide algorithmic implementations for standard Frank-Wolfe variants and conduct a comprehensive numerical evaluation, demonstrating its effectiveness in inducing sparsity. |
