×

zbMATH — the first resource for mathematics

On a commutative class of search directions for linear programming over symmetric cones. (English) Zbl 0994.90095
The author investigates the complexity of rather general path-following techniques for linear programming problems over symmetric cones. In particular, a commutative class of search directions is studied. As abstract tool the author uses the approach given in the book J. Faraut and A. Korányi [Analysis on symmetric cones. Clarendon Press, Oxford (1994; Zbl 0841.43002)]. A study of it is recommended to be easier able to follow the applied concept of Euclidean Jordan algebra and Pierce decomposition.

MSC:
90C05 Linear programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] MONTEIRO, R. D. C., and ZHANG, Y., A Unified Analysis for a Class of Path-Following Primal-Dual Interior-Point Algorithms for Semidefinite Programming, Mathematical Programming, Vol. 81, pp. 281–299, 1998. · Zbl 0919.90109
[2] NESTEROV, Y. E., and TODD, M. J., Primal-Dual Interior-Point Methods for Self-Scaled Cones, SIAM Journal on Optimization, Vol. 8, pp. 324–364, 1998. · Zbl 0922.90110
[3] FAYBUSOVICH, L., Jordan Algebras, Symmetric Cones, and Interior-Point Methods, Technical Report, Department of Mathematics, Notre Dame University, 1995.
[4] FAYBUSOVICH, L., Linear Systems in Jordan Algebras and Primal-Dual Interior-Point Algorithms, Journal of Computational and Applied Mathematics, Vol. 86, pp. 149–175, 1997. · Zbl 0889.65066
[5] STURM, J. F., Similarity and Other Spectral Relations for Symmetric Cones, Linear Algebra and Its Applications, Vol. 312, pp. 135–154, 2000. · Zbl 0973.90093
[6] SCHMIETA, S. H., and ALIZADEH, F., Associatiue Algebras, Symmetric Cones, and Polynomial-Time Interior-Point Algorithms, RUTCOR Research Report, Rutgers University, 1998. · Zbl 1073.90572
[7] MONTEIRO, R. D. C., Primal-Dual Path-Following Algorithms for Semidefinite Programming, SIAM Journal on Optimization, Vol. 7, pp. 663–678, 1997. · Zbl 0913.65051
[8] ZHANG, Y., On Extending Some Primal-Dual Interior-Point Algorithms from Linear Programming to Semidefinite Programming, SIAM Journal on Optimization, Vol. 8, pp. 365–386, 1998. · Zbl 0913.65050
[9] GU, M., On Primal-Dual Interior-Point Methods for Semidefinite Programming, CAM Report 97–12, Department of Mathematics, University of California at Los Angeles, 1997.
[10] MONTEIRO, R. D. C., and TSUCHIYA, T., Polynomial Conuergence of Primal-Dual Algorithms for the Second-Order Cone Program Based on the MZ-Family of Directions, Mathematical Programming, Vol. 88, pp. 61–83, 2000. · Zbl 0967.65077
[11] TSUCHIYA, T., A Polynomial Primal-Dual Path-Following Algorithm for Second-Order Cone Programming, Research Memorandum 649, Institute of Statistical Mathematics, Tokyo, Japan, 1997.
[12] TSUCHIYA, T., A Conuergence Analysis of the Scaling-Inuariant Primal-Dual Path-Following Algorithms for Second-Order Cone Programming, Optimization Methods and Software, Vols. 11–12, pp. 141–182, 1999. · Zbl 0957.90129
[13] HELMBERG, C., RENDL, F., VANDERBEI, R. J., and WOLKOWICZ, H., An Interior-Point Method for Semidefinite Programming, SIAM Journal on Optimization, Vol. 6, pp. 342–361, 1996. · Zbl 0853.65066
[14] KOJIMA, M., SHINDOH, S., and HARA, S., Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices, SIAM Journal on Optimization, Vol. 7, pp. 86–125, 1997. · Zbl 0872.90098
[15] FARAUT, J., and KOR’ANYI, A., Analysis on Symmetric Cones, Oxford University Press, New York, NY, 1994. · Zbl 0841.43002
[16] ALIZADEH, F., HAEBERLY, J. P. A., and OVERTON, M. L., Primal-Dual Interior-Point Methods for Semidefinite Programming, Technical Report 659, Computer Science Department, Courant Institute of Mathematical Sciences, New York University, 1994. · Zbl 0819.65098
[17] FAYBUSOVICH, L., and ARANA, R., A Long-Step Primal-Dual Algorithm for the Symmetric Programming Problem, Technical Report, Department of Mathematics, Notre Dame University, 2000. · Zbl 0970.90117
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.