A new one-step smoothing newton method for second-order cone programming

Jingyong Tang; Guoping He; Li Dong; Liang Fang

Applications of Mathematics (2012)

  • Volume: 57, Issue: 4, page 311-331
  • ISSN: 0862-7940

Abstract

top
In this paper, we present a new one-step smoothing Newton method for solving the second-order cone programming (SOCP). Based on a new smoothing function of the well-known Fischer-Burmeister function, the SOCP is approximated by a family of parameterized smooth equations. Our algorithm solves only one system of linear equations and performs only one Armijo-type line search at each iteration. It can start from an arbitrary initial point and does not require the iterative points to be in the sets of strictly feasible solutions. Without requiring strict complementarity at the SOCP solution, the proposed algorithm is shown to be globally and locally quadratically convergent under suitable assumptions. Numerical experiments demonstrate the feasibility and efficiency of our algorithm.

How to cite

top

Tang, Jingyong, et al. "A new one-step smoothing newton method for second-order cone programming." Applications of Mathematics 57.4 (2012): 311-331. <http://eudml.org/doc/246934>.

@article{Tang2012,
abstract = {In this paper, we present a new one-step smoothing Newton method for solving the second-order cone programming (SOCP). Based on a new smoothing function of the well-known Fischer-Burmeister function, the SOCP is approximated by a family of parameterized smooth equations. Our algorithm solves only one system of linear equations and performs only one Armijo-type line search at each iteration. It can start from an arbitrary initial point and does not require the iterative points to be in the sets of strictly feasible solutions. Without requiring strict complementarity at the SOCP solution, the proposed algorithm is shown to be globally and locally quadratically convergent under suitable assumptions. Numerical experiments demonstrate the feasibility and efficiency of our algorithm.},
author = {Tang, Jingyong, He, Guoping, Dong, Li, Fang, Liang},
journal = {Applications of Mathematics},
keywords = {second-order cone programming; smoothing Newton method; global convergence; quadratic convergence; Fischer-Burmeister function; Euclidean Jordan algebra; local quadratic convergence; Fischer-Burmeister function; Euclidean Jordan algebra; smoothing Newton method; global convergence; local quadratic convergence},
language = {eng},
number = {4},
pages = {311-331},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A new one-step smoothing newton method for second-order cone programming},
url = {http://eudml.org/doc/246934},
volume = {57},
year = {2012},
}

TY - JOUR
AU - Tang, Jingyong
AU - He, Guoping
AU - Dong, Li
AU - Fang, Liang
TI - A new one-step smoothing newton method for second-order cone programming
JO - Applications of Mathematics
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 57
IS - 4
SP - 311
EP - 331
AB - In this paper, we present a new one-step smoothing Newton method for solving the second-order cone programming (SOCP). Based on a new smoothing function of the well-known Fischer-Burmeister function, the SOCP is approximated by a family of parameterized smooth equations. Our algorithm solves only one system of linear equations and performs only one Armijo-type line search at each iteration. It can start from an arbitrary initial point and does not require the iterative points to be in the sets of strictly feasible solutions. Without requiring strict complementarity at the SOCP solution, the proposed algorithm is shown to be globally and locally quadratically convergent under suitable assumptions. Numerical experiments demonstrate the feasibility and efficiency of our algorithm.
LA - eng
KW - second-order cone programming; smoothing Newton method; global convergence; quadratic convergence; Fischer-Burmeister function; Euclidean Jordan algebra; local quadratic convergence; Fischer-Burmeister function; Euclidean Jordan algebra; smoothing Newton method; global convergence; local quadratic convergence
UR - http://eudml.org/doc/246934
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. Bai, Y. Q., Wang, G. Q., Roos, C., Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear Anal., Theory Methods Appl. 70 (2009), 3584-3602. (2009) Zbl1190.90275MR2502767
  3. Chen, B., Xiu, N., 10.1137/S1052623497316191, SIAM J. Optim. 9 (1999), 605-623. (1999) MR1681059DOI10.1137/S1052623497316191
  4. Chen, J. S., Tseng, P., 10.1007/s10107-005-0617-0, Math. Program., Ser B 104 (2005), 293-327. (2005) Zbl1093.90063MR2179239DOI10.1007/s10107-005-0617-0
  5. Clarke, F. H., Optimization and Nonsmooth Analysis, Wiley Sons New York (1983), Reprinted by SIAM, Philadelphia, 1990 0709590. (1983) Zbl0582.49001MR1058436
  6. Debnath, R., Muramatsu, M., Takahashi, H., 10.1007/s10489-005-4609-9, Appl. Intel. 23 (2005), 219-239. (2005) Zbl1080.68618DOI10.1007/s10489-005-4609-9
  7. Faraut, J., Korányi, A., Analysis on Symmetric Cones, Clarendon Press Oxford (1994). (1994) MR1446489
  8. Faybusovich, L., 10.1023/A:1009701824047, Positivity 1 (1997), 331-357. (1997) Zbl0973.90095MR1660399DOI10.1023/A:1009701824047
  9. Fukushima, M., Luo, Z.-Q., Tseng, P., 10.1137/S1052623400380365, SIAM J. Optim. 12 (2002), 436-460. (2002) MR1885570DOI10.1137/S1052623400380365
  10. Hayashi, S., Yamashita, N., Fukushima, M., 10.1137/S1052623403421516, SIAM J. Optim. 15 (2005), 593-615. (2005) Zbl1114.90139MR2144183DOI10.1137/S1052623403421516
  11. Jiang, H., Smoothed Fischer-Burmeister equation methods for the complementarity problem, Technical Report Department of Mathematics, The University of Melbourne Parille, Victoria, Australia, June 1997. 
  12. 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
  13. 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
  14. Monteiro, R. D. C., Tsuchiya, T., 10.1007/PL00011378, Math. Program. 88 (2000), 61-83. (2000) MR1765893DOI10.1007/PL00011378
  15. Ma, C., Chen, X., 10.1016/j.cam.2007.03.031, J. Comput. Appl. Math. 216 (2008), 1-13. (2008) Zbl1140.65046MR2421836DOI10.1016/j.cam.2007.03.031
  16. Mifflin, R., 10.1137/0315061, SIAM J. Control Optim. 15 (1977), 959-972. (1977) Zbl0376.90081MR0461556DOI10.1137/0315061
  17. Nesterov, Y. E., Todd, M. J., 10.1137/S1052623495290209, SIAM J. Optim. 8 (1998), 324-364. (1998) Zbl0922.90110MR1618802DOI10.1137/S1052623495290209
  18. Peng, X., King, I., 10.1016/j.neunet.2007.12.051, Neural Networks 21 (2008), 450-457. (2008) DOI10.1016/j.neunet.2007.12.051
  19. Peng, J., Roos, C., Terlaky, T., 10.1137/S1052623401383236, SIAM J. Optim. 13 (2002), 179-203. (2002) MR1922760DOI10.1137/S1052623401383236
  20. Qi, L., Sun, D., 10.1090/S0025-5718-99-01082-0, Math. Comput. 69 (2000), 283-304. (2000) Zbl0947.90117MR1642766DOI10.1090/S0025-5718-99-01082-0
  21. Qi, L., Sun, D., Zhou, G., 10.1007/s101079900127, Math. Program. 87 (2000), 1-35. (2000) Zbl0989.90124MR1734657DOI10.1007/s101079900127
  22. Qi, L., Sun, J., 10.1007/BF01581275, Math. Program. 58 (1993), 353-367. (1993) Zbl0780.90090MR1216791DOI10.1007/BF01581275
  23. Shivaswamy, P. K., Bhattacharyya, C., Smola, A. J., Second order cone programming approaches for handling missing and uncertain data, J. Mach. Learn. Res. 7 (2006), 1283-1314. (2006) Zbl1222.68305MR2274406
  24. Hayashi, S., Yamashita, N., Fukushima, M., 10.1137/S1052623403421516, SIAM J. Optim. 15 (2005), 593-615. (2005) Zbl1114.90139MR2144183DOI10.1137/S1052623403421516
  25. Sasakawa, T., Tsuchiya, T., 10.1137/S1064827500380350, SIAM J. Sci. Comput. 24 (2003), 1930-1950. (2003) Zbl1163.90796MR2005615DOI10.1137/S1064827500380350
  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. Toh, K. C., Tütüncü, R. H., Todd, M. J., SDPT3 Version 3.02---A MATLAB software for semidefinite-quadratic-linear programming, (2002), http://www.math.nus.edu.sg/ mattohkc/sdpt3.html. (2002) 
  28. Tseng, P., 10.1007/978-1-4757-3226-9_24, Nonlinear Optimization and Related Topics G. Di Pillo, F. Giannessi Kluwer Academic Publishers Dordrecht Appl. Optim. 36 (2000), 445-462. (2000) Zbl0965.65091MR1777934DOI10.1007/978-1-4757-3226-9_24

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.