A smoothing-type Newton method for second-order cone programming problems based on a new smooth function
Tóm tắt
A new smoothing function similar with the well known Fischer-Burmeister function is given. Based on this new function, a smoothing-type Newton method is proposed for solving second-order cone programming. At each iteration, the proposed algorithm solves only one system of linear equations and performs only one line search. This algorithm can start from an arbitrary point and it is Q-quadratically convergent under a mild assumption. Preliminary numerical results demonstrate the effectiveness of the method.
Tài liệu tham khảo
Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003)
Chen, J.: Two classes of merit functions for the second-order cone complementarity problem. Math. Methods Oper. Res. 64, 495–519 (2006)
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)
Debnath, R., Muramatsu, M., Takahashi, H.: An efficient support vector machine learning method with second-order cone programming for large-scale problems. Appl. Intell. 23, 219–239 (2005)
Faraut, J., Koranyi, A.: Analysis on Symmetric Cones. Oxford University Press, London/New York (1994) (ISBN: 0-198-53477-9)
Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1, 331–357 (1997)
Fukushima, M., Luo, Z., Tseng, P.: Smoothing functions for second-order-cone complimentarity problems. SIAM J. Optim. 12(2), 436–460 (2002)
Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularized method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005)
Kanno, Y., Ohsaki, M.: Contact analysis of cable networks by using second-order cone programming. SIAM J. Sci. Comput. 27(6), 2032–2052 (2006)
Kanzow, C., Kleinmichel, H.: A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comput. Optim. Appl. 11, 227–251 (1998)
Kuo, Y.J., Mittelmann, H.D.: Interior point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28, 255–285 (2004)
Liu, Y., Zhang, L., Wang, Y.: Analysis of a smoothing method for symmetric cone linear programming. J. Appl. Math. Comput. 22(1–2), 133–148 (2006)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)
Ma, C., Chen, X.: The convergence of a one-step smoothing Newton method for P 0-NCP based on a new smoothing NCP-function. J. Comput. Appl. Math. 216, 1–13 (2008)
Miffin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977)
Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8(2), 324–364 (1998)
Peng, X., King, I.: Robust BMPM training based on second-order cone programming and its application in medical diagnosis. Neural Netw. 21, 450–457 (2008)
Peng, J., Roos, C., Terlaky, T.: Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities. SIAM J. Optim. 13(1), 179–203 (2002)
Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)
Qi, L., Sun, D.: Improving the convergence of non-interior point algorithm for nonlinear complementarity problems. Math. Comput. 69, 283–304 (2000)
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)
Rangarajan, B.K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16(4), 1211–1229 (2006)
Sasakawa, T., Tsuchiya, T.: Optimal magnetic shield design with second-order cone programming. SIAM J. Sci. Comput. 24(6), 1930–1950 (2003)
Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior point algorithms to symmetric cones. Math. Program. Ser. A 96, 409–438 (2003)
Shivaswamy, P.K., Bhattacharyya, C., Smola, A.J.: Second order cone programming approaches for handling missing and uncertain data. J. Mach. Learn. Res. 7, 1283–1314 (2006)
Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11–12, 625–653 (1999). Special Issue on Interior Point Methods (CD supplement with software)
Sun, D., Sun, J.: Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions. Math. Program. Ser. A 103, 575–581 (2005)
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/~mattohkc/sdpt3.html (2002)
Tseng, P.: Error bounds and superlinear convergence analysis of some Newton-type methods in optimization. In: Di Pillo, G., Giannessi, F. (eds.) Nonlinear Optimization and Related Topics, pp. 445–462. Kluwer Academic, Boston (2000)
Yan, S., Ma, Y.: Robust supergain beamforming for circular array via second-order cone programming. Appl. Acoust. 66, 1018–1032 (2005)