A note on alternating projections for ill-posed semidefinite feasibility problems

• 成果类型: Article
• 署名作者: Drusvyatskiy, Dmitriy; Li, Guoyin; Wolkowicz, Henry
• 署名单位: University of Washington; University of Washington Seattle; University of New South Wales Sydney; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1048-9
• 发表日期: 2017
• 页码: 537-548
• 关键词: facial reduction; convex; algorithms

摘要

We observe that Sturm's error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of , where d is the singularity degree of the problem-the minimal number of facial reduction iterations needed to induce Slater's condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of O(1/root k).