A non-interior continuation method for generalized linear complementarity problems (Q1968796): Difference between revisions

The authors consider the problem (GLCP): to find \(x \in \mathbb{R}^n\) such that \[ W^i=N^ix+q^i, \quad W^i \geq 0,\quad x \geq 0 \quad x^i \prod_{j=1}^{m_i} W^i_j =0, \quad i=1, \dots, n \] where \(N^i \in \mathbb{R}^{m_i \times n}, q^i \in \mathbb{R}^{m_i}\), \(\sum m_i=m_0\). \(N\) (resp. \(q\)) denotes the vertical block matrix (vector) , whose \(i\)th-block is \(N^i\) (resp. \(q^i\)), its solution set, denoted by \(T\), is assumed not empty. (GLCP) is equivalent to solve the system: \(H_i(x)=\min\{x_i,W^i_1, \dots, W^i_{m_i}\}\), \(i=1,\dots,n.\) To smooth this system the function: \[ H_i(x,t)=-t \ln \left( \exp \left(\frac{x_i}{t} \right)\right) + \sum_{j=1}^{m_i} \exp\left(-\frac{-W^i_j(x)}{t}\right), \quad i=1 \dots n \] is used. The authors present a non-interior continuation algorithm which includes a Newton step at each iteration, and certain strategies to determine the step size and the reduction of the continuation parameter. The global convergence of the algorithm is proved under the assumption that the Jacobian \( \nabla H_x(x^k,t^k)\) is non singular for all \(k\) and there exists \(C\) such that \( \|\nabla H_x^{-1}(x^k,t^k) \|<C\) for all \(k\). The strict complementarity condition at the solution \(x^*\), is assumed to prove the local \(Q\)-quadratic convergence of the algorithm to \((x^*,0)\) . The algorithm is tested for several problems with \(N\) a \(P_0\)-matrix. Numerical results show that it behaves poorly if the strict complementarity condition doesn't hold.