×

Symmetric primal-dual path-following algorithms for semidefinite programming. (English) Zbl 0956.90027

A framework for developing and analyzing primal-dual interior point algorithms for semidefinite programming problems is proposed. The \(v\)-space concept for linear programming, which was introduced by M. Kojima, N. Megiddo, T. Toshito and A. Yoshise [see “A unified approach to interior point algorithms for linear complementarity problems”, Berlin (1991; Zbl 0766.90077)], is extended to semidefinite programming problems. This concept is based on the symmetric primal-dual transformation and the existence of primal-dual scaling in case of linear programming. It is shown that this property of linear programming can be inherited to some extent by semidefinite programming.
Taking this fact into account, the following three primal-dual interior point algorithms are generalized from linear programming to semidefinite programming: 1) the short step primal-dual path following algorithm, 2) the predictor-corrector algorithm, and 3) the largest step algorithm. If \(\varepsilon\) is the required precision, an \(O(\sqrt{n} \log (1/\varepsilon))\) bound on the number of main iterations for these algorithms is derived.

MSC:

90C22 Semidefinite programming
90C51 Interior-point methods

Citations:

Zbl 0766.90077
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5, 13-51 (1995) · Zbl 0833.90087
[2] Alizadeh, F.; Heaberly, J. A.; Overton, M., Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results, (Technical Report (1996), Computer Science Department, New York University: Computer Science Department, New York University New York) · Zbl 0911.65047
[3] Berkelaar, A. B.; Sturm, J. F.; Zhang, S., Polynomial primal-dual cone affine scaling for semidefinite programming, (Report 9667/A (1996), Econometric Institute, Erasmus University: Econometric Institute, Erasmus University The Netherlands) · Zbl 0956.90025
[4] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory, (Studies in Applied Mathematics, 15 (1994), SIAM: SIAM Philadelphia, PA) · Zbl 0816.93004
[5] de Klerk, E.; Roos, C.; Terlaky, T., Polynomial primal-dual affine scaling algorithms in semidefinite programming, (Technical Report 96-42 (1996), Faculty of Technical Mathematics and Computer Sciences, Delft University of Technology: Faculty of Technical Mathematics and Computer Sciences, Delft University of Technology The Netherlands) · Zbl 0911.90252
[6] Gonzaga, C. C., Interior path following algorithms, (Birge, J. R.; Murty, K. G., Mathematical Programming, State of the Art 1994 (1994), University of Michigan: University of Michigan Ann Arbor), 93-101
[7] Gonzaga, C. C., The largest step path following algorithm for monotone linear complementarity problems, Math. Programming, 76, 309-332 (1997) · Zbl 0882.90122
[8] Helmberg, C.; Rendl, F.; Vanderbei, R. J.; Wolkowicz, H., An interior-point method for semidefinite programming, SIAM J. Optim., 6, 342-361 (1996) · Zbl 0853.65066
[9] Jarre, F., An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices, SIAM J. Control Optim., 31, 1360-1377 (1993) · Zbl 0780.65023
[10] Kojima, M.; Mizuno, S.; Yoshise, A., A polynomial algorithm for a class of linear complementarity problems, Math. Programming, 44, 1-26 (1989) · Zbl 0676.90087
[11] Kojima, M.; Megiddo, N.; Noma, T.; Yoshise, A., A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems (1991), Springer: Springer Berlin · Zbl 0745.90069
[12] Kojima, M.; Shindoh, S.; Hara, S., Interior-point methods for the monotone linear complementarity problem in symmetric matrices, (Research Report on Information Sciences, B-282 (1994), Department of Information Sciences, Tokyo Institute of Technology: Department of Information Sciences, Tokyo Institute of Technology Tokyo, Japan) · Zbl 0872.90098
[13] Mizuno, S.; Todd, M. J.; Ye, Y., On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18, 4, 964-981 (1993) · Zbl 0810.90091
[14] Monteiro, R. D.C.; Adler, I., Interior path following primal-dual algorithms. Part 1: Linear programming, Math. Programming, 44, 27-41 (1989) · Zbl 0676.90038
[15] Monteiro, R. D.C., Primal-dual path following algorithms for semidefinite programming, SIAM J. Optim., 7, 663-678 (1997) · Zbl 0913.65051
[16] Nesterov, Y.; Nemirovsky, A., Interior Point Polynomial Methods in Convex Programming, (Studies in Applied Mathematics, 13 (1994), SIAM: SIAM Philadelphia, PA) · Zbl 0754.90042
[17] Nesterov, Y.; Todd, M. J., Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22, 1-42 (1997) · Zbl 0871.90064
[18] Nesterov, Y.; Todd, M. J., Primal-dual interior-point methods for self-scaled cones, (Technical Report 1125 (1995), School of Operations Research and Industrial Engineering, Cornell University: School of Operations Research and Industrial Engineering, Cornell University Ithaca, NY) · Zbl 0922.90110
[19] Sturm, J. F., Primal-dual interior point approach to semidefinite programming, (Ph.D. Thesis (1997), Thesis Publishers: Thesis Publishers Amsterdam), Tinbergen Institute Research Series 156
[20] Sturm, J. F.; Zhang, S., On weighted centers for semidefinite programming, (Report 9636/A (1996), Econometric Institute, Erasmus University: Econometric Institute, Erasmus University The Netherlands) · Zbl 0992.90051
[21] Vandenberghe, L.; Boyd, S., A primal-dual potential reduction method for problems involving matrix inequalities, Math. Programming, 69, 205-236 (1995) · Zbl 0857.90104
[22] L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev.; L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev. · Zbl 0845.65023
[23] Zhang, Y., On extending primal-dual interior-point algorithms from linear programming to semidefinite programming, (Technical Report (1995), Department of Mathematics and Statistics, University of Maryland: Department of Mathematics and Statistics, University of Maryland Baltimore County, Baltimore, MD) · Zbl 0913.65050
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.