Large scale semidefinite programming: simplicity, conditioning, and an efficient algorithm

Abstract

This thesis studies large scale semidefinite programming arising from modern applications. We first identify a set of regularity conditions, which we call simplicity, and show it holds in both a generic sense and in many practical applications. Next, based on simplicity, we derive conditioning results: error bounds and sensitivity of solution. Finally, we design an algorithm that is provably computationally efficient in terms of storage and time under simplicity.

这篇博士论文讨论现代应用中的大规模半正定规划。我们首先确认一组叫做质朴性的正则条件。质朴性条件不仅在某种一般意义下总是成立，而且也在特定的应用中成立。 接着，基于质朴性，我们推出一系列适定性结果：包括误差界和解的敏感性界。 最后，我们设计一个基于质朴性的算法。这个算法可被证明在时间和空间都是有效率的。