×

zbMATH — the first resource for mathematics

Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. (English) Zbl 1245.90144
Summary: Euclidean Jordan algebras were proved more than a decade ago to be an indispensable tool in the unified study of interior-point methods. By using it, we generalize the full-Newton step infeasible interior-point method for linear optimization of Roos [C. Roos, A full-Newton step \(O(n)\) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16, No. 4, 1110–1136 (2006; Zbl 1131.90029)] to symmetric optimization. This unifies the analysis for linear, second-order cone and semidefinite optimizations.

MSC:
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ben-Tal, A., Nemirovski, A., 2001. Lectures on modern convex optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, Analysis, Algorithms, and Engineering Applications. · Zbl 0986.90032
[2] de Klerk, E., Aspects of semidefinite programming, Applied optimization, Interior point algorithms and selected applications, vol. 65, (2002), Kluwer Academic Publishers Dordrecht · Zbl 0991.90098
[3] Faraut, J.; Korányi, A., Analysis on symmetric cones, Oxford mathematical monographs, (1994), Oxford Science Publications/The Clarendon Press Oxford University Press New York
[4] Faybusovich, L., Euclidean Jordan algebras and interior-point algorithms, Positivity, 1, 4, 331-357, (1997) · Zbl 0973.90095
[5] Faybusovich, L., Linear systems in Jordan algebras and primal-dual interior-point algorithms, Journal of computational and applied mathematics, 86, 1, 149-175, (1997), special issue dedicated to William B. Gragg (Monterey, CA, 1996) · Zbl 0889.65066
[6] Faybusovich, L., A Jordan-algebraic approach to potential-reduction algorithms, Mathematische zeitschrift, 239, 1, 117-129, (2002) · Zbl 0996.65065
[7] Güler, O., Barrier functions in interior point methods, Mathematics of operations research, 21, 4, 860-885, (1996) · Zbl 0867.90090
[8] Kojima, M.; Megiddo, N.; Mizuno, S., A primal-dual infeasible-interior-point algorithm for linear programming, Mathematical programming, 61, 3, Ser. A, 263-280, (1993) · Zbl 0808.90093
[9] Lustig, I.J., Feasibility issues in a primal-dual interior-point method for linear programming, Mathematical programming, 49, 2, Ser. A, 145-162, (1990/91) · Zbl 0726.90050
[10] Mizuno, S., Polynomiality of infeasible-interior-point algorithms for linear programming, Mathematical programming, 67, 1, Ser. A, 109-119, (1994) · Zbl 0828.90086
[11] Nesterov, Y.; Nemirovskii, A., Interior-point polynomial algorithms in convex programming, SIAM studies in applied mathematics. society for industrial and applied mathematics, vol. 13, (1994), SIAM Philadelphia, PA · Zbl 0824.90112
[12] Nesterov, Y.E.; Todd, M.J., Self-scaled barriers and interior-point methods for convex programming, Mathematics of operations research, 22, 1, 1-42, (1997) · Zbl 0871.90064
[13] Nesterov, Y.E.; Todd, M.J., Primal-dual interior-point methods for self-scaled cones, SIAM journal on optimization, 8, 2, 324-364, (1998), electronic · Zbl 0922.90110
[14] Potra, F.A., An infeasible-interior-point predictor – corrector algorithm for linear programming, SIAM journal on optimization, 6, 1, 19-32, (1996) · Zbl 0846.90071
[15] Rangarajan, B.K., Polynomial convergence of infeasible-interior-point methods over symmetric cones, SIAM journal on optimization, 16, 4, 1211-1229, (2006), electronic · Zbl 1131.90043
[16] Roos, C., A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM journal on optimization, 16, 4, 1110-1136, (2006) · Zbl 1131.90029
[17] Roos, C.; Terlaky, T.; Vial, J.-P., Interior point methods for linear optimization, Theory and algorithms for linear optimization, (2006), Springer New York, [Wiley, Chichester, 1997; MR1450094]
[18] Schmieta, S.H.; Alizadeh, F., Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones, Mathematics of operations research, 26, 3, 543-564, (2001) · Zbl 1073.90572
[19] Schmieta, S.H.; Alizadeh, F., Extension of primal-dual interior point algorithms to symmetric cones, Mathematical programming, 96, 3, Ser. A, 409-438, (2003) · Zbl 1023.90083
[20] Sturm, J.F., Similarity and other spectral relations for symmetric cones, Linear algebra and its applications, 312, 1-3, 135-154, (2000) · Zbl 0973.90093
[21] Vieira, M.V.C., 2007. Jordan algebraic approach to symmetric optimization. Ph.D. thesis, Delft University of Technology.
[22] Zhang, Y., On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM journal on optimization, 4, 1, 208-227, (1994) · Zbl 0803.90092
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.