论文标题
通过极点采样的记忆有效的结构化凸优化
Memory-efficient structured convex optimization via extreme point sampling
论文作者
论文摘要
当解决大规模凸优化问题（例如半决赛程序（SDPS））时，内存是一个关键的计算瓶颈。在本文中，我们专注于存储$ n \ times n $矩阵决策变量的制度。为了解决此制度中的SDP，我们开发了一种随机算法，该算法返回一个随机矢量，其协方差矩阵几乎是可行的，并且对于SDP而言非常优势。我们通过修改Frank-Wolfe算法以系统地替换矩阵迭代，以随机矢量迭代来展示如何开发这种算法。作为这种方法的应用，我们将展示如何使用$ \ Mathcal {O}（o}（n）$内存，除了存储问题实例所需的内存外，还使用$ \ Mathcal {o}（n）$内存来实现\ textsc {maxcut}的goemans-williamson近似算法。然后，我们扩展了处理更广泛的结构化凸优化问题的方法，以可行区域的随机极端点代替决策变量。
Memory is a key computational bottleneck when solving large-scale convex optimization problems such as semidefinite programs (SDPs). In this paper, we focus on the regime in which storing an $n\times n$ matrix decision variable is prohibitive. To solve SDPs in this regime, we develop a randomized algorithm that returns a random vector whose covariance matrix is near-feasible and near-optimal for the SDP. We show how to develop such an algorithm by modifying the Frank-Wolfe algorithm to systematically replace the matrix iterates with random vectors. As an application of this approach, we show how to implement the Goemans-Williamson approximation algorithm for \textsc{MaxCut} using $\mathcal{O}(n)$ memory in addition to the memory required to store the problem instance. We then extend our approach to deal with a broader range of structured convex optimization problems, replacing decision variables with random extreme points of the feasible region.
