×

Active-set prediction for interior point methods using controlled perturbations. (English) Zbl 1364.90356

Summary: 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.

MSC:

90C51 Interior-point methods
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Altman, A; Gondzio, J, Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11, 275-302, (1999) · Zbl 0957.90101
[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)
[3] Benson, H; Shanno, D, An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput. Optim. Appl., 38, 371-399, (2007) · Zbl 1171.90546
[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) · Zbl 0794.90036
[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) · Zbl 1269.90080
[6] Castro, J; Cuesta, J, Existence, uniqueness, and convergence of the regularized primal-dual central path, Oper. Res. Lett., 38, 366-371, (2010) · Zbl 1205.90193
[7] Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009) · Zbl 1192.90001
[8] DeMiguel, V; Friedlander, MP; Nogales, FJ; Scholtes, S, A two-sided relaxation scheme for mathematical programs with equilibrium constraints, SIAM J. Optim., 16, 587-609, (2005) · Zbl 1122.90060
[9] El-Bakry, AS; Tapia, R; Zhang, Y, A study of indicators for identifying zero variables in interior point methods, SIAM Rev., 36, 45-72, (1994) · Zbl 0801.65056
[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)
[11] Engau, A; Anjos, MF; Vannelli, A, On interior-point warmstarts for linear and combinatorial optimization, SIAM J. Optim., 20, 1828-1861, (2010) · Zbl 1206.90215
[12] Facchinei, F; Fischer, A; Kanzow, C, On the accurate identification of active constraints, SIAM J. Optim., 9, 14-32, (1998) · Zbl 0960.90080
[13] Ferris, M., Mangasarian, O., Wright, S.J.: Linear Programming with Matlab. SIAM, Philadelphia (2007)
[14] Freund, RM, A potential-function reduction algorithm for solving a linear program directly from an infeasible “warm start”, Math. Prog., 52, 441-466, (1991) · Zbl 0754.90033
[15] Freund, RM, Theoretical efficiency of a shifted-barrier-function algorithm for linear programming, Linear Algebra Appl., 152, 19-41, (1991) · Zbl 0729.65040
[16] Freund, RM, 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, 29-57, (1996) · Zbl 0848.90081
[17] Gill, PE; Murray, W; Saunders, MA; Tomlin, J; Wright, MH, On projected Newton barrier methods for linear programming and an equivalence to karmarkar’s projective method, Math. Prog., 36, 183-209, (1986) · Zbl 0624.90062
[18] Gondzio, J, Warm start of the primal-dual method applied in the cutting-plane scheme, Math. Prog., 83, 125-143, (1998) · Zbl 0920.90102
[19] Gondzio, J, Interior point methods 25 years later, Eur. J. Oper. Res., 218, 587-601, (2012) · Zbl 1244.90007
[20] Gondzio, J; Grothey, A, A new unblocking technique to warmstart interior point methods based on sensitivity analysis, SIAM J. Optim., 19, 1184-1210, (2008) · Zbl 1177.90411
[21] Gondzio, J; Vial, JP, Warm start and \(ϵ \)-subgradients in a cutting plane scheme for block-angular linear programs, Comput. Optim. Appl., 14, 17-36, (1999) · Zbl 0958.90057
[22] Güler, O; 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) · Zbl 0785.90067
[23] Karmarkar, N; Ramakrishnan, K, Computational results of an interior point algorithm for large scale linear programming, Math. Prog., 52, 555-586, (1991) · Zbl 0739.90042
[24] Mangasarian, O; Ren, J, New improved error bounds for the linear complementarity problem, Math. Prog., 66, 241-255, (1994) · Zbl 0829.90124
[25] McShane, KA; Monma, CL; Shanno, D, An implementation of a primal-dual interior point method for linear programming, ORSA J. Comput., 1, 70-83, (1989) · Zbl 0752.90047
[26] Mehrotra, S.: Finite termination and superlinear convergence in primal-dual methods. Tech. Rep. 91-13, Northwestern University (1991) · Zbl 0920.90102
[27] Mehrotra, S, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[28] Mehrotra, S; Ye, Y, Finding an interior point in the optimal face of linear programs, Math. Prog., 62, 497-515, (1993) · Zbl 0803.90089
[29] Mitchell, JE, An interior point column generation method for linear programming using shifted barriers, SIAM J. Optim., 4, 423-440, (1994) · Zbl 0820.90069
[30] Morales, JL, A numerical study of limited memory BFGS methods, Appl. Math. Lett., 15, 481-487, (2002) · Zbl 1175.90419
[31] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Madison (2006) · Zbl 1104.65059
[32] Oberlin, C; Wright, SJ, Active set identification in nonlinear programming, SIAM J. Optim., 17, 577-605, (2006) · Zbl 1174.90813
[33] Pang, JS, Error bounds in mathematical programming, Math. Prog., 79, 299-332, (1997) · Zbl 0887.90165
[34] Polyak, R, Modified barrier functions (theory and methods), Math. Prog., 54, 177-222, (1992) · Zbl 0756.90085
[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) · Zbl 1205.90193
[36] Sierksma, G.: Linear and Integer Programming: Theory and Practice, 2nd edn. CRC Press, Boca Raton (2001) · Zbl 0979.90087
[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) · Zbl 1269.90080
[38] Tone, K, An active-set strategy in an interior point method for linear programming, Math. Prog., 59, 345-360, (1993) · Zbl 0804.90093
[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) · Zbl 0801.65056
[40] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
[41] Xu, X; Hung, PF; Ye, Y, A simplified homogeneous and self-dual linear programming algorithm and its implementation, Ann. Oper. Res., 62, 151-171, (1996) · Zbl 0848.90095
[42] Ye, Y, On the finite convergence of interior-point algorithms for linear programming, Math. Prog., 57, 325-335, (1992) · Zbl 0794.90036
[43] Ye, Y; Todd, MJ; Mizuno, S, An o(nl)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 53-67, (1994) · Zbl 0799.90087
[44] Yildirim, E; Wright, SJ, Warm-start strategies in interior-point methods for linear programming, SIAM J. Optim., 12, 782-810, (2002) · Zbl 1007.90079
[45] Zhang, Y, Solving large-scale linear programs by interior-point methods under the Matlab environment, Optim. Methods Softw., 10, 1-31, (1998) · Zbl 0916.90208
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.