×

zbMATH — the first resource for mathematics

A new smoothing Newton-type method for second-order cone programming problems. (English) Zbl 1183.65065
The authors propose a novel smoothing Newton-type approach for solving a second-order cone optimization problem. The article begins with an introduction to second-order cone programming problems followed by an overview of useful notations and background theorems and properties of the cone. The third section proposes a new smoothing function for the second-order cone, and its links with the Fischer-Burmeister function. The fourth and fifth sections present and study the details of the main algorithm for solving the optimization problem and its convergence properties. The article concludes with a section containing the results of computational experimentation and a list of relevant references.

MSC:
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C51 Interior-point methods
Software:
SeDuMi; SDPT3
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Faraut, J.; Koranyi, A., Analysis on symmetric cones, (1994), Oxford University Press London, New York · Zbl 0841.43002
[2] Lobo, M.S.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear algebra and its applications, 284, 193-228, (1998) · Zbl 0946.90050
[3] Shivaswamy, P.K.; Bhattacharyya, C.; Smola, A.J., Second order cone programming approaches for handling missing and uncertain data, Journal of machine learning research, 7, 1283-1314, (2006) · Zbl 1222.68305
[4] Debnath, R.; Muramatsu, M.; Takahashi, H., An efficient support vector machine learning method with second-order cone programming for large-scale problems, Applied intelligence, 23, 219-239, (2005) · Zbl 1080.68618
[5] Schmieta, S.H.; Alizadeh, F., Extension of primal – dual interior point algorithms to symmetric cones, Mathematical programming, series A, 96, 409-438, (2003) · Zbl 1023.90083
[6] Yan, S.; Ma, Y., Robust supergain beamforming for circular array via second-order cone programming, Applied acoustics, 66, 1018-1032, (2005)
[7] Sasakawa, T.; Tsuchiya, T., Optimal magnetic shield design with second-order cone programming, SIAM journal of science and computation, 24, 6, 1930-1950, (2003) · Zbl 1163.90796
[8] Peng, X.; King, I., Robust BMPM training based on second-order cone programming and its application in medical diagnosis, Neural networks, 21, 450-457, (2008)
[9] Kanno, Y.; Ohsaki, M., Contact analysis of cable networks by using second-order cone programming, SIAM journal of science and computation, 27, 6, 2032-2052, (2006) · Zbl 1100.74045
[10] Kuo, Y.J.; Mittelmann, H.D., Interior point methods for second-order cone programming and OR applications, Computational optimization and applications, 28, 255-285, (2004) · Zbl 1084.90046
[11] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Mathematical programming, 95, 3-51, (2003) · Zbl 1153.90522
[12] Peng, J.; Roos, C.; Terlaky, T., Primal – dual interior-point methods for second-order conic optimization based on self-regular proximities, SIAM journal on optimization, 13, 1, 179-203, (2002) · Zbl 1041.90072
[13] Faybusovich, L., Euclidean Jordan algebras and interior-point algorithms, Positivity, 1, 331-357, (1997) · Zbl 0973.90095
[14] Nesterov, Y.E.; Todd, M.J., Primal – dual interior-point methods for self-scaled cones, SIAM journal on optimization, 8, 2, 324-364, (1998) · Zbl 0922.90110
[15] Sturm, J.F., Using sedumi 1.02 a MATLAB toolbox for optimization over symmetric cones, Optimization methods and software, 11-12, 625-653, (1999), Special issue on Interior Point Methods (CD supplement with software) · Zbl 0973.90526
[16] K.C. Toh, R.H. Tütüncü, M.J. Todd, SDPT3 Version 3.02 - A MATLAB software for semidefinite-quadratic-linear programming, 2002. <http://www.math.nus.edu.sg/ mattohkc/sdpt3.html>.
[17] 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 journal on optimization, 9, 605-623, (1999) · Zbl 1037.90052
[18] Ma, C.; Chen, X., The convergence of a one-step smoothing Newton method for \(P_0\)-NCP based on a new smoothing NCP-function, Journal of computational and applied mathematics, 216, 1-13, (2008) · Zbl 1140.65046
[19] Sun, D.; Sun, J., Strong semismoothness of the fischer – burmeister SDC and SOC complementarity functions, Mathematical programming, series A, 103, 575-581, (2005) · Zbl 1099.90062
[20] Qi, L.; Sun, D., Improving the convergence of non-interior point algorithm for nonlinear complementarity problems, Mathematics of computation, 69, 283-304, (2000) · Zbl 0947.90117
[21] Qi, L.; Sun, D.; Zhou, G., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Mathematical programming, 87, 1-35, (2000) · Zbl 0989.90124
[22] Fukushima, M.; Luo, Z.; Tseng, P., Smoothing functions for second-order-cone complimentarity problems, SIAM journal on optimization, 12, 2, 436-460, (2002)
[23] Miffin, R., Semismooth and semiconvex functions in constrained optimization, SIAM journal on control and optimization, 15, 957-972, (1977)
[24] Hayashi, S.; Yamashita, N.; Fukushima, M., A combined smoothing and regularized method for monotone second-order cone complementarity problems, SIAM journal on optimization, 15, 593-615, (2005) · Zbl 1114.90139
[25] Liu, Y.; Zhang, L.; Wang, Y., Analysis of a smoothing method for symmetric cone linear programming, Journal of applied mathematics and computing, 22, 1-2, 133-148, (2006) · Zbl 1132.90353
[26] Tseng, P., Error bounds and superlinear convergence analysis of some Newton-type methods in optimization, (), 445-462 · Zbl 0965.65091
[27] Chen, J., Two classes of merit functions for the second-order cone complementarity problem, Mathematical methods of operations research, 64, 495-519, (2006) · Zbl 1162.90572
[28] Chen, J.; Tseng, P., An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Mathematical programming, series B, 104, 293-327, (2005) · Zbl 1093.90063
[29] S. Pan, J. Chen, A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions, Computational Optimization and Applications. doi:10.1007/s10589-008-9166-9. · Zbl 1208.90170
[30] Rangarajan, B.K., Polynomial convergence of infeasible-interior-point methods over symmetric cones, SIAM journal on optimization, 16, 4, 1211-1229, (2006) · Zbl 1131.90043
[31] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Mathematical programming, 58, 353-367, (1993) · Zbl 0780.90090
[32] Clarke, F.H., Optimization and nonsmooth analysis, (1983), Wiley New York, Reprinted by SIAM, Philadelphia, 1990 · Zbl 0727.90045
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.