A multilevel iterative method for symmetric, positive definite linear complementarity problems (Q794138)

This paper presents a method for solving the constrained optimization problem \(\min f(x)=1/2x^ TAx-x^ Tb,\) \(x\geq c\) where A is a symmetric positive definite matrix. The method of solution consists of constructing a finite sequence of auxiliary problems \[ P_ k:\min f_ k(x^ k)=1/2(x^ k)^ TA_ kx^ k-(x^ k)^ Tb^ k,\quad x^ k\geq c^ k \] where \(x^ k\in V_ k=R^{V_ k}\) and \(\dim V_{k-1}<\dim V_ k.\) The sequence is for \(k=1...m\) and \(k=m\) corresponds to the original problem. The algorithm starts with a feasible solution for \(P_ m\) and with various iterations, constructs approximate solutions to the problems \(P_ k\), \(k<m\) and from these a corrected value of \(x^ m\). Since the process is a variational one the procedure will always converge and there is numerical evidence that this convergence is rapid. In the example given the method compares favourably with relaxation methods. The problem \(P_ m\) is said to be nondegenerate if \((x-c)+(Ax- b)>0\) where x is the solution. In such cases it is proved that this algorithm reduces to a linear iterative method and that the rate of convergence consequently depends on the spectral radius of a linear operator.