An adaptive long step interior point algorithm for linear optimization
Kybernetika (2010)
- Volume: 46, Issue: 4, page 722-729
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topSalahi, Maziar. "An adaptive long step interior point algorithm for linear optimization." Kybernetika 46.4 (2010): 722-729. <http://eudml.org/doc/196452>.
@article{Salahi2010,
abstract = {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.},
author = {Salahi, Maziar},
journal = {Kybernetika},
keywords = {linear optimization; interior point methods; long step algorithms; large neighborhood; polynomial complexity; linear optimization; interior point methods; long step algorithms; large neighborhood; polynomial complexity},
language = {eng},
number = {4},
pages = {722-729},
publisher = {Institute of Information Theory and Automation AS CR},
title = {An adaptive long step interior point algorithm for linear optimization},
url = {http://eudml.org/doc/196452},
volume = {46},
year = {2010},
}
TY - JOUR
AU - Salahi, Maziar
TI - An adaptive long step interior point algorithm for linear optimization
JO - Kybernetika
PY - 2010
PB - Institute of Information Theory and Automation AS CR
VL - 46
IS - 4
SP - 722
EP - 729
AB - 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.
LA - eng
KW - linear optimization; interior point methods; long step algorithms; large neighborhood; polynomial complexity; linear optimization; interior point methods; long step algorithms; large neighborhood; polynomial complexity
UR - http://eudml.org/doc/196452
ER -
References
top- Mehrotra, S., 10.1137/0802028, SIAM J. Optim. 2 (1992), 575–601. (1992) Zbl0773.90047MR1186163DOI10.1137/0802028
- Mizuno, S., Todd, M. J., Ye, Y., 10.1287/moor.18.4.964, Math. Oper. Res. 18 (1993), 4, 964–981. (1993) Zbl0810.90091MR1251690DOI10.1287/moor.18.4.964
- Potra, F. A., 10.1007/s10107-003-0472-9, Math. Program. Ser. A 100 (2004), 2, 317–337. (2004) MR2062930DOI10.1007/s10107-003-0472-9
- Roos, C., Terlaky, T., Vial, J. P., Interior Ooint Algorithms for Linear Optimization, Second edition. Springer Science, 2005. (2005)
- Salahi, M., Terlaky, T., 10.1142/S0217595909002183, Asia-Pacific J. Oper. Res. 26 (2009), 2, 235–256. (2009) Zbl1168.90616MR2536039DOI10.1142/S0217595909002183
- 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. (1985) MR0903521
- Wright, S. J., Primal-dual Interior-point Methods, SIAM, Philadelphia 1997. (1997) Zbl0863.65031MR1422257
- Zhao, G., 10.1137/S1052623494275574, SIAM J. Optim. 8 (1998), 397-�413. (1998) Zbl0913.90254MR1618810DOI10.1137/S1052623494275574
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.