Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
second-order cone programming; smoothing Newton algorithm; non-monotone line search; convergence
second-order cone programming; smoothing Newton algorithm; non-monotone line search; convergence
Summary:
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.
References:
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95 (2003), 3-51. DOI 10.1007/s10107-002-0339-5 | MR 1971381 | Zbl 1153.90522
[2] Chi, X., Liu, S.: A non-interior continuation method for second-order cone programming. Optimization 58 (2009), 965-979. DOI 10.1080/02331930701763421 | MR 2572781 | Zbl 1177.90318
[3] Chi, X., Liu, S.: A one-step smoothing Newton method for second-order cone programming. J. Comput. Appl. Math. 223 (2009), 114-123. DOI 10.1016/j.cam.2007.12.023 | MR 2463105 | Zbl 1155.65045
[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. MR 1058436 | Zbl 0696.49002
[5] Fang, L., Feng, Z.: A smoothing Newton-type method for second-order cone programming problems based on a new smoothing Fischer-Burmeister function. Comput. Appl. Math. 30 (2011), 569-588. DOI 10.1590/S1807-03022011000300005 | MR 2863924
[6] Fang, L., He, G., Hu, Y.: A new smoothing Newton-type method for second-order cone programming problems. Appl. Math. Comput. 215 (2009), 1020-1029. DOI 10.1016/j.amc.2009.06.029 | MR 2568957 | Zbl 1183.65065
[7] Fukushima, M., Luo, Z.-Q., Tseng, P.: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12 (2002), 436-460. DOI 10.1137/S1052623400380365 | MR 1885570
[8] Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton's method. SIAM J. Numer. Anal. 23 (1986), 707-716. DOI 10.1137/0723046 | MR 0849278 | Zbl 0616.65067
[9] Hu, S.-L., Huang, Z.-H., Wang, P.: A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. Optim. Methods Softw. 24 (2009), 447-460. DOI 10.1080/10556780902769862 | MR 2533101 | Zbl 1173.90552
[10] Huang, Z. H., Han, J., Chen, Z.: Predictor-corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a $P_0$-function. J. Optimization Theory Appl. 117 (2003), 39-68. DOI 10.1023/A:1023648305969 | MR 1990070 | Zbl 1044.90081
[11] Huang, Z. H., Hu, S. L., Han, J.: Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search. Sci. China, Ser. A 52 (2009), 833-848. DOI 10.1007/s11425-008-0170-4 | MR 2504979 | Zbl 1203.90123
[12] Huang, Z.-H., Ni, T.: Smoothing algorithms for complementarity problems over symmetric cones. Comput. Optim. Appl. 45 (2010), 557-579. DOI 10.1007/s10589-008-9180-y | MR 2600896 | Zbl 1198.90373
[13] Liu, X.-H., Huang, Z.-H.: A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones. Math. Methods Oper. Res. 70 (2009), 385-404. DOI 10.1007/s00186-008-0274-1 | MR 2558418 | Zbl 1175.90290
[14] Liu, Y.-J., Zhang, L.-W., Wang, Y.-H.: Analysis of a smoothing method for symmetric conic linear programming. J. Appl. Math. Comput. 22 (2006), 133-148. DOI 10.1007/BF02896466 | MR 2248446 | Zbl 1132.90353
[15] Lobo, M. S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284 (1998), 193-228. MR 1655138 | Zbl 0946.90050
[16] Ni, T., Wang, P.: A smoothing-type algorithm for solving nonlinear complementarity problems with a non-monotone line search. Appl. Math. Comput. 216 (2010), 2207-2214. DOI 10.1016/j.amc.2010.03.058 | MR 2647089 | Zbl 1194.65080
[17] Pan, S., Chen, J.-S.: A damped Gauss-Newton method for the second-order cone complementarity problem. Appl. Math. Optim. 59 (2009), 293-318. DOI 10.1007/s00245-008-9054-9 | MR 2491700 | Zbl 1169.49031
[18] Tang, J., He, G., Dong, L., Fang, L.: A smoothing Newton method for second-order cone optimization based on a new smoothing function. Appl. Math. Comput. 218 (2011), 1317-1329. DOI 10.1016/j.amc.2011.06.015 | MR 2831640 | Zbl 1229.65101
[19] Tang, J., He, G., Dong, L., Fang, L.: A new one-step smoothing Newton method for second-order cone programming. Appl. Math., Praha 57 (2012), 311-331. DOI 10.1007/s10492-012-0019-6 | MR 2984606 | Zbl 1265.90229
[20] Zhang, H., Hager, W. W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14 (2004), 1043-1056. DOI 10.1137/S1052623403428208 | MR 2112963 | Zbl 1073.90024
Search
Partner of
