Full-Newton step infeasible interior-point algorithm for SDO problems

Hossein Mansouri

Kybernetika (2012)

  • Volume: 48, Issue: 5, page 907-923
  • ISSN: 0023-5954

Abstract

top
In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the μ + -center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems.

How to cite

top

Mansouri, Hossein. "Full-Newton step infeasible interior-point algorithm for SDO problems." Kybernetika 48.5 (2012): 907-923. <http://eudml.org/doc/251417>.

@article{Mansouri2012,
abstract = {In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the $\mu ^+$-center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems.},
author = {Mansouri, Hossein},
journal = {Kybernetika},
keywords = {semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions; semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions},
language = {eng},
number = {5},
pages = {907-923},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Full-Newton step infeasible interior-point algorithm for SDO problems},
url = {http://eudml.org/doc/251417},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Mansouri, Hossein
TI - Full-Newton step infeasible interior-point algorithm for SDO problems
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 5
SP - 907
EP - 923
AB - In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the $\mu ^+$-center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems.
LA - eng
KW - semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions; semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions
UR - http://eudml.org/doc/251417
ER -

References

top
  1. Alizadeh, F., 10.1137/0805002, SIAM J. Optim. 5 (2006), 13-51. Zbl0833.90087MR1315703DOI10.1137/0805002
  2. Helmberg, C., Semidefinite Programming for Combinatorial Optimization., Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechink Berlin 2000. 
  3. Horn, R. A., Johnson, C. R., Topics in Matrix Analysis., Cambridge University Press, Cambridge 1991. Zbl0801.15001MR1091716
  4. Klerk, E. de, Aspects of Semidefinite Programming., Kluwer Academic Publishers, Dordrecht 2002. Zbl0991.90098MR2064921
  5. Kojima, M., Shida, M., Shindoh, S., 10.1007/BF01581723, Math. Program. 80 (1998), 129-160. MR1489167DOI10.1007/BF01581723
  6. Kojima, M., Megiddo, N., Noma, T., Yoshise, A., 10.1007/3-540-54509-3, Lecture Notes in Comput. Sci. 538, Springer, Berlin 1991. Zbl0745.90069MR1226025DOI10.1007/3-540-54509-3
  7. Luo, Z. Q., Sturm, J., Zhang, S. Z., 10.1137/S1052623496299187, SIAM J. Optim. 8 (1998), 59-81. Zbl0910.90229MR1617436DOI10.1137/S1052623496299187
  8. Lustig, I. J., 10.1007/BF01588785, Math. Program. 49 (1990/1991), 145-162. MR1087451DOI10.1007/BF01588785
  9. Lütkepohl, H., Handbook of Matrices., John Wiley & Sons, Chichester 1996. Zbl0856.15001MR1433592
  10. Mansouri, H., Full-Newton Step Interior-Point Methods for Conic Optimization., Ph.D. Thesis, Faculty of Mathematics and Computer Science, TU Delft, 2008. 
  11. Mansouri, H., Roos, C., 10.1007/s11075-009-9270-7, J. Numer. Algorithms 52 (2009), 2, 225-255. Zbl1180.65079MR2563703DOI10.1007/s11075-009-9270-7
  12. Mansouri, H., Zangiabadi, M., New complexity analysis of full Nesterov-Todd steps for semidefinite optimization., Bull. Iranian Math. Soc. 1 (2011), 269-286. MR2850119
  13. Mansouri, H., Siyavash, T., Zangiabadi, M., A path-following infeasible interior-point algorithm for semidefinite programming., Iranian J. Oper. Res. 3 (2012), 1, 11-30. 
  14. 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
  15. Nesterov, Y. E., Todd, M. J., 10.1137/S1052623495290209, SIAM J. Optim. 8 (1998), 2, 324-364. Zbl0922.90110MR1618802DOI10.1137/S1052623495290209
  16. Peng, J., Roos, C., Terlaky, T., 10.1007/s101070200296, Math. Program. 93 (2002), 129-171. Zbl1007.90037MR1912271DOI10.1007/s101070200296
  17. Potra, F. A., Sheng, R., 10.1137/S1052623495294955, SIAM J. Optim. 8 (1998), 1007-1028. Zbl0917.65058MR1646116DOI10.1137/S1052623495294955
  18. Roos, C., 10.1137/050623917, SIAM J. Optim. 16 (2006), 4, 1110-1136. Zbl1131.90029MR2219135DOI10.1137/050623917
  19. 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 2005.) Zbl0954.65041MR1450094
  20. Wolkowicz, H., Saigal, R., Vandenberghe, L., Handbook of Semidefinite Programming, Theory, Algorithms, and Applications., Kluwer Academic Publishers, Dordrecht 2000. Zbl0962.90001MR1778223
  21. Zhang, Y., 10.1137/S1052623495296115, SIAM J. Optim. 8 (1998), 365-386. Zbl0913.65050MR1618806DOI10.1137/S1052623495296115

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.