A smoothing Newton method for the second-order cone complementarity problem

Jingyong Tang; Guoping He; Li Dong; Liang Fang; Jinchuan Zhou

Applications of Mathematics (2013)

  • Volume: 58, Issue: 2, page 223-247
  • ISSN: 0862-7940

Abstract

top
In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.

How to cite

top

Tang, Jingyong, et al. "A smoothing Newton method for the second-order cone complementarity problem." Applications of Mathematics 58.2 (2013): 223-247. <http://eudml.org/doc/252504>.

@article{Tang2013,
abstract = {In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.},
author = {Tang, Jingyong, He, Guoping, Dong, Li, Fang, Liang, Zhou, Jinchuan},
journal = {Applications of Mathematics},
keywords = {second-order cone complementarity problem; smoothing function; smoothing Newton method; global convergence; quadratic convergence; second-order cone complementarity problem; smoothing function; smoothing Newton method; global convergence; quadratic convergence},
language = {eng},
number = {2},
pages = {223-247},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A smoothing Newton method for the second-order cone complementarity problem},
url = {http://eudml.org/doc/252504},
volume = {58},
year = {2013},
}

TY - JOUR
AU - Tang, Jingyong
AU - He, Guoping
AU - Dong, Li
AU - Fang, Liang
AU - Zhou, Jinchuan
TI - A smoothing Newton method for the second-order cone complementarity problem
JO - Applications of Mathematics
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 58
IS - 2
SP - 223
EP - 247
AB - In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.
LA - eng
KW - second-order cone complementarity problem; smoothing function; smoothing Newton method; global convergence; quadratic convergence; second-order cone complementarity problem; smoothing function; smoothing Newton method; global convergence; quadratic convergence
UR - http://eudml.org/doc/252504
ER -

References

top
  1. Burke, J., Xu, S., A non-interior predictor-corrector path-following algorithm for LCP, Reformulation: Nonsmooth, Piecewise Smooth and Smoothing Methods M. Fukushima, L. Qi Kluwer Academic Publishers Boston (1999), 45-63. (1999) MR1682736
  2. Burke, J., Xu, S., 10.1007/s101079900111, Math. Program. 87 (2000), 113-130. (2000) Zbl1081.90603MR1734661DOI10.1007/s101079900111
  3. Chen, B., Chen, X., 10.1137/S1052623497321109, SIAM J. Optim. 9 (1999), 624-645. (1999) MR1681055DOI10.1137/S1052623497321109
  4. Chen, B., Chen, X., 10.1023/A:1026546230851, Comput. Optim. Appl. 17 (2000), 131-158. (2000) Zbl0987.90079MR1806250DOI10.1023/A:1026546230851
  5. Chen, B., Xiu, N., 10.1137/S1052623497316191, SIAM J. Optim. 9 (1999), 605-623. (1999) Zbl1037.90052MR1681059DOI10.1137/S1052623497316191
  6. Chen, J., A new merit function and its related properties for the second-order cone complementarity problem, Pac. J. Optim. 2 (2006), 167-179. (2006) Zbl1178.90324MR2548216
  7. Chen, J., Chen, X., Tseng, P., 10.1007/s10107-004-0538-3, Math. Program. 101 (2004), 95-117. (2004) Zbl1065.49013MR2085260DOI10.1007/s10107-004-0538-3
  8. Chen, J., Tseng, P., 10.1007/s10107-005-0617-0, Math. Program. 104 (2005), 293-327. (2005) Zbl1093.90063MR2179239DOI10.1007/s10107-005-0617-0
  9. Chen, X. D., Sun, D., Sun, J., 10.1023/A:1022996819381, Comput. Optim. Appl. 25 (2003), 39-56. (2003) Zbl1038.90084MR1996662DOI10.1023/A:1022996819381
  10. Chi, X. N., Liu, S. Y., 10.1007/s12190-008-0057-0, J. Appl. Math. Comput. 27 (2008), 47-61. (2008) Zbl1193.90169MR2403140DOI10.1007/s12190-008-0057-0
  11. Chi, X. N., Liu, S. Y., 10.1016/j.cam.2007.12.023, J. Comput. Appl. Math. 223 (2009), 114-123. (2009) Zbl1155.65045MR2463105DOI10.1016/j.cam.2007.12.023
  12. Chi, X. N., Liu, S. Y., 10.1080/02331930701763421, Optimization 58 (2009), 965-979. (2009) Zbl1177.90318MR2572781DOI10.1080/02331930701763421
  13. Clarke, F. H., Optimization and Nonsmooth Analysis, John Wiley & Sons New York (1983), reprinted by SIAM, Philadelphia, 1990. (1983) Zbl0582.49001MR0709590
  14. Fang, L., 10.1016/j.amc.2010.02.001, Appl. Math. Comput. 216 (2010), 1087-1095. (2010) Zbl1239.65034MR2607218DOI10.1016/j.amc.2010.02.001
  15. Fang, L., He, G. P., Hu, Y. H., 10.1016/j.amc.2009.06.029, Appl. Math. Comput. 215 (2009), 1020-1029. (2009) Zbl1183.65065MR2568957DOI10.1016/j.amc.2009.06.029
  16. Fukushima, M., Luo, Z., Tseng, P., 10.1137/S1052623400380365, SIAM J. Optim. 12 (2002), 436-460. (2002) MR1885570DOI10.1137/S1052623400380365
  17. Hayashi, S., Yamashita, N., Fukushima, M., 10.1137/S1052623403421516, SIAM J. Optimization 15 (2005), 593-615. (2005) MR2144183DOI10.1137/S1052623403421516
  18. Huang, Z. H., Han, J. Y., Xu, D. C., Zhang, L. P., 10.1007/BF02877427, Sci. China, Ser. A 44 (2001), 1107-1114. (2001) Zbl1002.90072MR1860828DOI10.1007/BF02877427
  19. 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
  20. 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
  21. Mifflin, R., 10.1137/0315061, SIAM J. Control. Optim. 15 (1977), 957-972. (1977) Zbl0376.90081MR0461556DOI10.1137/0315061
  22. Pan, S. H., Chen, J. S., 10.1007/s00245-008-9054-9, Appl. Math. Optim. 59 (2009), 293-318. (2009) Zbl1169.49031MR2491700DOI10.1007/s00245-008-9054-9
  23. Pan, S. H., Chen, J. S., 10.1080/02331930903085359, Optimization 59 (2010), 1173-1197. (2010) Zbl1229.90239MR2738600DOI10.1080/02331930903085359
  24. Qi, L., 10.1287/moor.18.1.227, Math. Oper. Res. 18 (1993), 227-244. (1993) Zbl0776.65037MR1250115DOI10.1287/moor.18.1.227
  25. Qi, L., Sun, J., 10.1007/BF01581275, Math. Program. 58 (1993), 353-367. (1993) Zbl0780.90090MR1216791DOI10.1007/BF01581275
  26. Qi, L., Sun, D., 10.1090/S0025-5718-99-01082-0, Math. Comput. 69 (2000), 283-304. (2000) MR1642766DOI10.1090/S0025-5718-99-01082-0
  27. Qi, L., Sun, D., Zhou, G., 10.1007/s101079900127, Math. Program. 87 (2000), 1-35. (2000) Zbl0989.90124MR1734657DOI10.1007/s101079900127
  28. Tang, J. Y., He, G. P., 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
  29. Toh, K. C., Tütüncü, R. H., Todd, M. J., SDPT3 Version 3.02-A MATLAB software for semidefinite-quadratic-linear programming, 2000.http://www.math.nus.edu.sg/ mattohkc/sdpt3.html, . 
  30. Yoshise, A., 10.1137/04061427X, SIAM J. Optim. 17 (2006), 1129-1153. (2006) Zbl1136.90039MR2274506DOI10.1137/04061427X
  31. Zhang, L., Han, J., Huang, Z., 10.1007/s10114-004-0412-5, Acta Math. Sin. 21 (2005), 117-128. (2005) Zbl1124.90037MR2128829DOI10.1007/s10114-004-0412-5
  32. Zhang, J., Zhang, K., 10.1016/j.cam.2008.06.012, J. Comput. Appl. Math. 225 (2009), 1-8. (2009) Zbl1163.65043MR2490165DOI10.1016/j.cam.2008.06.012
  33. Zhou, G., Sun, D., Qi, L., Numerical experiments for a class of squared smoothing Newton methods for box constrained variational inequality problems, Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods M. Fukushima, L. Qi Kluwer Academic Publishers Boston (1999), 421-441. (1999) Zbl0928.65080MR1682739

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.