×

Extension of smoothing Newton algorithms to solve linear programming over symmetric cones. (English) Zbl 1242.90100

Summary: There recently has been much interest in studying some optimization problems over symmetric cones. This paper deals with linear programming over symmetric cones (SCLP). The objective here is to extend the Qi-Sun-Zhou’s smoothing Newton algorithm to solve SCLP, where characterization of symmetric cones using Jordan algebras forms the fundamental basis for our analysis. By using the theory of Euclidean Jordan algebras, the authors show that the algorithm is globally and locally quadratically convergent under suitable assumptions. The preliminary numerical results for solving the second-order cone programming are also reported.

MSC:

90C05 Linear programming

Software:

SDPT3; SCCP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 1995, 5: 13–51. · Zbl 0833.90087 · doi:10.1137/0805002
[2] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1997, 1: 331–357. · Zbl 0973.90095 · doi:10.1023/A:1009701824047
[3] L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 1997, 86: 149–175. · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2
[4] M. S. Gowda, R. Sznajder, and J. Tao, Some P-properties for linear transformations on Euclidean Jordan algebras, Linear Algebra Appl., 2004, 393: 203–232. · Zbl 1072.15002 · doi:10.1016/j.laa.2004.03.028
[5] Z. H. Huang and T. Ni, Smoothing algorithms for complementarity problems over symmetric cones, Comput. Optim. Appl., 2010, 45: 557–579. · Zbl 1198.90373 · doi:10.1007/s10589-008-9180-y
[6] L. C. Kong, J. Sun, and N. H. Xiu, A regularized smoothing Newton method for symmetric cone complementarity problems, SIAM J. Optim., 2008, 19: 1028–1047. · Zbl 1182.65092 · doi:10.1137/060676775
[7] D. Sun and J. Sun, Löwner’s operator and spectral functions in Euclidean Jordan algebras, Math. Oper. Res., 2008, 33: 421–445. · Zbl 1218.90197 · doi:10.1287/moor.1070.0300
[8] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones, Math. Program., 2003, 96: 409–438. · Zbl 1023.90083 · doi:10.1007/s10107-003-0380-z
[9] A. Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones, SIAM J. Optim., 2006, 17: 1129–1153. · Zbl 1136.90039 · doi:10.1137/04061427X
[10] L. Qi, D. Sun, and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems, Math. Program., 2000, 87: 1–35. · Zbl 0989.90124
[11] J. Faraut and A. Korányi, Analysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, New York, 1994. · Zbl 0841.43002
[12] Y. J. Liu, Z. W. Zhang, and Y. H. Wang, Analysis of smoothing method for symmetric conic linear programming, J. Appl. Math. Computing, 2006, 22: 133–148. · Zbl 1132.90353 · doi:10.1007/BF02896466
[13] Z. H. Huang, D. Sun, and G. Y. Zhao, A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming, Comput. Optim. Appl., 2006, 35: 199–237. · Zbl 1151.90509 · doi:10.1007/s10589-006-6512-7
[14] H. D. Qi, A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions, SIAM J. Optim., 2000, 10: 315–330. · Zbl 0955.90136 · doi:10.1137/S1052623497324047
[15] Z. H. Huang, Y. Zhang, and W. Wu, A smoothing-type algorithm for solving system of inequalities, J. Comput. Appl. Math., 2008, 220: 355–363. · Zbl 1148.65039 · doi:10.1016/j.cam.2007.08.024
[16] R. Mifflin, Semismooth and semiconvex functions in constraint optimization, SIAM J. Control Optim., 1997, 15: 957–972. · Zbl 0376.90081
[17] L. Qi and J. Sun, A nonsmooth version of Newton’s method, Math. Program., 1993, 58: 353–367. · Zbl 0780.90090 · doi:10.1007/BF01581275
[18] M. Kojima, M. Shida, and S. Shindoh, Local convergence of predictor-corrector infeasible interiorpoint algorithms for SDPs and SDLCPs, Math. Program. 1998, 80: 129–160. · Zbl 0897.90183
[19] F. Alizadeh, J. P. A. Haeberly, and M. L. Overton, Primal-dual interior point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM J. Optim., 1998, 8: 746–768. · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[20] Z. H. Huang and J. Han, Non-interior continuation method for solving the monotone semidefinite complementarity problem, Appl. Math. Optim., 2003, 47: 195–211. · Zbl 1030.65069 · doi:10.1007/s00245-003-0765-7
[21] X. Chen and P. Tseng, Non-interior continuous methods for solving semidefinite complementarity problems, Math. Program., 2003, 95: 431–474. · Zbl 1023.90046 · doi:10.1007/s10107-002-0306-1
[22] K. C. Toh, M. J. Todd, and R. H. Tütüncü, SDPT3 – A Matlab software package for semidefinite programming, Optim. Methods Softw., 1999, 11: 545–581. · Zbl 0997.90060 · doi:10.1080/10556789908805762
[23] Z. H. Huang and H. Wang, Smoothing-type algorithm for solving linear programs by using an augmented complementarity problem, Appl. Math. Comput., 2006, 177: 330–345. · Zbl 1101.65060 · doi:10.1016/j.amc.2005.11.012
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.