摘要
By attacking the linear programming problems from their dual side,a new general algorithm for linear programming is developed.At each iteration,the algorithm finds a feasible descent search direction by handling a least square problem associated with the dual system,using QR decomposition technique.The new method is a combination of pivot method and interior-point method.It in fact not only reduces the possibility of difficulty arising from degeneracy,but also has the same advantages as pivot method in warm-start to resolve linear programming problems.Numerical results of a group of randomly constructed problems are very encouraging.
By attacking the linear programming problems from their dual side,a new general algorithm for linear programming is developed. At each iteration,the algorithm finds a feasible descent search direction by handling a least square problem associated with the dual system, using QR decomposition technique. The new method is a combination of pivot method and interior-point method. It in fact not only reduces the possibility of difficulty arising from degeneracy, but also has the same advantages as pivot method in warm-start to resolve linear programming problems. Numerical results of a group of randomly constructed problems are very encouraging.
基金
SupportedbytheNationalNaturalScienceFoundationofChina(10371028),ScienceFoundationofZhejiangBureauofEducation(20030622)andScienceFoundationofHangzhouUniversityofElectronicTechnology(KYS091504025).
