×

zbMATH — the first resource for mathematics

A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones. (English) Zbl 1175.90290
Summary: We introduce a one-parametric class of smoothing functions which contains the Fischer-Burmeister smoothing function and the CHKS smoothing function as special cases. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve linear programming over symmetric cones. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.

MSC:
90C05 Linear programming
90C22 Semidefinite programming
90C25 Convex programming
90C30 Nonlinear programming
Software:
SCCP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alizadeh F, Schmieta SH (2000) Symmetric cones, potential reduction methods and word-by-word extensions. In: Sail R, Vandenberghe L, Wolkowicz H (eds) Handbook of semidefinite programming, theory, algorithms and applications. Kluwer, Dordrecht, pp 195–233 · Zbl 0957.90530
[2] Chen B, Harker PT (1993) A non-interior-point continuation method for linear complementarity problem. SIAM J Matrix Anal Appl 14: 1168–1190 · Zbl 0788.65073
[3] Chen JS, Pan SH (2008a) A one-parametric class of merit functions for the second-order cone complementarity problem. Comput Optim Appl. doi: 10.1007/s10589-008-9182-9
[4] Chen JS, Pan SH (2008b) A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions. Comput Optim Appl. doi: 10.1007/s10589-008-9166-9
[5] Chen X, Sun D, Sun J (2003) Complementarity function and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems. Comput Optim Appl 25: 39–56 · Zbl 1038.90084
[6] Clarke FH (1983) Optimization and nonsmooth analysis. Wiley, New York · Zbl 0582.49001
[7] Faraut U, Korányi A (1994) Analysis on symmetric cones, Oxford Mathematical Monographs. Oxford University Press, New York · Zbl 0841.43002
[8] Faybusovich L (1997a) Euclidean Jordan algebras and interior-point algorithms. Positivity 1: 331–357 · Zbl 0973.90095
[9] Faybusovich L (1997b) Linear systems in Jordan algebras and pridual-dual interior-point algorithms. J Comput Appl Math 86: 149–175 · Zbl 0889.65066
[10] Faybusovich L, Lu Y (2006) Jordan-algebraic aspects of nonconvex optimization over semmetric cones. Appl Math Optim 53: 67–77 · Zbl 1094.90031
[11] Faybusovich L, Tsuchiya T (2003) Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank. Math Program 97: 471–493 · Zbl 1035.90099
[12] Fischer A (1992) A special Newton-type optimization method. Optimization 24: 269–284 · Zbl 0814.65063
[13] Gowda MS, Sznajder R, Tao J (2004) Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl 393: 203–232 · Zbl 1072.15002
[14] Huang ZH, Gu WZ (2008) A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties. Appl Math Optim 57: 17–29 · Zbl 1190.90236
[15] Huang ZH, Ni T (2008) Smoothing algorithms for complementarity problems over symmetric cones. Comput Optim Appl. doi: 10.1007/s10589-008-9180-y
[16] Huang ZH, Sun D, Zhao GY (2006) A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Comput Optim Appl 35: 199–237 · Zbl 1151.90509
[17] Huang ZH, Zhang Y, Wu W (2008) A smoothing-type algorithm for solving system of inequalities. J Comput Appl Math 220: 355–363 · Zbl 1148.65039
[18] Kanzow C, Kleinmichel H (1998) A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comput Optim Appl 11: 227–251 · Zbl 0913.90250
[19] Kanzow C (1996) Some noninterior continuation methods for linear complementarity problems. SIAM J Matrix Anal Appl 17: 851–868 · Zbl 0868.90123
[20] Kong LC, Sun J, Xiu NH (2006) A regularized smoothing Newton method for symmetric cone complementarity problems. SIAM J Optim (to appear)
[21] Korányi A (1984) Monotone functions on formally real Jordan algebras. Math Ann 269: 73–76 · Zbl 0552.17014
[22] Liu YJ, Zhang ZW, Wang YH (2006) Analysis of smoothing method for symmetric conic linear programming. J Appl Math Comput 22: 133–148 · Zbl 1132.90353
[23] Mifflin R (1977) Semismooth and semiconvex functions in constrained optimization. SIAM J Control Optim 15: 957–972 · Zbl 0376.90081
[24] Pan SH, Chen JS (2007) A one-parametric class of merit functions for the symmetric cone complementarity problem. Preprint, Department of Mathematics, National Taiwan Normal University
[25] Qi HD (2000) A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions. SIAM J Optim 10: 315–330 · Zbl 0955.90136
[26] Qi L (1993) Convergence analysis of some algorithms for solving nonsmooth equations. Math Oper Res 18: 227–253 · Zbl 0776.65037
[27] Qi L, Sun D, Zhou G (2000) A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math Program 87: 1–35 · Zbl 0989.90124
[28] Qi L, Sun J (1993) A nonsmooth version of Newton’s method. Math Program 58: 353–367 · Zbl 0780.90090
[29] Schimieta SH, Alizadeh F (2001) Associative and Jordan algebras, and polynomial time interior-point algirithms for symmetric cones. Math Oper Res 26: 543–564 · Zbl 1073.90572
[30] Schimieta SH, Alizadeh F (2003) Extension of primal-dual interior-point algorithms to symmetric cones. Math Program 96: 409–438 · Zbl 1023.90083
[31] Smale S (1987) Algorithms for solving equations. In: Gleason AM (eds) Proceeding of international congress of mathematians. American Mathematics Society, Providence, pp 172–195
[32] Sun D, Sun J (2002) Semismooth matrix value functions. Math Oper Res 27: 150–169 · Zbl 1082.49501
[33] Sun D, Sun J (2008) Löwner’s operator and spectral functions in Euclidean Jordan algebras. Math Oper Res 33: 421–445 · Zbl 1218.90197
[34] Yoshise A (2006) Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J Optim 17: 1129–1153 · Zbl 1136.90039
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.