| Title:
|
New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization (English) |
| Author:
|
Kheirfam, Behrouz |
| Author:
|
Mahdavi-Amiri, Nezam |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
49 |
| Issue:
|
6 |
| Year:
|
2013 |
| Pages:
|
883-896 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
interior-point methods |
| Keyword:
|
symmetric cone optimization |
| Keyword:
|
Euclidean Jordan algebra |
| Keyword:
|
polynomial complexity |
| MSC:
|
17C50 |
| MSC:
|
90C25 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 06285133 |
| idMR:
|
MR3182646 |
| . |
| Date available:
|
2014-01-27T12:27:02Z |
| Last updated:
|
2015-03-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143577 |
| . |
| Reference:
|
[1] Faraut, J., Korányi, A.: Analysis on Symmetric Cones..Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York 1994. Zbl 0841.43002, MR 1446489 |
| Reference:
|
[2] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms..J. Comput. Appl. Math. 86 (1997), 149-175. Zbl 0889.65066, MR 1491432, 10.1016/S0377-0427(97)00153-2 |
| Reference:
|
[3] Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms..Math. Z. 239 (2002), 1, 117-129. Zbl 0996.65065, MR 1879331, 10.1007/s002090100286 |
| Reference:
|
[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. Zbl 1245.90144, MR 2820168, 10.1016/j.ejor.2011.02.022 |
| Reference:
|
[5] Güler, O.: Barrier functions in interior-point methods..Math. Oper. Res. 21 (1996), 4, 860-885. Zbl 0867.90090, MR 1419906, 10.1287/moor.21.4.860 |
| Reference:
|
[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. Zbl 0994.90095, MR 1892239, 10.1023/A:1017920200889 |
| Reference:
|
[7] Nesterov, Y. E., Nemirovski, A.: Interior-point Polynomial Algorithms in Convex Programming..SIAM, Philadelphia 1994. MR 1258086 |
| Reference:
|
[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. Zbl 0871.90064, MR 1436572, 10.1287/moor.22.1.1 |
| Reference:
|
[9] Rangarajan, B. K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones..SIAM J. Optim. 16 (2006), 4, 1211-1229. Zbl 1131.90043, MR 2219140, 10.1137/040606557 |
| Reference:
|
[10] Roos, C.: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization..SIAM J. Optim. 16 (2006), 4, 1110-1136. Zbl 1131.90029, MR 2219135, 10.1137/050623917 |
| Reference:
|
[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. Zbl 0954.65041, MR 1450094 |
| Reference:
|
[12] Schmieta, S. H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones..Math. Program. 96 (2003), 3, 409-438. MR 1993457, 10.1007/s10107-003-0380-z |
| Reference:
|
[13] Sturm, J. F.: Similarity and other spectral relations for symmetric cones..Algebra Appl. 312 (2000), 1 - 3, 135-154. Zbl 0973.90093, MR 1759328, 10.1016/S0024-3795(00)00096-3 |
| Reference:
|
[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. |
| . |
