A globally convergent non-interior point algorithm with full Newton step for second-order cone programming

Liang Fang; Guoping He; Li Sun

Applications of Mathematics (2009)

  • Volume: 54, Issue: 5, page 447-464
  • ISSN: 0862-7940

Abstract

top
A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.

How to cite

top

Fang, Liang, He, Guoping, and Sun, Li. "A globally convergent non-interior point algorithm with full Newton step for second-order cone programming." Applications of Mathematics 54.5 (2009): 447-464. <http://eudml.org/doc/37832>.

@article{Fang2009,
abstract = {A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of $A$ to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.},
author = {Fang, Liang, He, Guoping, Sun, Li},
journal = {Applications of Mathematics},
keywords = {non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central path; non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central path},
language = {eng},
number = {5},
pages = {447-464},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A globally convergent non-interior point algorithm with full Newton step for second-order cone programming},
url = {http://eudml.org/doc/37832},
volume = {54},
year = {2009},
}

TY - JOUR
AU - Fang, Liang
AU - He, Guoping
AU - Sun, Li
TI - A globally convergent non-interior point algorithm with full Newton step for second-order cone programming
JO - Applications of Mathematics
PY - 2009
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 54
IS - 5
SP - 447
EP - 464
AB - A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of $A$ to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm.
LA - eng
KW - non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central path; non-interior point algorithm; second-order cone programming; Jordan product; optimality condition; central path
UR - http://eudml.org/doc/37832
ER -

References

top
  1. Alizadeh, F., Goldfarb, D., 10.1007/s10107-002-0339-5, Math. Program. 95 (2003), 3-51. (2003) Zbl1153.90522MR1971381DOI10.1007/s10107-002-0339-5
  2. Benson, H. Y., Vanderbei, R. J., 10.1007/s10107-002-0350-x, Math. Program. Ser. B 95 (2003), 279-302. (2003) Zbl1030.90138MR1976482DOI10.1007/s10107-002-0350-x
  3. Ben-Tal, A., Nemirovski, A., 10.1287/moor.26.2.193.10561, Math. Oper. Res. 26 (2001), 193-205. (2001) Zbl1082.90133MR1895823DOI10.1287/moor.26.2.193.10561
  4. Chen, X. D., Sun, D., Sun, J., 10.1023/A:1022996819381, Comput. Optim. Appl. 25 (2003), 39-56. (2003) Zbl1038.90084MR1996662DOI10.1023/A:1022996819381
  5. Choi, I. C., Monma, C. L., Shanno, D., 10.1287/ijoc.2.4.304, ORSA J. Comput. 2 (1990), 304-311. (1990) DOI10.1287/ijoc.2.4.304
  6. Faraut, J., Korányi, A., Analysis on Symmetric Cones, Oxford University Press Oxford (1994). (1994) MR1446489
  7. Faybusovich, L., 10.1023/A:1009701824047, Positivity 1 (1997), 331-357. (1997) Zbl0973.90095MR1660399DOI10.1023/A:1009701824047
  8. Faybusovich, L., 10.1016/S0377-0427(97)00153-2, J. Comput. Appl. Math. 86 (1997), 149-175. (1997) Zbl0889.65066MR1491432DOI10.1016/S0377-0427(97)00153-2
  9. Fukushima, M., Luo, Z.-Q., Tseng, P., 10.1137/S1052623400380365, SIAM J. Optim. 12 (2002), 436-460. (2002) MR1885570DOI10.1137/S1052623400380365
  10. Han, Q. M., 10.1016/S0096-3003(97)10113-8, Appl. Math. Comput. 95 (1998), 275-289. (1998) Zbl0938.90054MR1633814DOI10.1016/S0096-3003(97)10113-8
  11. Hayashi, S., Yamashita, N., Fukushima, M., 10.1137/S1052623403421516, SIAM J. Optim. 15 (2005), 593-615. (2005) Zbl1114.90139MR2144183DOI10.1137/S1052623403421516
  12. He, B. S., Liao, L. Z., Han, D. R., Yang, H., 10.1007/s101070100280, Math. Program. 92 (2002), 103-118. (2002) MR1892298DOI10.1007/s101070100280
  13. Huang, Z., Gu, W., 10.1007/s00245-007-9004-y, Appl. Math. Optim. 57 (2008), 17-29. (2008) Zbl1190.90236MR2373004DOI10.1007/s00245-007-9004-y
  14. Kim, S., Kojima, M., 10.1080/10556780108805819, Optim. Methods Softw. 15 (2001), 201-224. (2001) MR1892585DOI10.1080/10556780108805819
  15. Kuo, Y. J., Mittelmann, H. D., 10.1023/B:COAP.0000033964.95511.23, Comput. Optim. Appl. 28 (2004), 255-285. (2004) Zbl1084.90046MR2080003DOI10.1023/B:COAP.0000033964.95511.23
  16. Liu, Y., Zhang, L., Wang, Y., 10.1007/BF02896466, J. Appl. Math. Comput. 22 (2006), 133-148. (2006) Zbl1132.90353MR2248446DOI10.1007/BF02896466
  17. Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H., Applications of second order cone programming, Linear Algebra Appl. 284 (1998), 193-228. (1998) Zbl0946.90050MR1655138
  18. Monteiro, R. D. C., Tsuchiya, T., 10.1007/PL00011378, Math. Program. 88 (2000), 61-83. (2000) Zbl0967.65077MR1765893DOI10.1007/PL00011378
  19. Monteiro, R. D. C., Zhang, Y., 10.1007/BF01580085, Math. Program. 81 (1998), 281-299. (1998) MR1617748DOI10.1007/BF01580085
  20. Nesterov, Yu. E., Nemirovskii, A. S., Interior-Point Polynomial Algorithms in Convex Programming, SIAM Philadelphia (1994). (1994) Zbl0824.90112MR1258086
  21. Rangarajan, B. K., 10.1137/040606557, SIAM J. Optim. 16 (2006), 1211-1229. (2006) Zbl1131.90043MR2219140DOI10.1137/040606557
  22. Rangarajan, B., Todd, M. J., Convergence of infeasible-interior-point methods for self-scaled conic programming. Technical Report 1388, School of OR & IE, Cornell University. 
  23. Schmieta, S. H., Alizadeh, F., 10.1007/s10107-003-0380-z, Math. Program. 96 (2003), 409-438. (2003) MR1993457DOI10.1007/s10107-003-0380-z
  24. Schmieta, S. H., Alizadeh, F., 10.1287/moor.26.3.543.10582, Math. Oper. Res. 26 (2001), 543-564. (2001) Zbl1073.90572MR1849884DOI10.1287/moor.26.3.543.10582
  25. Schmieta, S. H., Alizadeh, F., Extension of commutative class of primal-dual interior point algorithms to symmetric cones. Technical Report RRR 13-99, RUTCOR, Rutgers University, August 1999. 
  26. Sun, D., Sun, J., 10.1007/s10107-005-0577-4, Math. Program., Ser. A 103 (2005), 575-581. (2005) Zbl1099.90062MR2166550DOI10.1007/s10107-005-0577-4
  27. Todd, M., 10.1017/S0962492901000071, Acta Numerica 10 (2001), 515-560. (2001) Zbl1105.65334MR2009698DOI10.1017/S0962492901000071
  28. Toh, K. C., Todd, M. J., Tütüncü, R. H., 10.1080/10556789908805762, Optim. Methods Softw. 11 (1999), 545-581. (1999) MR1778429DOI10.1080/10556789908805762
  29. Tsuchiya, T., 10.1080/10556789908805750, Optim. Methods Softw. 11 (1999), 141-182. (1999) Zbl0957.90129MR1777456DOI10.1080/10556789908805750
  30. Tsuchiya, T., A polynomial primal-dual path-following algorithm for second-order cone programming. Technical Report No. 649, The Institute of Statistical Mathematics Tokyo (1997). (1997) 
  31. Wang, S. L., Yang, H., He, B. S., 10.1016/S0898-1221(00)85004-X, Comput. Math. Appl. 40 (2000), 927-937. (2000) Zbl0959.49009MR1781888DOI10.1016/S0898-1221(00)85004-X
  32. Wright, S. J., Primal-Dual Interior Point Methods, Society for Industrial and Applied Mathematics (SIAM) Philadelphia (1997). (1997) Zbl0863.65031MR1422257
  33. Xue, G. L., Ye, Y. Y., 10.1137/S1052623495288362, SIAM J. Optim. 7 (1997), 1017-1036. (1997) Zbl0885.68074MR1479612DOI10.1137/S1052623495288362
  34. Zhang, Y., 10.1137/S1052623495296115, SIAM J. Optim. 8 (1998), 365-386. (1998) Zbl0913.65050MR1618806DOI10.1137/S1052623495296115

NotesEmbed ?

top

You must be logged in to post comments.