×

zbMATH — the first resource for mathematics

A one-step smoothing Newton method for second-order cone programming. (English) Zbl 1155.65045
The second-order cone programming problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of a finite number of second-order cones. In this paper, a new smoothing function is introduced by smoothing the symmetric perturbed Fischer-Burmeister function. This new function is basis for a one-step smoothing Newton method for solving the second-order cone programming problem.
The algorithm can start from an arbitrary point. Only one system of linear equations needs to be solved and only one line search is performed in each iteration. If an accumulation point of the iteration sequence satisfies a nonsingularity assumption then the iteration sequence converges to the accumulation point globally and locally Q-quadratically without strict complementarity. The efficiency of the algorithm is illustrated by some numerical experimental results on ten randomly generated test problems.

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C53 Methods of quasi-Newton type
Software:
SDPT3
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Mathematical programming, 95, 3-51, (2003) · Zbl 1153.90522
[2] Clarke, F.H., Optimization and nonsmooth analysis, (1983), John Wiley and Sons New York · Zbl 0727.90045
[3] 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
[4] Faraut, J.; Korányi, A., Analysis on symmetric cones, (1994), Oxford University Press Oxford, UK · Zbl 0841.43002
[5] Fukushima, M.; Luo, Z.Q.; Tseng, P., Smoothing functions for second-order-cone complementarity problems, SIAM journal on optimization, 12, 436-460, (2001) · Zbl 0995.90094
[6] 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, Journal of optimization theory and applications, 117, 39-68, (2003) · Zbl 1044.90081
[7] 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
[8] 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
[9] 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
[10] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM journal on control and optimization, 15, 957-972, (1977) · Zbl 0376.90081
[11] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Mathematical programming, 58, 353-367, (1993) · Zbl 0780.90090
[12] 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
[13] 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
[14] Sun, D.; Sun, J., Strong semismoothness of fischer – burmeister SDC and SOC complementarity functions, Mathematical programming, 103, 575-581, (2005) · Zbl 1099.90062
[15] Tseng, P., Error bounds and superlinear convergence analysis of some Newton-type methods in optimization, (), 445-462 · Zbl 0965.65091
[16] K.C. Toh, R.H. Tütüncü, M.J. Todd, SDPT3 Version 3.02-A MATLAB software for semidefinite-quadratic-linear programming. http://www.math.nus.edu.sg/ mattohkc/sdpt3.html, 2002
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.