Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity
interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity
Summary:
A full Nesterov-Todd step infeasible interior-point algorithm is proposed for solving linear programming problems over symmetric cones by using the Euclidean Jordan algebra. Using a new approach, we also provide a search direction and show that the iteration bound coincides with the best known bound for infeasible interior-point methods.
References:
[1] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York 1994. MR 1446489 | Zbl 0841.43002
[2] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86 (1997), 149-175. DOI 10.1016/S0377-0427(97)00153-2 | MR 1491432 | Zbl 0889.65066
[3] Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239 (2002), 1, 117-129. DOI 10.1007/s002090100286 | MR 1879331 | Zbl 0996.65065
[4] Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. European J. Oper. Res. 214 (2011), 3, 473-484. DOI 10.1016/j.ejor.2011.02.022 | MR 2820168 | Zbl 1245.90144
[5] Güler, O.: Barrier functions in interior-point methods. Math. Oper. Res. 21 (1996), 4, 860-885. DOI 10.1287/moor.21.4.860 | MR 1419906 | Zbl 0867.90090
[6] Muramatsu, M.: On a commutative class of search directions for linear programming over symmetric cones. J. Optim. Theory Appl. 112 (2002), 3, 595-625. DOI 10.1023/A:1017920200889 | MR 1892239 | Zbl 0994.90095
[7] Nesterov, Y. E., Nemirovski, A.: Interior-point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia 1994. MR 1258086
[8] Nesterov, Y. E., Todd, M. J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22 (1997), 1, 1-42. DOI 10.1287/moor.22.1.1 | MR 1436572 | Zbl 0871.90064
[9] Rangarajan, B. K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16 (2006), 4, 1211-1229. DOI 10.1137/040606557 | MR 2219140 | Zbl 1131.90043
[10] Roos, C.: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136. DOI 10.1137/050623917 | MR 2219135 | Zbl 1131.90029
[11] Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization: An Interior-Point Approach. John Wiley and Sons, Chichester 1997, Second edition Springer 2006. MR 1450094 | Zbl 0954.65041
[12] Schmieta, S. H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96 (2003), 3, 409-438. DOI 10.1007/s10107-003-0380-z | MR 1993457
[13] Sturm, J. F.: Similarity and other spectral relations for symmetric cones. Algebra Appl. 312 (2000), 1 - 3, 135-154. DOI 10.1016/S0024-3795(00)00096-3 | MR 1759328 | Zbl 0973.90093
[14] Vieira, M. V. C.: Jordan Algebraic Approach to Symmetric Optimization. Ph.D. Thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology 2007.
Search
Partner of
