solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看5961次
Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting. (arXiv:1810.05231v1 [math.OC])
来源于:arXiv
In contrast with many other convex optimization classes, state-of-the-art
semidefinite programming solvers are yet unable to efficiently solve large
scale instances. This work aims to reduce this scalability gap by proposing a
novel proximal algorithm for solving general semidefinite programming problems.
The proposed methodology, based on the primal-dual hybrid gradient method,
allows the presence of linear inequalities without the need of adding extra
slack variables and avoids solving a linear system at each iteration. More
importantly, it does simultaneously compute the dual variables associated with
the linear constraints. The main contribution of this work is to achieve a
substantial speedup by effectively adjusting the proposed algorithm in order to
exploit the low-rank property inherent to several semidefinite programming
problems. This proposed modification is the key element that allows the
operator splitting method to efficiently scale to larger instances. Convergence
guaran 查看全文>>