×

zbMATH — the first resource for mathematics

An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path. (English) Zbl 06737238
Summary: In this paper, we propose a new arc-search infeasible-interior-point method for symmetric optimization using a wide neighborhood of the central path. The proposed algorithm searches for optimizers along the ellipses that approximate the central path. The convergence is shown for a commutative class of search directions, which includes the Nesterov-Todd direction and the \(xs\) and \(sx\) directions. The complexity bound is \(\mathcal {O}(r^{5/4}\log \varepsilon ^{-1})\) for the Nesterov-Todd direction, and \(\mathcal {O}(r^{7/4}\log \varepsilon ^{-1})\) for the \(xs\) and \(sx\) directions, where \(r\) is the rank of the associated Euclidean Jordan algebra and \(\varepsilon \) is the required precision. The obtained complexity bounds coincide with the currently best known theoretical complexity bounds for the short step path-following algorithm. Some limited encouraging computational results are reported.

MSC:
90C Mathematical programming
Software:
Netlib; SDPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Borchers, B, Sdplib 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11, 683-690, (1999) · Zbl 0973.90522
[2] Browne, S., Dongarra, J., Grosse, E., Rowan, T.: The Netlib Mathematical Software Repository. Corporation for National Research Initiatives, Reston (1995) · Zbl 1229.90084
[3] Faraut, J., Korányi, A.: Analysis on Symmetric Cone. Oxford University Press, New York (1994) · Zbl 0841.43002
[4] Faybusovich, L, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86, 149-175, (1997) · Zbl 0889.65066
[5] Güler, O, Barrier functions in interior-point methods, Math. Oper. Res., 21, 860-885, (1996) · Zbl 0867.90090
[6] Jansen, B; Roos, C; Terlaky, T; Ye, Y, Improved complexity using higher-order correctors for primal-dual dikin affine scaling, Math. Program., 76, 17-130, (1996) · Zbl 0884.90112
[7] Lahmam, H., Cadou, J.M., Zahrouni, H., Damil, N., Potier-Ferry, M.: High-order predictor-corrector algorithms. Int. J. Numer. Methods Eng. 55, 685-704 (2002). http://onlinelibrary.wiley.com/doi/10.1002/nme.524/abstract · Zbl 1058.76572
[8] Liu, C.: Study on complexity of some interior-point algorithms in conic programming (in Chinese). Ph.D. thesis, Xidian University (2012) · Zbl 0884.90112
[9] Liu, C; Liu, H; Liu, X, Polynomial convergence of second-order mehrotra-type predictor-corrector algorithms over symmetric cones, J. Optim. Theory Appl., 154, 949-965, (2012) · Zbl 1268.90128
[10] Liu, H; Yang, X; Liu, C, A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming, J. Optim. Theory Appl., 158, 949-965, (2013) · Zbl 1274.90389
[11] Nesterov, Y; Todd, M, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22, 1-42, (1997) · Zbl 0871.90064
[12] Nesterov, Y; Todd, M, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8, 324-364, (1998) · Zbl 0922.90110
[13] Rangarajan, BK, Polynomial convergence of infeasible-interior-point methods over symmetric cones, SIAM J. Optim., 16, 1211-1229, (2006) · Zbl 1131.90043
[14] Salahi, M; Mahdavi-Amiri, N, Polynomial time second order mehrotra-type predictor-corrector algorithms, Appl. Math. Comput., 183, 646-658, (2006) · Zbl 1112.65057
[15] Schmieta, SH; Alizadeh, F, Extension of primal-dual interior point algorithm to symmetric cones, Math. Program., 96, 409-438, (2003) · Zbl 1023.90083
[16] Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM Publications, Philsdephia (1997) · Zbl 0863.65031
[17] Yang, Y.: Arc-search path-following interior-point algorithms for linear programming. Optimization Oline (2009). http://www.optimization-online.org/ARCHIVE_CAT/LINSDP/2009.html · Zbl 0867.90090
[18] Yang, Y, A polynomial arc-search interior-point algorithm for convex quadratic programming, Eur. J. Oper. Res., 215, 25-38, (2011) · Zbl 1252.90059
[19] Yang, Y, A polynomial arc-search interior-point algorithm for linear programming, J. Optim. Theory Appl., 158, 859-873, (2013) · Zbl 1274.90494
[20] Zhang, Y; Zhang, D, On polynomiality of the mehrotra-type predictor-corrector interior-point algorithms, Math. Program., 68, 303-318, (1995) · Zbl 0837.90087
[21] Zhang, J; Zhang, K, Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming, Math. Meth. Oper. Res., 73, 75-90, (2011) · Zbl 1229.90084
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.