New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization

Behrouz Kheirfam; Nezam Mahdavi-Amiri

Kybernetika (2013)

  • Volume: 49, Issue: 6, page 883-896
  • ISSN: 0023-5954

Abstract

top
A full Nesterov-Todd step infeasible interior-point algorithm is proposed for solving linear programming problems over symmetric cones by using the Euclidean Jordan algebra. Using a new approach, we also provide a search direction and show that the iteration bound coincides with the best known bound for infeasible interior-point methods.

How to cite

top

Kheirfam, Behrouz, and Mahdavi-Amiri, Nezam. "New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization." Kybernetika 49.6 (2013): 883-896. <http://eudml.org/doc/260832>.

@article{Kheirfam2013,
abstract = {A full Nesterov-Todd step infeasible interior-point algorithm is proposed for solving linear programming problems over symmetric cones by using the Euclidean Jordan algebra. Using a new approach, we also provide a search direction and show that the iteration bound coincides with the best known bound for infeasible interior-point methods.},
author = {Kheirfam, Behrouz, Mahdavi-Amiri, Nezam},
journal = {Kybernetika},
keywords = {interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity; interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity},
language = {eng},
number = {6},
pages = {883-896},
publisher = {Institute of Information Theory and Automation AS CR},
title = {New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization},
url = {http://eudml.org/doc/260832},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Kheirfam, Behrouz
AU - Mahdavi-Amiri, Nezam
TI - New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 6
SP - 883
EP - 896
AB - A full Nesterov-Todd step infeasible interior-point algorithm is proposed for solving linear programming problems over symmetric cones by using the Euclidean Jordan algebra. Using a new approach, we also provide a search direction and show that the iteration bound coincides with the best known bound for infeasible interior-point methods.
LA - eng
KW - interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity; interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity
UR - http://eudml.org/doc/260832
ER -

References

top
  1. Faraut, J., Korányi, A., Analysis on Symmetric Cones., Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York 1994. Zbl0841.43002MR1446489
  2. Faybusovich, L., 10.1016/S0377-0427(97)00153-2, J. Comput. Appl. Math. 86 (1997), 149-175. Zbl0889.65066MR1491432DOI10.1016/S0377-0427(97)00153-2
  3. Faybusovich, L., 10.1007/s002090100286, Math. Z. 239 (2002), 1, 117-129. Zbl0996.65065MR1879331DOI10.1007/s002090100286
  4. Gu, G., Zangiabadi, M., Roos, C., 10.1016/j.ejor.2011.02.022, European J. Oper. Res. 214 (2011), 3, 473-484. Zbl1245.90144MR2820168DOI10.1016/j.ejor.2011.02.022
  5. Güler, O., 10.1287/moor.21.4.860, Math. Oper. Res. 21 (1996), 4, 860-885. Zbl0867.90090MR1419906DOI10.1287/moor.21.4.860
  6. Muramatsu, M., 10.1023/A:1017920200889, J. Optim. Theory Appl. 112 (2002), 3, 595-625. Zbl0994.90095MR1892239DOI10.1023/A:1017920200889
  7. Nesterov, Y. E., Nemirovski, A., Interior-point Polynomial Algorithms in Convex Programming., SIAM, Philadelphia 1994. MR1258086
  8. Nesterov, Y. E., Todd, M. J., 10.1287/moor.22.1.1, Math. Oper. Res. 22 (1997), 1, 1-42. Zbl0871.90064MR1436572DOI10.1287/moor.22.1.1
  9. Rangarajan, B. K., 10.1137/040606557, SIAM J. Optim. 16 (2006), 4, 1211-1229. Zbl1131.90043MR2219140DOI10.1137/040606557
  10. Roos, C., 10.1137/050623917, SIAM J. Optim. 16 (2006), 4, 1110-1136. Zbl1131.90029MR2219135DOI10.1137/050623917
  11. Roos, C., Terlaky, T., Vial, J.-Ph., Theory and Algorithms for Linear Optimization: An Interior-Point Approach., John Wiley and Sons, Chichester 1997, Second edition Springer 2006. Zbl0954.65041MR1450094
  12. Schmieta, S. H., Alizadeh, F., 10.1007/s10107-003-0380-z, Math. Program. 96 (2003), 3, 409-438. MR1993457DOI10.1007/s10107-003-0380-z
  13. Sturm, J. F., 10.1016/S0024-3795(00)00096-3, Algebra Appl. 312 (2000), 1 - 3, 135-154. Zbl0973.90093MR1759328DOI10.1016/S0024-3795(00)00096-3
  14. Vieira, M. V. C., Jordan Algebraic Approach to Symmetric Optimization., Ph.D. Thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology 2007. 

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.