×

zbMATH — the first resource for mathematics

An adaptive infeasible-interior-point method with the one-norm wide neighborhood for semi-definite programming. (English) Zbl 1415.65141
Summary: In this paper, we present a Mehrotra-type predictor-corrector infeasible-interior-point method, based on the one-norm wide neighborhood, for semi-definite programming. The proposed algorithm uses Mehrotra’s adaptive updating scheme for the centering parameter, which incorporates a safeguard strategy that keeps the iterates in a prescribed neighborhood and allows to get a reasonably large step size. Moreover, by using an important inequality that is the relationship between the one-norm and the Frobenius-norm, the convergence is shown for a commutative class of search directions. In particular, the complexity bound is \(\mathcal {O}(n\log \varepsilon ^{-1})\) for Nesterov-Todd direction, and \(\mathcal {O}(n^{3/2}\log \varepsilon ^{-1})\) for Helmberg-Kojima-Monteiro directions, where \(\varepsilon \) is the required precision. The derived complexity bounds coincide with the currently best known theoretical complexity bounds obtained so far for the infeasible semi-definite programming. Some preliminary numerical results are provided as well.
MSC:
65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
90C51 Interior-point methods
Software:
SDPLIB; SeDuMi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alizadeh, F.: Combinatorial optimization with interior-point methods and semi-definite matrices Ph.D. thesis, Computer Sience Department, University of Minnesota, Minneapolis, USA (1991)
[2] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5, 13-51, (1995) · Zbl 0833.90087
[3] Borchers, B., Sdplib 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11, 683-690, (1999) · Zbl 0973.90522
[4] Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory. SIAM, Philadelphia (1994) · Zbl 0816.93004
[5] De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 0991.90098
[6] Helmberg, C.; Rendl, F.; Vanderbei, RJ; Wolkowicz, H., An interior-point method for semidefinite programming, SIAM J. Optim., 6, 342-361, (1996) · Zbl 0853.65066
[7] Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, New York (1991) · Zbl 0729.15001
[8] Ji, J.; Potra, FA; Sheng, R., On the local convergence of a predictor-corrector method for semi-definite programming, SIAM J. Optim., 10, 195-210, (1999) · Zbl 0959.65076
[9] Kojima, M.; Shindoh, S.; Hara, S., Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7, 86-125, (1997) · Zbl 0872.90098
[10] Kojima, M.; Shida, MA; Shindoh, S., Local convergence of predictor-corrector infeasible-interior-point algorithm for SDPs and SDLCPs, Math. Program., 80, 129-160, (1998) · Zbl 0897.90183
[11] Koulaei, MH; Terlaky, T., On the complexity analysis of a Mehrotra-type primal–dual feasible algorithm for semidefinite optimization, Optim. Methods Softw., 25, 467-485, (2010) · Zbl 1220.90082
[12] Li, Y.; Terlaky, T., A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with \(O(\sqrt{n}\log {(\text{Tr}(X^0S^0)/{\varepsilon })})\) iteration complexity, SIAM J. Optim., 20, 2853-2875, (2010) · Zbl 1228.90072
[13] Liu, H.; Liu, C.; Yang, X., New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming, Optim. Methods Softw., 28, 1179-1194, (2013) · Zbl 1310.65065
[14] Luo, ZQ; Sturm, JF; Zhang, S., Conic convex programming and self-dual embedding, Optim. Methods Softw., 14, 169-218, (2000) · Zbl 1072.90559
[15] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[16] Monteiro, RDC, Primal-dual path-following algorithms for semidefenite programming, SIAM J. Optim., 7, 663-678, (1997) · Zbl 0913.65051
[17] Monteiro, RDC, Polynomial convergence of primal–dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions, SIAM J. Optim., 8, 797-812, (1998) · Zbl 0913.65052
[18] Monteiro, RDC; Zhang, Y., A unified analysis for a class of long-step primal–dual path-following interior-point algorithms for semidefinite programming, Math. Program., 81, 281-299, (1998) · Zbl 0919.90109
[19] Nesterov, Y.E., Nemirovsky, A.S.: Interior-Point Methods in Convex Programming: Theory and Applications. SIAM, Philsdephia (1994)
[20] Nesterov, Y.; Todd, M., Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22, 1-42, (1997) · Zbl 0871.90064
[21] Nesterov, Y.; Todd, M., Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8, 324-364, (1998) · Zbl 0922.90110
[22] Peng, J., Roos, C., Terlaky, T.: Self-Regularity: An New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton (2002) · Zbl 1136.90045
[23] Peng, J.; Roos, C.; Terlaky, T., Self-regular functions and new search directions for linear and semidefinite optimization, Math. Program. Ser. A, 93, 129-171, (2002) · Zbl 1007.90037
[24] Potra, FA; Sheng, R., A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming, SIAM J. Optim., 8, 1007-1028, (1998) · Zbl 0917.65058
[25] Potra, FA; Sheng, R., On homogeneous interior-point algorithms for semi-definite programming, Optim. Methods Softw., 9, 161-184, (1998) · Zbl 0904.90118
[26] Potra, FA; Sheng, R., Superlinear convergence of interior-point algorithms for semidefinite programming, J. Optim. Theory Appl., 99, 103-119, (1998) · Zbl 0911.90255
[27] Rangarajan, BK, Polynomial convergence of infeasible-interior-point methods over symmetric cones, SIAM J. Optim., 16, 1211-1229, (2006) · Zbl 1131.90043
[28] Salahi, M.; Mahdavi-Amiri, N., Polynomial time second order Mehrotra-type predictor-corrector algorithms, Appl. Math. Comput., 183, 646-658, (2006) · Zbl 1112.65057
[29] Salahi, M.; Peng, J.; Terlaky, T., On Mehrotra-type predictor-corrector algorithms, SIAM J. Optim., 18, 1377-1397, (2007) · Zbl 1165.90569
[30] Sturm, JF, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Method Soft., 11, 625-653, (1999) · Zbl 0973.90526
[31] Todd, MJ; Toh, KC; Tütüncü, RH, On the Nesterov-Todd direction in semidefinite programming, SIAM J. Optim., 8, 769-796, (1998) · Zbl 0913.90217
[32] Yang, X.; Liu, H.; Zhang, Y., A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming, Inter. J. Comput. Math., 91, 1082-1096, (2014) · Zbl 1297.90112
[33] Ye, Y., A class of projective transformations for linear programming, SIAM J. Comput., 19, 457-466, (1990)
[34] Zhang, Y., On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim., 4, 208-227, (1994) · Zbl 0803.90092
[35] Zhang, Y., On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM J. Optim., 8, 365-386, (1998) · Zbl 0913.65050
[36] Zhang, Y.; Zhang, D., On polynomial of the Mehrotra-type predictor-corrector interior-point algorithms, Math. Program., 68, 303-318, (1995) · Zbl 0837.90087
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.