Approximating Parameterized Convex Optimization Problems
Approximating Parameterized Convex Optimization Problems
复制标题
DOI：
10.1145/2390176.2390186
复制
发表时间：
2012-12-01
影响因子：
1.3
通讯作者：
Laue, Soeren
中科院分区：
文献类型：
--
作者：
Giesen, Joachim;Jaggi, Martin;Laue, Soeren
我们考虑单位单形上依赖于一个参数的参数化凸优化问题。我们提供了一种简单而有效的方案来维护整个参数路径上的epsilon近似解(以及相应的epsilon-coset)。证明了该方法的正确性和最优性。抽象的参数化优化问题的实际相关实例是例如支持向量机的正则化路径、多核学习和移动点的最小包围球。
We consider parameterized convex optimization problems over the unit simplex, that depend on one parameter. We provide a simple and efficient scheme for maintaining an epsilon-approximate solution (and a corresponding epsilon-coreset) along the entire parameter path. We prove correctness and optimality of the method. Practically relevant instances of the abstract parameterized optimization problem are for example regularization paths of support vector machines, multiple kernel learning, and minimum enclosing balls of moving points.