×

zbMATH — the first resource for mathematics

A successive quadratic programming algorithm for SDP relaxation of Max-Bisection. (English) Zbl 1150.90005
Summary: A successive quadratic programming algorithm for solving SDP relaxation of Max-Bisection is provided and its convergence result is given. The step-size in the algorithm is obtained by solving \(n\) easy quadratic equations without using the linear search technique. The numerical experiments show that this algorithm is rather faster than the interior-point method.
MSC:
90C22 Semidefinite programming
90C55 Methods of successive quadratic programming type
Software:
SDPpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barahon F, Grotschel M. An appliction of combinatorial optimization to statiscal optimization and circuit layout design, Operation Research, 1998, 36(3):493–513. · Zbl 0646.90084 · doi:10.1287/opre.36.3.493
[2] Chang K C, Wang D H. Eifficient algorithms for layer assignment problems, IEEE Trans Comput Aided Design, 1987, 6(1): 67–78. · Zbl 05447564 · doi:10.1109/TCAD.1987.1270247
[3] Ye Yinyu. A 0.699-approximation algorithm for Max-Bisection, Math Prog, 2001, 90(1): 101–111. · Zbl 1059.90119 · doi:10.1007/PL00011415
[4] Helberg C, Rendel F. An interior point method for semidefinite programming, SIAM J Optim, 1990, 10: 842–861.
[5] Mu Xuewen, Liu Sanyang, Liu Hongwei, et al. A projected gradient algorithm for Max-Bisection, J Engineering Math, 2005, 22(1): 171–174. · Zbl 1119.90337
[6] Mäkelä M M, Neittaanmäki P. Nonsmooth optimization: analysis and algorithms with application to optimization control, Singapore: World Scientific, 1992. · Zbl 0757.49017
[7] Nayakakuppam M V, Overton M L, Schemita S. SDPpack user’s guide-version 0.9 Beta, Technical Report Yr 1997-737, Courtant Institute of Mathematical Science, New York: NYU, 1997.
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.