提出一种新算法，可高效求解正交约束下的优化问题。
Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization
- 基于半定规划松弛与随机取样构造近似算法
- 在任意维度下保证1/3的近似比，且理论最优
- 适合研究组合优化与矩阵计算的学者参考
受Goemans和Williamson（1995）在最大割问题上的方法启发，本文针对正交约束二次优化问题，设计了一种多项式时间近似算法。首先，通过构建半定松弛并提出随机取样算法，从松弛解生成可行解；其次，证明了该算法具有常数因子近似保证。当在n维空间中优化m个正交向量时，利用强对偶性与半定互补松弛性，证明算法达到1/3的近似比。对于任意形如2^q（q为整数）的m，我们构造了一个实例，其性能恰好为(m+2)/(3m)，当m趋于无穷时趋近于1/3，说明分析紧致。因此，该近似比不可再改进。
原文摘要 · Abstract (English)
Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive constant-factor approximation guarantees for our algorithm. When optimizing for $m$ orthonormal vectors in dimension $n$, we leverage strong duality and semidefinite complementary slackness to show that our algorithm achieves a $1/3$-approximation ratio. For any $m$ of the form $2^q$ for some integer $q$, we also construct an instance where the performance of our algorithm is exactly $(m+2)/(3m)$, which can be made arbitrarily close to $1/3$ by taking $m \rightarrow + \infty$, hence showing that our analysis is tight.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。