×

Feasible direction algorithm for solving the SDP relaxations of quadratic \(\{-1,1\}\) programming problems. (English) Zbl 1072.65081

Author’s abstract: We propose a feasible direction algorithm for solving the semidefinite programming (SDP) relaxations of quadratic \(\{-1,1\}\) programming problems. This algorithm’s distinguishing features are that it uses a low rank factorization and searches with a constant step-size. Its convergence is also proven. Finally, we report some numerical examples to compare our method with the low rank factorization of S. Burer and R. D. C. Monteiro [Math. Program., 95B, No. 2, 329–357 (2003; Zbl 1030.90077)] on the SDP of the max-cut problem.

MSC:

65K05 Numerical mathematical programming methods
90C10 Integer programming
90C20 Quadratic programming
90C22 Semidefinite programming

Citations:

Zbl 1030.90077
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1287/opre.36.3.493 · Zbl 0646.90084
[2] DOI: 10.1109/TCAD.1987.1270247 · Zbl 05447564
[3] DOI: 10.1109/TCS.1983.1085357 · Zbl 0505.94031
[4] DOI: 10.1145/227683.227684 · Zbl 0885.68088
[5] DOI: 10.1137/S1052623497328008 · Zbl 0997.90059
[6] DOI: 10.1137/0806020 · Zbl 0853.65066
[7] DOI: 10.1137/S1052623497328987 · Zbl 0960.65074
[8] DOI: 10.1137/S1052623400382467 · Zbl 1152.90532
[9] DOI: 10.1006/jpdc.1997.1381
[10] DOI: 10.1080/10556780108805818 · Zbl 1109.90341
[11] DOI: 10.1007/s10107-002-0352-8 · Zbl 1030.90077
[12] DOI: 10.1007/BF02574037 · Zbl 0829.05025
[13] DOI: 10.1287/moor.23.2.339 · Zbl 0977.90051
[14] Helmberg C., Semidefinite Programming for Combinatorial Optimization (2000) · Zbl 0960.65074
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.