On the solution of linear programs by Jacobian smoothing methods
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.
- Jacobian Smoothing Methods for Nonlinear Complementarity Problems
- A new Jacobian smoothing method for solving nonlinear complementarity problems
- scientific article; zbMATH DE number 5951419
- Improved smoothing-type methods for the solution of linear programs
- A global Jacobian smoothing algorithm for nonlinear complementarity problems
- scientific article; zbMATH DE number 5732751
- Modified Jacobian smoothing method for nonsmooth complementarity problems
- Smoothing methods for convex inequalities and linear complementarity problems
- A partially smoothing Jacobian method for nonlinear complementarity problems with P₀ function
- A smoothing-type method for solving semidefinite programs
- Improved smoothing-type methods for the solution of linear programs
- Predictor-corrector smoothing methods for linear programs with a more flexible update of the smoothing parameter
- A smoothing Newton-type method for generalized nonlinear complementarity problem
- Smoothing-type algorithm for solving linear programs by using an augmented complementarity problem
- A smoothing Levenberg-Marquardt method for the extended linear complementarity problem
This page was built for publication: On the solution of linear programs by Jacobian smoothing methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5959288)
