Smoothing Newton algorithm for linear programming over symmetric cones

Abstract

By using the theory of Euclidean Jordan algebras, based on a new class of smoothing functions, the Qi-Sun-Zhou’s smoothing Newton algorithm is extended to solve linear programming over symmetric cones (SCLP). The algorithm is globally convergent under suitable assumptions.

Keywords

linear programming / symmetric cone / Euclidean Jordan algebra / smoothing algorithm

References

[1] Alizadeh F., Schmieta S. H. Sail R., Vandenberghe L., Wolkowicz H. Symmetric cones, potential reduction methods and word-by-word extensions [M] Handbook of Semidefinite Programming, Theory, Algorithms and Applications, 2000, Kluwer: Kluwer Academic Publishers.

[2] Faybusovich L. Euclidean Jordan algebras and interior-point algorithms[J]. Positivity, 1997, 1(4): 331-357.

[3] Faybusovich L. Linear systems in Jordan algebras and primal-dual interior point algorithms[J]. J Comput Appl Math, 1997, 86(1): 149-175.

[4] Faybusovich L., Lu Y. Jordan-algebraic aspects of nonconvex optimization over symmetric cones[J]. Appl Math Optim, 2006, 53(1): 67-77.

[5] Faybusovich L., Tsuchiya T. Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank[J]. Math Program, 2003, 97(3): 471-493.

[6] Schimieta S. H., Alizadeh F. Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones[J]. Math Oper Res, 2001, 26(3): 543-564.

[7] Schimieta S. H., Alizadeh F. Extension of primal-dual interior-point algorithms to symmetric cones[J]. Math Program, 2003, 96(3): 409-438.

[8] Qi L., Sun D., Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems[J]. Math Program, 2000, 87(1): 1-35.

[9] Faraut J., Korányi A. Analysis on Symmetric Cones[M]. 1994, New York: Oxford University Press.

[10] Korányi A. Monotone functions on formally real Jordan algebras[J]. Math Ann, 1984, 269(1): 73-76.

[11] Gowda M. S., Sznajder R., Tao J. Some P-properties for linear transformations on Euclidean Jordan algebras[J]. Linear Algebra Appl, 2004, 393 203-232.

[12] Yoshise A. Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones[J]. SIAM J Optim, 2006, 17(4): 1129-1153.

[13] Fischer A. A special Newton-type optimization method[J]. Optim, 1992, 24 269-284.

[14] Kanzow C. Some noninterior continuation methods for linear complementarity problems[J]. SIAM J Matrix Anal Appl, 1996, 17(4): 851-868.

[15] Chen B., Harker P. T. A non-interior-point continuation method for linear complementarity problem[J]. SIAM J Matrix Anal Appl, 1993, 14(4): 1168-1190.

[16] Smale S. Algorithms for solving equations [C]. In: Gleason A M, Proceedings of International Congress of Mathematicians, American Mathematics Society. Providence, Rhode Island, 1987. 172–195.

[17] Qi H. D. A regularized smoothing Newton method for box constrained variational inequality problems with P ₀ — functions[J]. SIAM J Optim, 1999, 10(2): 315-330.

[18] Huang Z. H., Sun D., Zhao G. Y. A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming[J]. Comput Optim Appl, 2006, 35(2): 199-237.

[19] Huang Z. H., Sun J. A non-interior continuation algorithm for the P ₀ or P _* LCP with strong global and local convergence properties[J]. Appl Math Optim, 2005, 52(2): 237-262.