A vertex exchange method is proposed for solving the strongly convex
quadratic program subject to the generalized simplex constraint. We conduct
rigorous convergence analysis for the proposed algorithm and demonstrate its
essential roles in solving some important classes of constrained convex
optimization. To get a feasible initial point to execute the algorithm, we also
present and analyze a highly efficient semismooth Newton method for computing
the projection onto the generalized simplex. The excellent practical
performance of the proposed algorithms is demonstrated by a set of extensive
numerical experiments. Our theoretical and numerical results further motivate
the potential applications of the considered model and the proposed algorithms.

提出了一种顶点交换方法，用于解决满足广义单纯形约束的强凸二次规划问题。通过对该算法进行严格收敛性分析，证明了它在解决某些重要类别的约束凸优化中的关键作用。为了获得算法执行的可行初始点，还提出并分析了一种高效的半光滑牛顿法，用于计算广义单纯形上的投影。通过一系列广泛的数值实验，展示了所提算法的出色实际性能。我们的理论和数值结果进一步激发了所考虑模型和所提算法的潜在应用。

一类二次规划问题的顶点交换方法

Vertex Exchange Method for a Class of Quadratic Programming Problems

Recently, several works have shown that natural modifications of the
classical conditional gradient method (aka Frank-Wolfe algorithm) for
constrained convex optimization, provably converge with a linear rate when: i)
the feasible set is a polytope, and ii) the objective is smooth and
strongly-convex. However, all of these results suffer from two significant
shortcomings: large memory requirement due to the need to store an explicit
convex decomposition of the current iterate, and as a consequence, large
running-time overhead per iteration, and worst case convergence rate that
depends unfavorably on the dimension.
In this work we present a new conditional gradient variant and a
corresponding analysis that improves on both of the above shortcomings. In
particular: both memory and computation overheads are only linear in the
dimension. Moreover, in case the optimal solution is sparse, the new
convergence rate replaces a factor which is at least linear in the dimension in
previous works, with a linear dependence on the number of non-zeros in the
optimal solution.
At the heart of our method, and corresponding analysis, is a novel way to
compute decomposition-invariant away-steps. While our theoretical guarantees do
not apply to any polytope, they apply to several important structured polytopes
that capture central concepts such as paths in graphs, perfect matchings in
bipartite graphs, marginal distributions that arise in structured prediction
tasks, and more. Our theoretical findings are complemented by empirical
evidence which shows that our method delivers state-of-the-art performance.

提出了一种改进的条件梯度方法来解决约束凸优化问题，针对多面体进行了相应的分析及优化，降低了每次迭代时的计算及内存开销，并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。

结构多面体的线性内存和分解不变线性收敛条件梯度算法

Linear-memory and Decomposition-invariant Linearly Convergent  Conditional Gradient Algorithm for Structured Polytopes

We propose a new primal-dual algorithmic framework for a prototypical
constrained convex optimization template. The algorithmic instances of our
framework are universal since they can automatically adapt to the unknown
Holder continuity degree and constant within the dual formulation. They are
also guaran- teed to have optimal convergence rates in the objective residual
and the feasibility gap for each Holder smoothness degree. In contrast to
existing primal-dual algorithms, our framework avoids the proximity operator of
the objective function. We instead leverage computationally cheaper,
Fenchel-type operators, which are the main workhorses of the generalized
conditional gradient (GCG)-type methods. In contrast to the GCG-type methods,
our framework does not require the objective function to be differentiable, and
can also process additional general linear inclusion constraints, while
guarantees the convergence rate on the primal problem

提出一种新的原始对偶算法框架，以解决约束的凸优化问题，具有优秀的收敛速度和更高效的计算方式。