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
SDPT3
Full Text:
References:
  Alizadeh, F.; Goldfarb, D., Second-order cone programming, Mathematical programming, 95, 3-51, (2003) · Zbl 1153.90522  Clarke, F.H., Optimization and nonsmooth analysis, (1983), John Wiley and Sons New York · Zbl 0727.90045  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  Faraut, J.; Korányi, A., Analysis on symmetric cones, (1994), Oxford University Press Oxford, UK · Zbl 0841.43002  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  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  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  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  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  Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM journal on control and optimization, 15, 957-972, (1977) · Zbl 0376.90081  Qi, L.; Sun, J., A nonsmooth version of newton’s method, Mathematical programming, 58, 353-367, (1993) · Zbl 0780.90090  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  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  Sun, D.; Sun, J., Strong semismoothness of fischer – burmeister SDC and SOC complementarity functions, Mathematical programming, 103, 575-581, (2005) · Zbl 1099.90062  Tseng, P., Error bounds and superlinear convergence analysis of some Newton-type methods in optimization, (), 445-462 · Zbl 0965.65091  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.