On the solution of linear programs by Jacobian smoothing methods (Q5959288)

The authors consider the linear program in standard form \[ \min c^Tx \text{ subject to }Ax= b, \quad x\geq 0,\tag{1} \] where \(A\in \mathbb{R}^{m\times n}\) has full rank, \(c\in \mathbb{R}^n\), \(b\in \mathbb{R}^m\). The dual problem of (1) is \[ \max b^Tx \text{ subject to }A^T\lambda+s=c, \quad s\geq 0,\tag{2} \] where \(\lambda\in \mathbb{R}^n\) is the dual variable and \(s\in \mathbb{R}^n\) is a nonnegative slack variable. (1) and (2) have the same optimality conditions, namely \[ A^T\lambda+s=c\;Ax=b,\;x_i\geq 0,\;s_i\geq 0,\;x_i s_i=0 \quad\forall i=1,2,\dots, n.\tag{3} \] In order to find the optimality conditions of (3), the authors consider the nonlinear systems of solutions \[ \Phi(x,\lambda,s)=0. \tag{4} \] Since \(\Phi\) is nonsmooth in general and the Jacobian matrix \(\Phi(x,\lambda,s)\) turns out to be singular at some differentiable point \((x,\lambda,s)\). The authors use some perturbed Newton methods. The method is quite similar to the one given by \textit{X. J. Chen, L. Qi} and \textit{D. F. Sun} [Math. Comput. 67, 519-540 (1998; Zbl 0894.90143)]. In fact there are some differences between this paper and Chen et al. The assumptions used in Chen et al. in order to establish global convergence are not satisfied for linear programs, moreover in the local convergence part, the authors exploit special properties of the linear program to get a complete characterization of the situation where the optimal conditions (3) have a unique solution. The authors also compare the method with the class of primal-dual interior methods.