×

Smoothing algorithms for complementarity problems over symmetric cones. (English) Zbl 1198.90373

The authors study a smoothing function in the context of symmetric cones and show that this function is coercive under some suitable conditions. Another objective of this paper is to extend two generic frameworks of smoothing algorithms to solve the complementarity problems over symmetric cones and to show the global convergence of the algorithms under suitable assumptions. The authors also provide a specific smoothing Newton algorithm which is globally and locally quadratically convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in the analysis. Some numerical results of a smoothing Newton algorithm for solving second-order cone complementarity problems are also reported.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F., Schmieta, S.H.: 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, pp. 195–233. Kluwer Academic, Dordrecht (2000) · Zbl 0957.90530
[2] Burke, J., Xu, S.: A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Math. Program. 87, 113–130 (2000) · Zbl 1081.90603
[3] Chen, X., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998) · Zbl 0894.90143 · doi:10.1090/S0025-5718-98-00932-6
[4] Chen, B., Harker, P.T.: A non-interior-point continuation method for linear complementarity problem. SIAM J. Matrix Anal. Appl. 14, 1168–1190 (1993) · Zbl 0788.65073 · doi:10.1137/0614081
[5] Chen, J.-S.: The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem. J. Glob. Optim. 36, 565–580 (2006) · Zbl 1144.90493 · doi:10.1007/s10898-006-9027-y
[6] Chen, J.-S., Tseng, P.: An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. Math. Program. 104, 293–327 (2005) · Zbl 1093.90063 · doi:10.1007/s10107-005-0617-0
[7] Chen, X., Ye, Y.: On homotopy-smoothing methods for variational inequalities. SIAM J. Control Optim. 37, 589–616 (1999) · Zbl 0973.65051 · doi:10.1137/S0363012997315907
[8] Chen, X., Tseng, P.: Non-interior continuous methods for solving semidefinite complementarity problems. Math. Program. 95, 431–474 (2003) · Zbl 1023.90046 · doi:10.1007/s10107-002-0306-1
[9] Chen, X., Sun, D., Sun, J.: Complementarity function and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems. Comput. Optim. Appl. 25, 39–56 (2003) · Zbl 1038.90084 · doi:10.1023/A:1022996819381
[10] Engelke, S., Kanzow, C.: Improved non-interior continuation methods for the solution of linear programming. Numer. Math. 90, 487–507 (2002) · Zbl 0994.65065 · doi:10.1007/s002110100301
[11] Facchinei, F., Kanzow, C.: Beyond monotonicity in regularization methods for nonlinear complementarity problems. SIAM J. Control Optim. 37, 1150–1161 (1999) · Zbl 0997.90085 · doi:10.1137/S0363012997322935
[12] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997) · Zbl 0873.90096 · doi:10.1137/S1052623494279110
[13] Faraut, U., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs. Oxford University Press, Oxford (1994) · Zbl 0841.43002
[14] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149–175 (1987) · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2
[15] Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1, 331–357 (1997) · Zbl 0973.90095 · doi:10.1023/A:1009701824047
[16] Faybusovich, L., Lu, Y.: Jordan-algebraic aspects of nonconvex optimization over symmetric cones. Appl. Math. Optim. 53, 67–77 (2006) · Zbl 1094.90031 · doi:10.1007/s00245-005-0835-0
[17] Faybusovich, L., Tsuchiya, T.: Primal-dual algorithms and inifite-dimensional Jordan algebras of finite rank. Math. Program. 97, 471–493 (2003) · Zbl 1035.90099 · doi:10.1007/s10107-003-0424-4
[18] Gowda, M.S., Sznajder, R.: Some global uniqueness and solvability results for linear complementarity problems over symmetric cones. SIAM J. Optim. 18, 461–481 (2006) · Zbl 1153.90019 · doi:10.1137/06065943X
[19] Gowda, M.S., Sznajder, R.: Automorphism invariance of P and GUS properties of linear transformations in Euclidean Jordan algebras. Math. Oper. Res. 31, 109–123 (2006) · Zbl 1168.90620 · doi:10.1287/moor.1050.0182
[20] Gowda, M.S., Sznajder, R., Tao, J.: Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 393, 203–232 (2004) · Zbl 1072.15002 · doi:10.1016/j.laa.2004.03.028
[21] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005) · Zbl 1114.90139 · doi:10.1137/S1052623403421516
[22] Huang, Z.H., Han, J., Chen, Z.: A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P 0 function. J. Optim. Theory Appl. 117, 39–68 (2003) · Zbl 1044.90081 · doi:10.1023/A:1023648305969
[23] Huang, Z.H., Liu, X.H.: Extension of smoothing Newton algorithms to solve linear programming over symmetric cones. Technique Report, Department of Mathematics, School of Science, Tianjin University, China (2007)
[24] Huang, Z.H., Sun, D., Zhao, G.Y.: A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Comput. Optim. Appl. 35, 199–237 (2006) · Zbl 1151.90509 · doi:10.1007/s10589-006-6512-7
[25] Huang, Z.H., Sun, J.: A non-interior continuation algorithm for the P 0 or P * LCP with strong global local convergence properties. Appl. Math. Optim. 26, 237–262 (2005) · Zbl 1112.90083 · doi:10.1007/s00245-005-0827-0
[26] Huang, Z.H., Xu, S.W.: Convergence properties of a non-interior-point smoothing algorithm for the P * NCP. J. Ind. Manage. Optim. 3, 569–584 (2007) · Zbl 1166.90370
[27] Kanzow, C.: Some noninterior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17, 851–868 (1996) · Zbl 0868.90123 · doi:10.1137/S0895479894273134
[28] Kanzow, C., Nagel, C.: Semidefinite programs: new search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13, 1–23 (2003) · Zbl 1029.90052 · doi:10.1137/S1052623401390525
[29] Kong, L.C., Xiu, N.H.: New smooth C-functions for symmetric cone complementarity problems. Opt. Lett. 1, 391–400 (2007) · Zbl 1220.90133 · doi:10.1007/s11590-006-0037-y
[30] Korányi, A.: Monotone functions on formally real Jordan algebras. Math. Ann. 269, 73–76 (1984) · Zbl 0552.17014 · doi:10.1007/BF01455996
[31] Lin, Y., Yoshise, A.: A homogeneous model for mixed complementarity problems over symmetric cones. Technique Report, Graduate School of Systems and Information Engineering, University of Tsukuba, Japan (2005) · Zbl 1213.90192
[32] Palais, R.S., Terng, C.-L.: Critical Point Theory and Submanifold Geometry. Lecture Notes in Mathematics, vol. 1353. Springer, Berlin (1988) · Zbl 0658.49001
[33] Qi, H.D.: A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions. SIAM J. Optim. 10, 315–330 (2000) · Zbl 0955.90136 · doi:10.1137/S1052623497324047
[34] Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87, 1–35 (2000) · Zbl 0989.90124
[35] Schmieta, S.H., Alizadeh, F.: Associative and Jordan algebras, and polynonial time interior-point algorithms for symmetrc cones. Math. Oper. Res. 26, 543–564 (2001) · Zbl 1073.90572 · doi:10.1287/moor.26.3.543.10582
[36] Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. 96, 409–438 (2003) · Zbl 1023.90083 · doi:10.1007/s10107-003-0380-z
[37] Smale, S.: Algorithms for solving equations. In: Gleason, A.M. (ed.) Proceeding of International Congress of Mathematicians, pp. 172–195. American Mathematics Society, Providence (1987) · Zbl 0665.65058
[38] Sun, D., Sun, J.: Semismooth matrix valued functions. Math. Oper. Res. 27, 150–169 (2002) · Zbl 1082.49501 · doi:10.1287/moor.27.1.150.342
[39] Sun, D., Sun, J.: Löwner’s operator and spectral functions in Euclidean Jordan algebras. Math. Oper. Res. 33 (2008, in press) · Zbl 1218.90197
[40] Sun, J., Sun, D., Qi, L.: A square smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems. SIAM J. Optim. 14, 783–806 (2004) · Zbl 1079.90094 · doi:10.1137/S1052623400379620
[41] Tseng, P.: Merit functions for semidefinite complementarity problems. Math. Program. 83, 159–185 (1998) · Zbl 0920.90135
[42] Yoshise, A.: Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J. Optim. 17, 1129–1153 (2006) · Zbl 1136.90039 · doi:10.1137/04061427X
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.