JCM
Journal of Computational Mathematics ›› 2019, Vol. 37 ›› Issue (6): 843-865.DOI: 10.4208/jcm.1907-m2019-0016

Previous Articles     Next Articles

A ROBUST INTERIOR POINT METHOD FOR COMPUTING THE ANALYTIC CENTER OF AN ILL-CONDITIONED POLYTOPE WITH ERRORS

Zhouhong Wang1, Yuhong Dai2,3, Fengmin Xu4   

  1. 1 School of Science, Beijing Jiaotong University, Beijing 100044, China;
    2 LESC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190;
    3 School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;
    4 School of Economics and Finance, Xi'an Jiaotong University, Xi'an 710061, China
  • Received:2019-01-27 Revised:2019-04-11 Online:2019-12-15 Published:2019-12-15
PDF ( 19 ) Cited

Zhouhong Wang, Yuhong Dai, Fengmin Xu. A ROBUST INTERIOR POINT METHOD FOR COMPUTING THE ANALYTIC CENTER OF AN ILL-CONDITIONED POLYTOPE WITH ERRORS[J]. Journal of Computational Mathematics, 2019, 37(6): 843-865.

In this paper we propose an efficient and robust method for computing the analytic center of the polyhedral set P={x ∈ Rn|Ax=b, x ≥ 0}, where the matrix A ∈ Rm×n is ill-conditioned, and there are errors in A and b. Besides overcoming the difficulties caused by ill-conditioning of the matrix A and errors in A and b, our method can also detect the infeasibility and the unboundedness of the polyhedral set P automatically during the computation. Detailed mathematical analyses for our method are presented and the worst case complexity of the algorithm is also given. Finally some numerical results are presented to show the robustness and effectiveness of the new method.
Key words: Analytic center, Ill-conditioning, Unboundedness, Primal-dual interior point algorithm, Convergence, Polynomial complexity

CLC Number: 

[1] D.S. Atkinson and P.M. Vaidya, A scaling technique for finding the weighted analytic center of a polytope, Mathematical Programming, 57(1992), 163-192.

[2] M.S. Bazaraa, H.D. Sherali and C.M. Shetty, Nonlinear Programming:Theory and Algorithms, 3rd edition, John Wiley & Sons, New Jersey, 2006.

[3] J.F. Bonnans and C.C. Gonzaga, Convergence of interior point algorithms for the monotone linear complementarity problem, Mathematics of Operations Research, 21(1996), 1-25.

[4] J.F. Bonnans and F.A. Potra, On the convergence of the iteration sequence of infeasible path following algorithms for linear complementarity problems, Mathematics of Operations Research, 22(1997), 378-407.

[5] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.

[6] Y.H. Dai, Z.H. Wang and F.M. Xu, A primal-dual method for unfolding neutron energy spectrum from multiple activation foils, Research report, AMSS, Chinese Academy of Sciences, 2018.

[7] C.C. Gonzaga, The largest step path following algorithm for monotone linear complementarity problems, Mathematical Programming, 76(1997), 309-332.

[8] C.C. Gonzaga and R.A. Tapia, On the convergence of the Mizuno-Todd-Ye algorithm to the analytic center of the solution set, SIAM Journal on Optimization, 7(1997), 47-65.

[9] M.D. González-Lima, R.A. Tapia and F.A. Potra, On effectively computing the analytic center of the solution set by primal-dual interior-point methods, SIAM Journal on Optimization, 8(1998), 1-25.

[10] M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Mathematical Programming, 61(1993), 263-280.

[11] M. Kojima, S. Mizuno and A. Yoshise, A primal-dual interior point algorithm for linear programming, in Progress in Mathematical Programming:Interior-Point and Related Methods, N. Megiddo (ed.), Springer, New York, 1989, 29-47.

[12] I.J. Lustig, R.E. Marsten and D.F. Shanno, On implementing Mehrotra's predictor-corrector interior-point method for linear programming, SIAM Journal on Optimization, 2(1992), 435-449.

[13] N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming:Interior-Point and Related Methods, N. Megiddo (ed.), Springer, New York, 1989, 131-158.

[14] S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, 2(1992), 575-601.

[15] S. Mehrotra, Quadratic convergence in a primal-dual method, Mathematics of Operations Research, 18(1993), 741-751.

[16] S. Mizuno, Polynomiality of infeasible-interior-point algorithms for linear programming, Mathematical Programming, 67(1994), 109-119.

[17] S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Mathematics of Operations Research, 18(1993), 964-981.

[18] S. Mizuno, M.J. Todd and Y. Ye, A Surface of Analytic Centers and Primal-Dual InfeasibleInterior-Point Algorithms for Linear Programming, Mathematics of Operations Research, 20(1995), 135-162.

[19] R. Monteiro, J. O'Neal and T. Tsuchiya, Uniform boundedness of a preconditioned normal matrix used in interior-point methods, SIAM Journal on Optimization, 15(2004), 96-100.

[20] A. Oliveira and D. Sorensen, A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Linear Algebra and its Applications, 394(2005), 1-24.

[21] F. Potra, An infeasible-interior-point predictor-corrector algorithm for linear programming, SIAM Journal on Optimization, 6(1996), 19-32.

[22] J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, SIAM, Philadelphia, 2001.

[23] C. Roos, A full-newton step o(n) infeasible interior-point algorithm for linear optimization, SIAM Journal on Optimization, 16(2006), 1110-1136.

[24] C. Roos, T. Terlaky and J.P. Vial, Interior Point Methods for Linear Optimization, 2nd edition, Springer, Berlin, 2005.

[25] A. Wächter and L.T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106(2006), 25-57.

[26] Y. Wang, Y. Yuan and H. Zhang, A trust region-CG algorithm for deblurring problem in atmospheric image reconstruction, Science in China Series A:Mathematics, 45(2002), 731-740.

[27] M. Wright, Ill-conditioning and computational error in interior methods for nonlinear programming, SIAM Journal on Optimization, 9(1998), 84-111.

[28] S.J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1996.

[29] S.J. Wright, Effects of finite-precision arithmetic on interior-point methods for nonlinear programming, SIAM Journal on Optimization, 12(2001), 36-78.

[30] Y. Ye, Interior Point Algorithms:Theory and Analysis, John Wiley & Sons, New Jersey, 1997.

[31] Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, A quadratically convergent O(√nL)-iteration algorithm for linear programming, Mathematical Programming, 59(1993), 151-162.

[32] Y. Ye, M.J. Todd and S. Mizuno, An O(√nL)-iteration homogeneous and self-dual linear programming algorithm, Mathematics of Operations Research, 19(1994), 53-67.

[33] Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization, 4(1994), 208-227.

[34] Y. Zhang, Solving large-scale linear programs by interior-point methods under the MATLAB environment, Optimization Methods and Software, 10(1998), 1-31.

[35] Y. Zhangsun, Unfolding Method Based on Entropy Theory for the Determination of Neutron Spectrum (in Chinese), Master's thesis, Northwest Institute of Nuclear Technology, Xi'an, Shanxi, P. R. China, 2015.
[1] Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[2] Mohammed Harunor Rashid. METRICALLY REGULAR MAPPING AND ITS UTILIZATION TO CONVERGENCE ANALYSIS OF A RESTRICTED INEXACT NEWTON-TYPE METHOD [J]. Journal of Computational Mathematics, 2022, 40(1): 44-69.
[3] Yang Chen, Chunlin Wu. DATA-DRIVEN TIGHT FRAME CONSTRUCTION FOR IMPULSIVE NOISE REMOVAL [J]. Journal of Computational Mathematics, 2022, 40(1): 89-107.
[4] Qianqian Chu, Guanghui Jin, Jihong Shen, Yuanfeng Jin. NUMERICAL ANALYSIS OF CRANK-NICOLSON SCHEME FOR THE ALLEN-CAHN EQUATION [J]. Journal of Computational Mathematics, 2021, 39(5): 655-665.
[5] Lu Zhang, Qifeng Zhang, Hai-wei Sun. A FAST COMPACT DIFFERENCE METHOD FOR TWO-DIMENSIONAL NONLINEAR SPACE-FRACTIONAL COMPLEX GINZBURG-LANDAU EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(5): 708-732.
[6] Xia Cui, Guangwei Yuan, Fei Zhao. ANALYSIS ON A NUMERICAL SCHEME WITH SECOND-ORDER TIME ACCURACY FOR NONLINEAR DIFFUSION EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(5): 777-800.
[7] Yong Liu, Chi-Wang Shu, Mengping Zhang. SUB-OPTIMAL CONVERGENCE OF DISCONTINUOUS GALERKIN METHODS WITH CENTRAL FLUXES FOR LINEAR HYPERBOLIC EQUATIONS WITH EVEN DEGREE POLYNOMIAL APPROXIMATIONS [J]. Journal of Computational Mathematics, 2021, 39(4): 518-537.
[8] Xiaobing Feng, Yukun Li, Yi Zhang. STRONG CONVERGENCE OF A FULLY DISCRETE FINITE ELEMENT METHOD FOR A CLASS OF SEMILINEAR STOCHASTIC PARTIAL DIFFERENTIAL EQUATIONS WITH MULTIPLICATIVE NOISE [J]. Journal of Computational Mathematics, 2021, 39(4): 574-598.
[9] Bin Huang, Aiguo Xiao, Gengen Zhang. IMPLICIT-EXPLICIT RUNGE-KUTTA-ROSENBROCK METHODS WITH ERROR ANALYSIS FOR NONLINEAR STIFF DIFFERENTIAL EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(4): 599-620.
[10] Yaozong Tang, Qingzhi Yang, Gang Luo. CONVERGENCE ANALYSIS ON SS-HOPM FOR BEC-LIKE NONLINEAR EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2021, 39(4): 621-632.
[11] Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[12] Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.
[13] Huaijun Yang, Dongyang Shi, Qian Liu. SUPERCONVERGENCE ANALYSIS OF LOW ORDER NONCONFORMING MIXED FINITE ELEMENT METHODS FOR TIME-DEPENDENT NAVIER-STOKES EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(1): 63-80.
[14] Yongtao Zhou, Chengjian Zhang, Huiru Wang. BOUNDARY VALUE METHODS FOR CAPUTO FRACTIONAL DIFFERENTIAL EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(1): 108-129.
[15] Xiaocui Li, Xu You. MIXED FINITE ELEMENT METHODS FOR FRACTIONAL NAVIER-STOKES EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(1): 130-146.
Viewed
Full text


Abstract

Journal of Computational Mathematics
Contact Us
Editor-in-Chief: Zhiming Chen
Electronic: 1991-7139
ISSN Print: 0254-9409
Issues: 6 / year
Institute of Computational Mathematics and Scientific/ Engineering Computing
Chinese Academy of Sciences
Zhongguancun East Rd. No.55
Beijing 100190, China
Phone: 86-10-82541418
Email: jcm@lsec.cc.ac.cn
×

扫码分享

The journal is sponsored by ICMSEC
Copyrights © ICMSEC