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

Dmitriy Drusvyatskiy University of Washington Guoyin Li University of New South Wales Henry Wolkowicz University of Waterloo

Numerical Analysis and Scientific Computing Numerical Linear Algebra Optimization and Control mathscidoc:2108.25003

Mathematical Programming, 162, 537-548, 2017.11
We observe that Sturm’s error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of O(k^{-1/(2^{d+1}-2)}), 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/k^{0.5}).
Error bounds · Regularity · Alternating projections · Sublinear convergence · Linear matrix inequality (LMI) · Semi-definite program (SDP)
[ Download ] [ 2021-08-23 15:33:53 uploaded by gyli ] [ 130 downloads ] [ 0 comments ]
@inproceedings{dmitriy2017a,
  title={A note on alternating projections for ill-posed semidefinite feasibility problems},
  author={Dmitriy Drusvyatskiy, Guoyin Li, and Henry Wolkowicz},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210823153353120075862},
  booktitle={Mathematical Programming},
  volume={162},
  pages={537-548},
  year={2017},
}
Dmitriy Drusvyatskiy, Guoyin Li, and Henry Wolkowicz. A note on alternating projections for ill-posed semidefinite feasibility problems. 2017. Vol. 162. In Mathematical Programming. pp.537-548. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210823153353120075862.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved