arrow
Volume 40, Issue 5
Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data

Xinlong Luo & Yiyan Yao

J. Comp. Math., 40 (2022), pp. 760-780.

Published online: 2022-05

Export citation
  • Abstract

In this article, we consider the primal-dual path-following method and the trust-region updating strategy for the standard linear programming problem. For the rank-deficient problem with the small noisy data, we also give the preprocessing method based on the QR decomposition with column pivoting. Then, we prove the global convergence of the new method when the initial point is strictly primal-dual feasible. Finally, for some rank-deficient problems with or without the small noisy data from the NETLIB collection, we compare it with other two popular interior-point methods, i.e. the subroutine pathfollow.m and the built-in subroutine linprog.m of the MATLAB environment. Numerical results show that the new method is more robust than the other two methods for the rank-deficient problem with the small noise data.

  • Keywords

Continuation Newton method, Trust-region method, Linear programming, Rank deficiency, Path-following method, Noisy data.

  • AMS Subject Headings

65L20, 65K05, 65L05

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

luoxinlong@bupt.edu.cn (Xinlong Luo)

yaoyiyan@bupt.edu.cn (Yiyan Yao)

  • BibTex
  • RIS
  • TXT
@Article{JCM-40-760, author = {Xinlong and Luo and luoxinlong@bupt.edu.cn and 23357 and School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing, China and Xinlong Luo and Yiyan and Yao and yaoyiyan@bupt.edu.cn and 23358 and School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing, China and Yiyan Yao}, title = {Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data}, journal = {Journal of Computational Mathematics}, year = {2022}, volume = {40}, number = {5}, pages = {760--780}, abstract = {

In this article, we consider the primal-dual path-following method and the trust-region updating strategy for the standard linear programming problem. For the rank-deficient problem with the small noisy data, we also give the preprocessing method based on the QR decomposition with column pivoting. Then, we prove the global convergence of the new method when the initial point is strictly primal-dual feasible. Finally, for some rank-deficient problems with or without the small noisy data from the NETLIB collection, we compare it with other two popular interior-point methods, i.e. the subroutine pathfollow.m and the built-in subroutine linprog.m of the MATLAB environment. Numerical results show that the new method is more robust than the other two methods for the rank-deficient problem with the small noise data.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2101-m2020-0173}, url = {http://global-sci.org/intro/article_detail/jcm/20546.html} }
TY - JOUR T1 - Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data AU - Luo , Xinlong AU - Yao , Yiyan JO - Journal of Computational Mathematics VL - 5 SP - 760 EP - 780 PY - 2022 DA - 2022/05 SN - 40 DO - http://doi.org/10.4208/jcm.2101-m2020-0173 UR - https://global-sci.org/intro/article_detail/jcm/20546.html KW - Continuation Newton method, Trust-region method, Linear programming, Rank deficiency, Path-following method, Noisy data. AB -

In this article, we consider the primal-dual path-following method and the trust-region updating strategy for the standard linear programming problem. For the rank-deficient problem with the small noisy data, we also give the preprocessing method based on the QR decomposition with column pivoting. Then, we prove the global convergence of the new method when the initial point is strictly primal-dual feasible. Finally, for some rank-deficient problems with or without the small noisy data from the NETLIB collection, we compare it with other two popular interior-point methods, i.e. the subroutine pathfollow.m and the built-in subroutine linprog.m of the MATLAB environment. Numerical results show that the new method is more robust than the other two methods for the rank-deficient problem with the small noise data.

Xinlong Luo & Yiyan Yao. (2022). Primal-Dual Path-Following Methods and the Trust-Region Updating Strategy for Linear Programming with Noisy Data. Journal of Computational Mathematics. 40 (5). 760-780. doi:10.4208/jcm.2101-m2020-0173
Copy to clipboard
The citation has been copied to your clipboard