On the convergence of the method of analytic centers when applied to convex quadratic programs (Q2277366): Difference between revisions

The problem under study is to find \[ \lambda^*=\min \{c^ Tx| x\in P\},\quad P=\{x\in R^ n| f_ i(x)\leq 0,\quad 1\leq i\leq m\}, \] where \(f_ i\), \(1\leq i\leq m\) are convex quadratic functions, int \(P\neq \emptyset\). The method mentioned in the title generates sequences of optimal value estimations \(\lambda_ k>\lambda_{k+1}\downarrow \lambda^*\) and iterative points \[ y_ k\in int(P\cap \{x:c^ Tx\leq \lambda_ k\}). \] Here \(y_{k+1}\) is obtained from \(y_ k\) by one Newton step for solving the system \(D_ x\phi (x,\lambda_{k+1})=0\), \[ \phi (x,\lambda)=-\sum^{m}_{i=1}\ell n(-f_ i(x))-m \ell n(\lambda - c^ Tx). \] The aim of the paper is to prove the following estimation of the speed of convergence \[ 0<c^ Ty_ k-\lambda^*<\epsilon (c^ Ty_ 0-\lambda^*) \] for all \(k\geq const \sqrt{m}\ell n(1/\epsilon)\).