Active-set prediction for interior point methods using controlled perturbations

详细信息    查看全文

• 作者：Coralia Cartis ; Yiming Yan
• 关键词：Active ; set prediction ; Interior point methods ; Linear programming
• 刊名：Computational Optimization and Applications
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：63
• 期：3
• 页码：639-684
• 全文大小：1,482 KB
• 参考文献：1.Altman, A., Gondzio, J.: Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim. Methods Softw. 11(1–4), 275–302 (1999)CrossRef MathSciNet
  2.Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Special simplex implementations and optimality conditions, pp. 201–257. Wiley, Hoboken (2009)CrossRef
  3.Benson, H., Shanno, D.: An exact primal–dual penalty method approach to warmstarting interior-point methods for linear programming. Comput. Optim. Appl. 38(3), 371–399 (2007)CrossRef MathSciNet MATH
  4.Berkelaar, M., Eikland, K., Notebaert, P.: lpsolve : open source (mixed-integer) linear programming system. Eindhoven University of Technology. http://​lpsolve.​sourceforge.​net/​5.​5/​ (2004)
  5.Cartis, C., Gould, N.I.M.: Finding a point in the relative interior of a polyhedron. Tech. Rep. RAL 2006-016, Rutherford Appleton Laboratory (2006)
  6.Castro, J., Cuesta, J.: Existence, uniqueness, and convergence of the regularized primal-dual central path. Oper. Res. Lett. 38(5), 366–371 (2010)CrossRef MathSciNet MATH
  7.Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009)CrossRef MATH
  8.DeMiguel, V., Friedlander, M.P., Nogales, F.J., Scholtes, S.: A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16(2), 587–609 (2005)CrossRef MathSciNet MATH
  9.El-Bakry, A.S., Tapia, R., Zhang, Y.: A study of indicators for identifying zero variables in interior point methods. SIAM Rev. 36(1), 45–72 (1994)CrossRef MathSciNet MATH
  10.Engau, A., Anjos, M.F., Vannelli, A.: Operations Research and Cyber-Infrastructure. A primal-dual slack approach to warmstarting interior-point methods for linear programming, vol. 47, pp. 195–217. Springer, New York (2009)CrossRef
  11.Engau, A., Anjos, M.F., Vannelli, A.: On interior-point warmstarts for linear and combinatorial optimization. SIAM J. Optim. 20(4), 1828–1861 (2010)CrossRef MathSciNet MATH
  12.Facchinei, F., Fischer, A., Kanzow, C.: On the accurate identification of active constraints. SIAM J. Optim. 9(2), 14–32 (1998)CrossRef MathSciNet MATH
  13.Ferris, M., Mangasarian, O., Wright, S.J.: Linear Programming with Matlab. SIAM, Philadelphia (2007)CrossRef
  14.Freund, R.M.: A potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”. Math. Prog. 52(1–3), 441–466 (1991)CrossRef MATH
  15.Freund, R.M.: Theoretical efficiency of a shifted-barrier-function algorithm for linear programming. Linear Algebra Appl. 152, 19–41 (1991)CrossRef MathSciNet MATH
  16.Freund, R.M.: An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution. Ann. Oper. Res. 62(1), 29–57 (1996)CrossRef MathSciNet MATH
  17.Gill, P.E., Murray, W., Saunders, M.A., Tomlin, J., Wright, M.H.: On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method. Math. Prog. 36(2), 183–209 (1986)CrossRef MathSciNet MATH
  18.Gondzio, J.: Warm start of the primal-dual method applied in the cutting-plane scheme. Math. Prog. 83(1–3), 125–143 (1998)MathSciNet MATH
  19.Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218, 587–601 (2012)CrossRef MathSciNet MATH
  20.Gondzio, J., Grothey, A.: A new unblocking technique to warmstart interior point methods based on sensitivity analysis. SIAM J. Optim. 19(3), 1184–1210 (2008)CrossRef MathSciNet MATH
  21.Gondzio, J., Vial, J.P.: Warm start and \(\epsilon \) -subgradients in a cutting plane scheme for block-angular linear programs. Comput. Optim. Appl. 14(1), 17–36 (1999)CrossRef MathSciNet MATH
  22.Güler, O., den Hertog, D., Roos, C., Terlaky, T., Tsuchiya, T.: Degeneracy in interior point methods for linear programming: a survey. Ann. Oper. Res. 46–47, 107–138 (1993)CrossRef
  23.Karmarkar, N., Ramakrishnan, K.: Computational results of an interior point algorithm for large scale linear programming. Math. Prog. 52(1–3), 555–586 (1991)CrossRef MathSciNet MATH
  24.Mangasarian, O., Ren, J.: New improved error bounds for the linear complementarity problem. Math. Prog. 66(2), 241–255 (1994)CrossRef MathSciNet MATH
  25.McShane, K.A., Monma, C.L., Shanno, D.: An implementation of a primal-dual interior point method for linear programming. ORSA J. Comput. 1(2), 70–83 (1989)CrossRef MATH
  26.Mehrotra, S.: Finite termination and superlinear convergence in primal-dual methods. Tech. Rep. 91-13, Northwestern University (1991)
  27.Mehrotra, S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992)CrossRef MathSciNet MATH
  28.Mehrotra, S., Ye, Y.: Finding an interior point in the optimal face of linear programs. Math. Prog. 62(1–3), 497–515 (1993)CrossRef MathSciNet MATH
  29.Mitchell, J.E.: An interior point column generation method for linear programming using shifted barriers. SIAM J. Optim. 4(2), 423–440 (1994)CrossRef MathSciNet MATH
  30.Morales, J.L.: A numerical study of limited memory BFGS methods. Appl. Math. Lett. 15(4), 481–487 (2002)CrossRef MathSciNet MATH
  31.Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Madison (2006)MATH
  32.Oberlin, C., Wright, S.J.: Active set identification in nonlinear programming. SIAM J. Optim. 17(2), 577–605 (2006)CrossRef MathSciNet MATH
  33.Pang, J.S.: Error bounds in mathematical programming. Math. Prog. 79(1), 299–332 (1997)MATH
  34.Polyak, R.: Modified barrier functions (theory and methods). Math. Prog. 54(1–3), 177–222 (1992)CrossRef MathSciNet MATH
  35.Saunders, M., Tomlin, J.: Solving regularized linear programs using barrier methods and KKT systems. Tech. Rep. SOL 96-4, Deptartment of Operations Research, Stanford University (1996)
  36.Sierksma, G.: Linear and Integer Programming: Theory and Practice, 2nd edn. CRC Press, Boca Raton (2001)
  37.Skajaa, A., Andersen, E., Ye, Y.: Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems. Math. Prog. Comput. 5, 1–25 (2013)CrossRef MathSciNet MATH
  38.Tone, K.: An active-set strategy in an interior point method for linear programming. Math. Prog. 59(1–3), 345–360 (1993)CrossRef MathSciNet MATH
  39.Williams, P.J.: Effective finite termination procedures in interior-point methods for linear programming. Ph.D. thesis, Department of Computational and Applied Mathematics, Rice University (1998)
  40.Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)CrossRef MATH
  41.Xu, X., Hung, P.F., Ye, Y.: A simplified homogeneous and self-dual linear programming algorithm and its implementation. Ann. Oper. Res. 62(1), 151–171 (1996)CrossRef MathSciNet MATH
  42.Ye, Y.: On the finite convergence of interior-point algorithms for linear programming. Math. Prog. 57(1), 325–335 (1992)CrossRef MATH
  43.Ye, Y., Todd, M.J., Mizuno, S.: An o(nl)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19(1), 53–67 (1994)CrossRef MathSciNet MATH
  44.Yildirim, E., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optim. 12(3), 782–810 (2002)CrossRef MathSciNet MATH
  45.Zhang, Y.: Solving large-scale linear programs by interior-point methods under the Matlab Environment. Optim. Methods Softw. 10(1), 1–31 (1998)CrossRef MathSciNet MATH
  
• 作者单位：Coralia Cartis (1)
  Yiming Yan (2)
  
  1. Mathematical Institute, Radcliffe Observatory Quarter, University of Oxford, Andrew Wiles Building, Woodstock Road, Oxford, OX2 6GG, UK
  2. School of Mathematics, University of Edinburgh, James Clerk Maxwell Building, The King’s Buildings, Mayfield Road, Edinburgh, EH9 3JZ, UK
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Statistics
  Convex and Discrete Geometry
  
• 出版者：Springer Netherlands
• ISSN：1573-2894

文摘

We propose the use of controlled perturbations to address the challenging question of optimal active-set prediction for interior point methods. Namely, in the context of linear programming, we consider perturbing the inequality constraints/bounds so as to enlarge the feasible set. We show that if the perturbations are chosen appropriately, the solution of the original problem lies on or close to the central path of the perturbed problem. We also find that a primal-dual path-following algorithm applied to the perturbed problem is able to accurately predict the optimal active set of the original problem when the duality gap for the perturbed problem is not too small; furthermore, depending on problem conditioning, this prediction can happen sooner than predicting the active set for the perturbed problem or when the original one is solved. Encouraging preliminary numerical experience is reported when comparing activity prediction for the perturbed and unperturbed problem formulations.