×

Solving semidefinite programming problems via alternating direction methods. (English) Zbl 1098.65069

The author proposes an alternating direction method to solve the semi definite programming problem. In this respect the complementary conditions in the primal-dual optimality conditions are reformulated as a projection equation and based on this reformulation at each iterate is needed only to solve a linear system with reduced dimension and make one projection. It is proved that the algorithm converges to a solution of the semidefinite programming problem under weak conditions.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C22 Semidefinite programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F., Interior point methods in semidefinite programming with application to combinatorial optimization, SIAM J. Optim., 5, 13-51 (1995) · Zbl 0833.90087
[2] Alizadeh, F.; Haeberly, J. P.A.; Overton, M. L., Primal-dual interior point methods for semidefinite programming: convergence rates, stability and numerical result, SIAM J. Optim., 8, 746-768 (1998) · Zbl 0911.65047
[3] Fortin, M.; Glowinski, R., Augmented Lagrangian Methods: Application to the Solution of Boundary-valued Problems (1983), North-Holland: North-Holland Amsterdam
[4] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appl., 2, 17-40 (1976) · Zbl 0352.65034
[5] Glowinski, R., Numerical Methods for Nonlinear Variational Problems (1984), Springer: Springer New York · Zbl 0575.65123
[6] Han, Q. M., Projection and contraction methods for semidefinite programming, Appl. Math. Comput., 95, 275-289 (1998) · Zbl 0938.90054
[7] He, B. S., A new method for a class of linear variational inequalities, Math. Programming, 66, 137-144 (1994) · Zbl 0813.49009
[8] He, B. S., Solving a class of linear projection equation, Numer. Math., 68, 71-80 (1994) · Zbl 0822.65040
[9] He, B. S.; Liao, L. Z.; Han, D. R.; Yang, H., A new inexact alternating directions method for monotone variational inequality, Math. Programming, 92, 103-118 (2002) · Zbl 1009.90108
[10] He, B. S.; Zhou, J., A modified alternating direction for convex minimization problems, Appl. Math. Lett., 13, 123-130 (2000) · Zbl 0988.90020
[11] Helebery, C.; Rendl, F.; Vanderbei, R.; Wolkowicz, H., An interior point method for semidefinite programming, SIAM J. Optim., 6, 342-361 (1996) · Zbl 0853.65066
[12] Kanzow, C.; Nagel, C., Semidefinite programming: new search direction, smoothing-type methods and numerical results, SIAM J. Optim., 13, 1-23 (2002) · Zbl 1029.90052
[14] 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
[15] Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0241.90052
[16] Monteiro, R. D.C., Primal-dual path following algorithms for semidefinite programming, SIAM J. Optim., 7, 663-678 (1997) · Zbl 0913.65051
[17] Nesterov, Y.; Nemirovskii, A., Interior Point Polynomial Algorithm in Convex Programming (1994), SIAM: SIAM Philadelphia, PA · Zbl 0824.90112
[18] Potra, F. A.; Sheng, R. Q., A superlinearly convergent primal-dual infeasible interior point algorithm for semidefinite programming, SIAM J. Optim., 8, 1007-1028 (1998) · Zbl 0917.65058
[19] Tseng, P., Merit function for semidefinite complementarity problems, Math. Programming, 83, 159-185 (1998) · Zbl 0920.90135
[20] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 49-95 (1996) · Zbl 0845.65023
[21] Wang, S. L.; Yang, H.; He, B. S., Solving a class of asymmetric variational inequalities by a new alternating direction method, Comput. Math. Appl., 40, 927-937 (2000) · Zbl 0959.49009
[23] Zhang, Y., On extending some interior point algorithms from linear programming to semidefinite programming, SIAM J. Optim., 8, 365-386 (1998) · 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.