Corvinus
Corvinus

A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation

E. Nagy, Marianna and Varga, Anita (2021) A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation. Working Paper. Corvinus University of Budapest, Budapest.

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
377kB

Abstract

In this paper, we investigate a new primal-dual long-step interior point algorithm for linear optimization. Based on the step-size, interior point algorithms can be divided into two main groups, short-step and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighbourhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique by Darvay to determine the search directions of the method.

Item Type:Monograph (Working Paper)
Series Name:Corvinus Economics Working Papers - CEWP
Series Number / Identification Number:2021/06
Uncontrolled Keywords:Mathematical programming; Linear optimization; Interior point algorithms; Algebraic equivalent transformation technique
JEL classification:C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Divisions:Faculty of Economics > Department of Operations Research and Actuarial Sciences
Subjects:Mathematics, Econometrics
Projects:OTKA NKFIH 125700, BME IE-MI-FM TKP2020
References:

Adler, I., Karmarkar, N., Resende, M.G., Veiga, G.: Data structures and programming techniques for the implemen-
tation of Karmarkar's algorithm. ORSA J Comput 1(2), 84{106 (1989). https://doi.org/10.1287/ijoc.1.2.84

Ai, W., Zhang, S.: An O(pnL) iteration primal-dual path-following method, based on wide neighborhoods and large
updates, for monotone LCP. SIAM J Optim 16(2), 400{417 (2005). https://doi.org/10.1137/040604492

Bai, Y., Lesaja, G., Roos, C., Wang, G., El Ghami, M.: A class of large-update and small-update primal-dual interior-point algorithms for linear optimization. J Optim Theory Appl 138(3), 341{359 (2008). https://doi.org/10.1007/s10957-008-9389-z

Darvay, Zs.: New interior point algorithms in linear programming. Adv Model Optim 5(1), 51{92 (2003)

Darvay, Zs., Illés, T., Kheirfam, B., Rigó, P.R.: A corrector{predictor interior-point method with new search direction
for linear optimization. Cent Eur J Oper Res 28(3), 1123{1140 (2020)

Darvay, Zs., Illés, T., Majoros, C.: Interior-point algorithm for sufficient LCPs based on the technique of algebraically equivalent transformation. Optim Lett 15(2), 357{376 (2021)

Darvay, Zs., Illés, T., Povh, J., Rigó, P.R.: Feasible corrector-predictor interior-point algorithm for p *(�)-linear com-plementarity problems based on a new search direction. SIAM J Optim 30(3), 2628{2658 (2020)

Darvay, Zs., Papp, I.M., Takács, P.R.: Complexity analysis of a full-Newton step interior-point method for linear
optimization. Period Math Hung 73(1), 27{42 (2016). https://doi.org/10.1007/s10998-016-0119-2

Darvay, Zs., Takács, P.R.: Large-step interior-point algorithm for linear optimization based on a new wide neighbour-
hood. Cent Eur J Oper Res 26(3), 551{563 (2018). https://doi.org/10.1007/s10100-018-0524-0

Feng, Z., Fang, L.: A new O(nL)-iteration predictor{corrector algorithm with wide neighborhood for semidefinite
programming. J Comput Appl Math 256, 65{76 (2014). https://doi.org/10.1016/j.cam.2013.07.011

Gay, D.M.: Electronic mail distribution of linear programming test problems. Math Program Soc COAL Newsl 13,
10{12 (1985)

Jansen, B., Roos, C., Terlaky, T.: The theory of linear programming: skew symmetric self-dual problems and the central
path. Optim 29(3), 225{233 (1994). https://doi.org/10.1080/02331939408843952

Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the sixteenth annual
ACM symposium on Theory of computing, pp. 302{311 (1984). https://doi.org/10.1145/800057.808695

Kheirfam, B., Haghighi, M.: A full-Newton step feasible interior-point algorithm for P�(�)-LCP based on a new search
direction. Croat Oper Res Rev pp. 277{290 (2016)

Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point algorithm for linear programming. In: Progress in
Mathematical Programming, pp. 29{47. Springer (1989). https://doi.org/10.1007/978-1-4613-9617-8_2

Li, Y., Terlaky, T.: A new class of large neighborhood path-following interior point algorithms for semidefinite
optimization with O �n log Tr(X0S0)"� iteration complexity. SIAM J Optim 20(6), 2853{2875 (2010). https://doi.org/10.1137/080729311

Liu, C., Liu, H., Cong, W.: An O(pnL) iteration primal-dual second-order corrector algorithm for linear programming. Optim Lett 5(4), 729{743 (2011). https://doi.org/10.1007/s11590-010-0242-6

Peng, J., Roos, C., Terlaky, T.: Self-regularity: A New Paradigm for Primal-dual Interior-point Algorithms. Princeton series in applied mathematics. Princeton University Press (2002). https://doi.org/10.2307/j.ctt7sf0f

Pirhaji, M., Mansouri, H., Zangiabadi, M.: An O
????p nL � wide neighborhood interior-point algorithm for semidefinite
optimization. Comput Appl Math 36(1), 145{157 (2017). https://doi.org/10.1007/s40314-015-0220-9

Ploskas, N., Samaras, N.: Linear Programming Using MATLAB R
, vol. 127. Springer (2017). https://doi.org/10.1007/978-3-319-65919-0

Potra, F.A.: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with O(pnL) iteration complexity. Math Program 100(2), 317{337 (2004). https://doi.org/10.1007/
s10107-003-0472-9

Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J Optim 24(1), 1{28 (2014). https://doi.org/10.1137/120884341

Sonnevend, G.: An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: System Modelling and Optimization, pp. 866{875. Springer (1986). https://doi.org/10.1007/
BFb0043914

Yang, X., Zhang, Y., Liu, H.: A wide neighborhood infeasible-interior-point method with arc-search for linear programming. J Appl Math Comput 51(1-2), 209{225 (2016). https://doi.org/10.1007/s12190-015-0900-z

Ye, Y., Todd, M.J., Mizuno, S.: An O????pnL�-iteration homogeneous and self-dual linear programming algorithm. Math
Oper Res 19(1), 53{67 (1994).
https://doi.org/10.1287/moor.19.1.53

ID Code:6771
Deposited By: Ádám Hoffmann
Deposited On:09 Sep 2021 11:00
Last Modified:09 Sep 2021 11:00

Repository Staff Only: item control page

Downloads

Downloads per month over past year

View more statistics