×

zbMATH — the first resource for mathematics

Analysis of a non-interior continuation method for second-order cone programming. (English) Zbl 1193.90169
Summary: Based on the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, a non-interior continuation method is presented for solving the second-order cone programming (SOCP). Our algorithm reformulates the SOCP as a nonlinear system of equations and then applies Newton’s method to the perturbation of this system. The proposed algorithm does not have restrictions regarding its starting point and solves at most one linear system of equations at each iteration. Under suitable assumptions, the algorithm is shown to be globally and locally quadratically convergent. Some numerical results are also included which indicate that our algorithm is promising and comparable to interior-point methods.

MSC:
90C25 Convex programming
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
Software:
SDPT3
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003) · Zbl 1153.90522
[2] Burke, J., Xu, S.: A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Math. Program. 87, 113–130 (2000) · Zbl 1081.90603
[3] Chen, X., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998) · Zbl 0894.90143
[4] Chen, X.D., Sun, D., Sun, J.: Complementarity functions and numerical experiments on smoothing Newton methods for second-order-cone complementarity problems. Comput. Optim. Appl. 25, 39–56 (2003) · Zbl 1038.90084
[5] Chen, X., Tseng, P.: Non-interior continuation methods for solving semidefinite complementarity problems. Math. Program. 95, 431–474 (2003) · Zbl 1023.90046
[6] Chen, B., Xiu, N.: A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions. SIAM J. Optim. 9, 605–623 (1999) · Zbl 1037.90052
[7] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[8] Engelke, S., Kanzow, C.: Improved smoothing-type methods for the solution of linear programs. Numer. Math. 90, 487–507 (2002) · Zbl 0994.65065
[9] Engelke, S., Kanzow, C.: Predictor-corrector smoothing methods for linear programs with a more flexible update of the smoothing parameter. Comput. Optim. Appl. 23, 299–320 (2002) · Zbl 1028.90026
[10] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford University Press, Oxford (1994) · Zbl 0841.43002
[11] Fukushima, M., Luo, Z.Q., Tseng, P.: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12, 436–460 (2001) · Zbl 0995.90094
[12] Huang, Z.H., Han, J., Chen, Z.: A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problems with a P 0 function. J. Optim. Theory Appl. 117, 39–68 (2003) · Zbl 1044.90081
[13] Liu, Y.J., Zhang, L.W., Wang, Y.H.: Analysis of a smoothing method for symmetric conic linear programming. J. Appl. Math. Comput. 22, 133–148 (2006) · Zbl 1132.90353
[14] Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998) · Zbl 0946.90050
[15] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977) · Zbl 0376.90081
[16] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090
[17] Qi, L., Sun, D.: Improving the convergence of non-interior point algorithm for nonlinear complementarity problems. Math. Comput. 69, 283–304 (2000) · Zbl 0947.90117
[18] Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87, 1–35 (2000) · Zbl 0989.90124
[19] Sun, D., Sun, J.: Strong semismoothness of Fischer-Burmeister SDC and SOC complementarity functions. Math. Program. 103, 575–581 (2005) · Zbl 1099.90062
[20] Toh, K.C., Tütüncü, R.H., Todd, M.J.: SDPT3 Version 3.02–a MATLAB software for semidefinite-quadratic-linear programming. http://www.math.nus.edu.sg/\(\sim\)mattohkc/sdpt3.html (2002)
[21] Tseng, P.: Analysis of a non-interior continuation method based on Chen-Mangasarian smoothing functions for complementarity problems. In: Fukushima, M., Qi, L. (eds.) Reformulation–Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, pp. 381–404. Kluwer Academic, Boston (1999) · Zbl 0928.65078
[22] Zhang, L.W., Liu, Y.J.: Convergence analysis of a nonlinear Lagrange algorithm for nonlinear programming with inequality constraints. J. Appl. Math. Comput. 13, 1–10 (2003) · Zbl 1044.90079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.