×

A conversion of an SDP having free variables into the standard form SDP. (English) Zbl 1146.90492

Summary: This paper deals with a semidefinite program (SDP) having free variables, which often appears in practice. To apply the primal-dual interior-point method, we usually need to convert our SDP into the standard form having no free variables. One simple way of conversion is to represent each free variable as a difference of two nonnegative variables. But this conversion not only expands the size of the SDP to be solved but also yields some numerical difficulties which are caused by the non-existence of a primal-dual pair of interior-feasible solutions in the resulting standard form SDP and its dual. This paper proposes a new conversion method that eliminates all free variables. The resulting standard form SDP is smaller in its size, and it can be more stably solved in general because the SDP and its dual have interior-feasible solutions whenever the original primal-dual pair of SDPs have interior-feasible solutions. Effectiveness of the new conversion method applied to SDPs having free variables is reported in comparison to some other existing methods.

MSC:

90C22 Semidefinite programming
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R., Magnanti, T., Orlin, J.: Network Flows–Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993) · Zbl 1201.90001
[2] Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., Mckenney, A., Sorensen, D.: LAPACK Users’ Guide Third. SIAM, Philadelphia (1999) · Zbl 0934.65030
[3] Borchers, B.: SDPLIB 1.2, a library of semidefinite programming test problems. Optim. Methods Software 11&12, 683–690 (1999) · Zbl 0973.90522 · doi:10.1080/10556789908805769
[4] Fujisawa, K., Fukuda, M., Kojima, M., Nakata, K.: Numerical evaluation of SDPA (SemiDefinite Programming Algorithm). In: Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.) High Performance Optimization, pp. 267–301. Kluwer Academic, Dordrecht (2000) · Zbl 0952.90047
[5] Fujisawa, K., Kojima, M., Nakata, K.: Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Math. Program. 79, 235–253 (1997) · Zbl 0887.90156
[6] Fukuda, M., Braams, B.J., Nakata, M., Overton, M.L., Percus, J.K., Yamashita, M., Zhao, Z.: Large-scale semidefinite programs in electronic structure calculation. Math. Program., to appear · Zbl 1278.90495
[7] Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: General framework. SIAM J. Optim. 11, 647–674 (2000) · Zbl 1010.90053 · doi:10.1137/S1052623400366218
[8] Helmberg, C.: Semidefinite programming for combinatorial optimization. Habilitationsschrift. ZIP Report ZR-0034, TU Berlin, Konrad-Zuse-Zentrum, Berlin (2000). Available at http://www.zip.de/PaperWeb/abstracts/ZR-0034/ · Zbl 0960.65074
[9] 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 · doi:10.1137/0806020
[10] 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 · doi:10.1137/S1052623494269035
[11] Lasserre, J.B.: Global optimization with polynomials and the problems of moments. SIAM J. Optim. 11, 796–817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[12] Monteiro, R.D.C.: Primal–dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7, 663–678 (1997) · Zbl 0913.65051 · doi:10.1137/S1052623495293056
[13] Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results. Math. Program. 95, 303–327 (2003) · Zbl 1030.90081 · doi:10.1007/s10107-002-0351-9
[14] Nakata, K., Yamashita, M., Fujisawa, K., Kojima, M.: A parallel primal–dual interior-point method for semidefinite programs using positive definite matrix completion. Parallel Comput. 32, 24–43 (2006) · doi:10.1016/j.parco.2005.07.002
[15] Nakata, M., Nakatsuji, H., Ehara, M., Fukuda, M., Nakata, K., Fujisawa, K.: Variational calculations of fermion second-order reduced density matrices by semidefinite programming algorithm. J. Chem. Phys. 114, 8282–8292 (2001) · doi:10.1063/1.1360199
[16] Nesterov, Yu.E., Todd, M.J.: Primal–dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324–364 (1998) · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[17] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11&12, 625–653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[18] Tütüncü, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95, 189–217 (2003) · Zbl 1030.90082 · doi:10.1007/s10107-002-0347-5
[19] Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 218–242 (2006) · Zbl 1109.65058 · doi:10.1137/050623802
[20] GLOBAL Library: http://www.gamsworld.org/global/globallib.htm · Zbl 1208.93090
[21] Vanderbei, R.J., Carpenter, T.J.: Symmetric indefinite systems for interior point methods. Math. Program. 58, 1–32 (1993) · Zbl 0791.90033 · doi:10.1007/BF01581257
[22] Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA6.0 (SemiDefinite Programming Algorithm 6.0). Optim. Methods Software 18, 491–505 (2003) · Zbl 1106.90366 · doi:10.1080/1055678031000118482
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.