<p>We study the convergence rate of the alternating projection method (APM) applied to the intersection of an affine subspace and the second-order cone. We show that when they intersect non-transversally, the convergence rate is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(k^{-1/2})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>k</i> is the number of iterations of the APM. In particular, when the intersection is not at the origin or forms a ray extending from the origin, the obtained convergence rate can be exact because a lower bound of the convergence rate is evaluated. Such an intersection is of singularity degree 1, and the convergence rate agrees with the worst-case convergence rate obtained with the error bound discussed in [<CitationRef CitationID="CR1">1</CitationRef>]. Furthermore, we consider the intersection of an affine subspace and the direct product of the two second-order cones to deal with a case where the singularity degree of the intersection is 2, and evaluate the convergence rate of APM in this case. We then provide an example that the convergence rate of the APM for any initial point is not tight for the rate expected from the error bound for the example.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Convergence rate of alternating projection method for the intersection of an affine subspace and the second-order cone

  • Hiroyuki Ochiai,
  • Yoshiyuki Sekiguchi,
  • Hayato Waki

摘要

We study the convergence rate of the alternating projection method (APM) applied to the intersection of an affine subspace and the second-order cone. We show that when they intersect non-transversally, the convergence rate is \(O(k^{-1/2})\) O ( k - 1 / 2 ) , where k is the number of iterations of the APM. In particular, when the intersection is not at the origin or forms a ray extending from the origin, the obtained convergence rate can be exact because a lower bound of the convergence rate is evaluated. Such an intersection is of singularity degree 1, and the convergence rate agrees with the worst-case convergence rate obtained with the error bound discussed in [1]. Furthermore, we consider the intersection of an affine subspace and the direct product of the two second-order cones to deal with a case where the singularity degree of the intersection is 2, and evaluate the convergence rate of APM in this case. We then provide an example that the convergence rate of the APM for any initial point is not tight for the rate expected from the error bound for the example.