Analysis of a non-monotone smoothing-type algorithm for the second-order cone programming

Jingyong Tang; Li Dong; Liang Fang; Li Sun

Applications of Mathematics (2015)

  • Volume: 60, Issue: 1, page 35-49
  • ISSN: 0862-7940

Abstract

top
The smoothing-type algorithm is a powerful tool for solving the second-order cone programming (SOCP), which is in general designed based on a monotone line search. In this paper, we propose a smoothing-type algorithm for solving the SOCP with a non-monotone line search. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. The preliminary numerical results are also reported which indicate that the non-monotone smoothing-type algorithm is promising for solving the SOCP.

How to cite

top

Tang, Jingyong, et al. "Analysis of a non-monotone smoothing-type algorithm for the second-order cone programming." Applications of Mathematics 60.1 (2015): 35-49. <http://eudml.org/doc/262175>.

@article{Tang2015,
abstract = {The smoothing-type algorithm is a powerful tool for solving the second-order cone programming (SOCP), which is in general designed based on a monotone line search. In this paper, we propose a smoothing-type algorithm for solving the SOCP with a non-monotone line search. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. The preliminary numerical results are also reported which indicate that the non-monotone smoothing-type algorithm is promising for solving the SOCP.},
author = {Tang, Jingyong, Dong, Li, Fang, Liang, Sun, Li},
journal = {Applications of Mathematics},
keywords = {second-order cone programming; smoothing Newton algorithm; non-monotone line search; convergence; second-order cone programming; smoothing Newton algorithm; non-monotone line search; global convergence; local quadratic convergence},
language = {eng},
number = {1},
pages = {35-49},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Analysis of a non-monotone smoothing-type algorithm for the second-order cone programming},
url = {http://eudml.org/doc/262175},
volume = {60},
year = {2015},
}

TY - JOUR
AU - Tang, Jingyong
AU - Dong, Li
AU - Fang, Liang
AU - Sun, Li
TI - Analysis of a non-monotone smoothing-type algorithm for the second-order cone programming
JO - Applications of Mathematics
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 60
IS - 1
SP - 35
EP - 49
AB - The smoothing-type algorithm is a powerful tool for solving the second-order cone programming (SOCP), which is in general designed based on a monotone line search. In this paper, we propose a smoothing-type algorithm for solving the SOCP with a non-monotone line search. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. The preliminary numerical results are also reported which indicate that the non-monotone smoothing-type algorithm is promising for solving the SOCP.
LA - eng
KW - second-order cone programming; smoothing Newton algorithm; non-monotone line search; convergence; second-order cone programming; smoothing Newton algorithm; non-monotone line search; global convergence; local quadratic convergence
UR - http://eudml.org/doc/262175
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. Chi, X., Liu, S., 10.1080/02331930701763421, Optimization 58 (2009), 965-979. (2009) Zbl1177.90318MR2572781DOI10.1080/02331930701763421
  3. Chi, X., Liu, S., 10.1016/j.cam.2007.12.023, J. Comput. Appl. Math. 223 (2009), 114-123. (2009) Zbl1155.65045MR2463105DOI10.1016/j.cam.2007.12.023
  4. Clarke, F. H., Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts. John Wiley & Sons New York (1983); reprinted by SIAM, Philadelphia, 1990. Zbl0696.49002MR1058436
  5. Fang, L., Feng, Z., 10.1590/S1807-03022011000300005, Comput. Appl. Math. 30 (2011), 569-588. (2011) MR2863924DOI10.1590/S1807-03022011000300005
  6. Fang, L., He, G., Hu, Y., 10.1016/j.amc.2009.06.029, Appl. Math. Comput. 215 (2009), 1020-1029. (2009) Zbl1183.65065MR2568957DOI10.1016/j.amc.2009.06.029
  7. Fukushima, M., Luo, Z.-Q., Tseng, P., 10.1137/S1052623400380365, SIAM J. Optim. 12 (2002), 436-460. (2002) MR1885570DOI10.1137/S1052623400380365
  8. Grippo, L., Lampariello, F., Lucidi, S., 10.1137/0723046, SIAM J. Numer. Anal. 23 (1986), 707-716. (1986) Zbl0616.65067MR0849278DOI10.1137/0723046
  9. Hu, S.-L., Huang, Z.-H., Wang, P., 10.1080/10556780902769862, Optim. Methods Softw. 24 (2009), 447-460. (2009) Zbl1173.90552MR2533101DOI10.1080/10556780902769862
  10. Huang, Z. H., Han, J., Chen, Z., 10.1023/A:1023648305969, J. Optimization Theory Appl. 117 (2003), 39-68. (2003) Zbl1044.90081MR1990070DOI10.1023/A:1023648305969
  11. Huang, Z. H., Hu, S. L., Han, J., 10.1007/s11425-008-0170-4, Sci. China, Ser. A 52 (2009), 833-848. (2009) Zbl1203.90123MR2504979DOI10.1007/s11425-008-0170-4
  12. Huang, Z.-H., Ni, T., 10.1007/s10589-008-9180-y, Comput. Optim. Appl. 45 (2010), 557-579. (2010) Zbl1198.90373MR2600896DOI10.1007/s10589-008-9180-y
  13. Liu, X.-H., Huang, Z.-H., 10.1007/s00186-008-0274-1, Math. Methods Oper. Res. 70 (2009), 385-404. (2009) Zbl1175.90290MR2558418DOI10.1007/s00186-008-0274-1
  14. Liu, Y.-J., Zhang, L.-W., Wang, Y.-H., 10.1007/BF02896466, J. Appl. Math. Comput. 22 (2006), 133-148. (2006) Zbl1132.90353MR2248446DOI10.1007/BF02896466
  15. 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
  16. Ni, T., Wang, P., 10.1016/j.amc.2010.03.058, Appl. Math. Comput. 216 (2010), 2207-2214. (2010) Zbl1194.65080MR2647089DOI10.1016/j.amc.2010.03.058
  17. Pan, S., Chen, J.-S., 10.1007/s00245-008-9054-9, Appl. Math. Optim. 59 (2009), 293-318. (2009) Zbl1169.49031MR2491700DOI10.1007/s00245-008-9054-9
  18. Tang, J., He, G., Dong, L., Fang, L., 10.1016/j.amc.2011.06.015, Appl. Math. Comput. 218 (2011), 1317-1329. (2011) Zbl1229.65101MR2831640DOI10.1016/j.amc.2011.06.015
  19. Tang, J., He, G., Dong, L., Fang, L., 10.1007/s10492-012-0019-6, Appl. Math., Praha 57 (2012), 311-331. (2012) Zbl1265.90229MR2984606DOI10.1007/s10492-012-0019-6
  20. Zhang, H., Hager, W. W., 10.1137/S1052623403428208, SIAM J. Optim. 14 (2004), 1043-1056. (2004) Zbl1073.90024MR2112963DOI10.1137/S1052623403428208

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.