| Title:
|
An adaptive long step interior point algorithm for linear optimization (English) |
| Author:
|
Salahi, Maziar |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
46 |
| Issue:
|
4 |
| Year:
|
2010 |
| Pages:
|
722-729 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
It is well known that a large neighborhood interior point algorithm for linear optimization performs much better in implementation than its small neighborhood counterparts. One of the key elements of interior point algorithms is how to update the barrier parameter. The main goal of this paper is to introduce an ``adaptive'' long step interior-point algorithm in a large neighborhood of central path using the classical logarithmic barrier function having $O(n\operatorname{log}\frac{(x^0)^Ts^0}{\epsilon})$ iteration complexity analogous to the classical long step algorithms. Preliminary encouraging numerical results are reported. (English) |
| Keyword:
|
linear optimization |
| Keyword:
|
interior point methods |
| Keyword:
|
long step algorithms |
| Keyword:
|
large neighborhood |
| Keyword:
|
polynomial complexity |
| MSC:
|
90C05 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 1203.90110 |
| idMR:
|
MR2722097 |
| . |
| Date available:
|
2010-10-22T05:28:59Z |
| Last updated:
|
2013-09-21 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140780 |
| . |
| Reference:
|
[1] Mehrotra, S.: On the implementation of a (primal-dual) interior point method. SIAM J. Optim. 2 (1992), 575–601. Zbl 0773.90047, MR 1186163, 10.1137/0802028 |
| Reference:
|
[2] Mizuno, S., Todd, M. J., Ye, Y.: On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18 (1993), 4, 964–981. Zbl 0810.90091, MR 1251690, 10.1287/moor.18.4.964 |
| Reference:
|
[3] Potra, F. A.: A superliner convergent predictor–corrector method for degenerate LCP in a wide neighborhood of the central path with $O(\sqrt{n}L)$-iteration complexity. Math. Program. Ser. A 100 (2004), 2, 317–337. MR 2062930, 10.1007/s10107-003-0472-9 |
| Reference:
|
[4] Roos, C., Terlaky, T., Vial, J. P.: Interior Ooint Algorithms for Linear Optimization.Second edition. Springer Science, 2005. |
| Reference:
|
[5] Salahi, M., Terlaky, T.: A hybrid adaptive algorithm for linear optimization. Asia-Pacific J. Oper. Res. 26 (2009), 2, 235–256. Zbl 1168.90616, MR 2536039, 10.1142/S0217595909002183 |
| Reference:
|
[6] Sonnevend, G.: An “analytic center" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming.In: Proc. 12th IFIP Conference System Modeling and Optimization (A. Prékopa, J. Szelezsán, and B. Strazicky, eds.), Budapest 1985. Lecture Notes in Control and Information Sciences, pp. 866–876. Springer Verlag, Berlin, 1986. MR 0903521 |
| Reference:
|
[7] Wright, S. J.: Primal-dual Interior-point Methods.SIAM, Philadelphia 1997. Zbl 0863.65031, MR 1422257 |
| Reference:
|
[8] Zhao, G.: Interior–point algorithms for linear complementarity problems based on large neighborhoods of the central path. SIAM J. Optim. 8 (1998), 397-�413. Zbl 0913.90254, MR 1618810, 10.1137/S1052623494275574 |
| . |
