半定规划随机非凸优化的全局线性收敛理论

本文主要探讨了半定规划（Semidefinite Programming, SDP）中的随机非凸优化问题，焦点在于全球线性收敛性。随着低秩分解技术在随机凸SDP优化中的广泛应用，这种非凸重构方法因其显著的实践效率和可扩展性而受到广泛关注。相比于原始的凸形式，非凸模型通常涉及更少的变量，使得处理大规模问题成为可能，涉及上百万个变量的情况也不再受限。 然而，这种优势也带来了新的挑战：即使在实际应用中展现出成功，如何确保在满足统计最优精度的情况下，非凸的随机算法能够找到全局最小解，即所谓的“population minimizer”。这个问题在理论层面尚未得到充分解答。 本文的贡献是解决了这一难题，作者Jinshan Zeng、Ke Ma和Yuan Yao提出了将随机梯度下降（Stochastic Gradient Descent, SGD）方法应用于原始凸问题的非凸重构形式。他们证明，通过采用固定步长，SGD能够在全局范围内实现线性收敛，这意味着算法将以指数速度逼近最优的统计精度，从而找到全局最优解。这是一项重要的理论成果，为理解和改进非凸随机优化算法的稳定性提供了坚实的基础，对于推动半定规划在大数据和复杂优化问题中的实际应用具有深远影响。